algorithm - 时间复杂度: Continuously summing the digits of a number until a single digit result

Question

给我一​​个数字 N。不断对数字求和，直到结果为一位数。 例如 35252 ==> 17 ==> 8 我编写了以下代码:

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。

在最坏的情况下，全部都是 9，递归将达到最大值两次，我将得到 O(loglogn)

在最好的情况下，对于个位数 N，复杂度将为 O(1)

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

Answer 1

首先，你的分析是错误的，最坏情况下时间复杂度不是O(loglogn)，而是O(logn) ，具有以下递归公式:

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

现在，我们可以证明上面的内容在 O(logn) 中，使用归纳法，归纳假设为: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))是相当微不足道的，观察 T(n) >= 0对于所有人n .

---

关于手头的问题，平均时间复杂度是多少，让我们用G(n)来表示平均情况复杂度。 ，我们假设 n是均匀分布的(如果不是 - 这将改变分析，结果可能会不同)。

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 中仍然是对数的.