代码复杂度 [英] Code complexity

问题描述

任何人都可以向我解释以下代码的时间复杂度：

Can anybody explain to me the time complexity of the following code:

cin >> n;
while(n>9)
{
    int num = n;
    int s = 0;
    while(num!=0)
    {
        s = s + num%10;
        num = num/10;
    }
    n = s;
}
cout<<n<<endl;

上面的代码将计算数字的总和，直到总和变为一个数字为止。

The above code calculates the sum of the digits of the number until the sum becomes a single digit number.

示例： 45859 = 4 + 5 + 8 + 5 + 9 = 31 = 3 + 1 = 4

Example: 45859 = 4+5+8+5+9 = 31 = 3+1 = 4

编辑：我认为，计算数字总和的内部循环的复杂度为O（log_base_10（n）），但外部循环一直持续到到目前为止获得的总和小于10。所以总复杂度取决于外循环要运行多少次。我无法弄清楚……某种数学头来计算复杂度

I think that the inner loop calculating the sum of digits has O(log_base_10(n)) complexity, but the outer loop continues till the sum obtained so far is less than 10. So the total complexity depends on how many times the outer loop is going to run.. I am not able to figure that out... Some kind of mathematical gimmicks to calculate the complexity of the outer loop would help!!!

推荐答案

您正在计算数字的总和。 n 中的位数与log（ n ）成比例。

You are calculating the sum of the digits. The number of digits in n scales with log(n).

这篇关于代码复杂度的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！