时间复杂度：连续将数字的数字求和，直到得到一位数字 [英] Time Complexity : Continuously summing the digits of a number until a single digit result

问题描述

给我一​​个数字N。继续对数字求和，直到得出一位数字。
例如35252 ==> 17 ==> 8
我编写了以下代码：

I am given a number N. Keep summing the digits until a single digit result. e.g 35252 ==> 17 ==> 8 I have written the following code :

int digitSum(int n)
{
    int sum = 0;
    int digit;

    while(n)
    {
        digit = n%10;
        n = n/10;
        sum += digit;
    }

    if(sum > 9)
        return digitSum(sum);
    else
        return sum;
}

时间复杂度：
N为0 <== N <= 10 ^ 9。

Coming to the time complexity : I am given the range for N as 0 <= N <= 10^9.

在最坏的情况下，所有9s都将递归两次，并且得到O（loglogn ）

In worst case, with all 9s, the recursion will go max twice and I will get O(loglogn)

在最佳情况下，使用个位数N时，复杂度将为O（1）

In best case, with single digit N, complexity will be O(1)

将是平均复杂度？我的意思是，如果N可以是没有定义范围的任何数字，那么复杂度是多少。

What will be the average complexity? I mean, what will be the complexity if N can be any number with no range defined.

推荐答案

首先，您的分析是错误的，在最坏的情况下，时间复杂度不是O（loglogn），它是 O（logn），具有以下递归公式：

First, your analysis is wrong, the time complexity is not O(loglogn) for worst case, it's O(logn), with the following recursive formula:

T(n) = logn + T(log(n) * AVG(digits)) = logn + T(9*logn)
T(1) = 1

现在，我们可以显示上面的内容在 O（logn）中，使用归纳假设为： T（n）< = 2logn

Now, we can show that the above is in O(logn), using induction with the induction hypothesis of: T(n) <= 2logn

T(n+1) = log(n+1) + T(9logn) <= (i.h) log(n+1) + 2*log(9log(n)) =
       = log(n+1) + 2log(9) + 2loglog(n) < 2log(n)

显示它是 Omega（log（n））非常简单，观察到对于所有 n T（n）> = 0 >。

Showing it is Omega(log(n)) is pretty trivial, with the observation that T(n) >= 0 for all n.

关于眼前的问题，平均时间复杂度是多少，让我们表示 G（n），并假设 n 是均匀分布的（如果不是，这将改变分析和结果可能会有所不同。）

Regarding the question at hand, what is the average time complexity, let's denote the average case complexity with G(n), and let's assume n is uniformly distributed (if it's not - that will change the analysis, and the outcome might be different).

G(N) = lim{N->infinity} sum{i=1 to N} T(n)/N =
     = lim{N->infinity} T(1) / N + T(2) / N + ... + T(N) / N
     = lim{N->infinity} 1/N (T(1) + T(2) + ... + T(N))
     < lim{N->infinity} 1/N (2log(1) + 2log(2) + ... + 2log(N)) 
     = lim{N->inifnity} 2/N (log(1) + ... + log(N))
     = lim{N->inifnity} 2/N (log(1 * 2 * ... * N))
     = lim{N->infinity} 2/N log(N!) 
     = lim{N->infinity} 2/N * CONST * NlogN = 2*CONST * logN

因此，我们可以得出结论： G（N）也在 O中（logN），因此平均案例分析在 N 中仍然是对数的。

So, we can conclude G(N) is also in O(logN), so the average case analysis is still logarithmic in N.

这篇关于时间复杂度：连续将数字的数字求和，直到得到一位数字的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！