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