Java - addDigits 方法的大O？

Question

这段代码的大O是什么？我认为它是O(logn)，因为每次递归，num都会得到/= 10。否则，它一定是O(n)。对此有什么想法吗？

P.S:不是家庭作业问题，只是面试复习。所以欢迎回答。

public class Solution {
    public int addDigits(int num) {
        int sum = 0;
        while (num > 0){
            sum += num % 10;
            num /= 10;
        }
        if (sum < 10){
            return sum;
        }
        else{
            return addDigits(sum);
        }
    }
}

Answer 1

我认为 O(logn) 不是正确答案，因为 O(logn) 仅覆盖第一个 while 循环您计算第一个总和。但当 sum 大于 10 时，您将进行另一轮计算，即 O(log(sum)) + 如果新的 sum 为另一轮计算大于 10。所以:

• 第一个计算是 logn
• 第一个总和将小于 9 * logn(例如，如果第一个数字是 4 位数字，则它将小于 9999，因此第一个总和将小于 9 * 4) ，因此第二次计算最多为 log(9 * logn) + 第二个和的计算
• 第二个总和将小于 9 * log(9 * logn)，因此第三次计算最多为 log(9 * log(9 * logn)) + 第三个总和的计算。
• 诸如此类

所以最终值似乎是O(logn + log(logn) + log(log(logn)) + ...) - 当 log(log(.. .(logn)..)) = 0.