algorithm - 解释为什么对长度为 N 的数字求和的时间复杂度是 O(logN)

Question

代码如下:

int sumDigits(int n) {
    int sum = 0;

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

    return sum;
}

我理解这段代码，代码将取个位数字，将该数字加到总和中，然后删除该数字。它一直这样做，直到 n 等于 0，此时它将返回 sum。直观上运行时间将是数字 N 中的位数。但我不明白为什么这个时间复杂度是 O(logN)。我以为是 O(N)。

即使有这样的解释:“具有 d 位的数字的值最大为 10^d。如果 n = 10^d，则 d = log n。因此运行时间为 O(logN)。”没有完全点击。

我遵循第一部分，如果 d 为 3，则值 < 10^d == 值 < 1000。意思是最大值为 999，数字长度为 3，我同意这一点。但是在那之后，当他们建立起如果 n = 10^d 的联系时，我不明白 1) 他们如何知道要实现相等以及 2) 这如何使复杂度为 O(logN) 而不是 O(N)。

Answer 1

复杂度与位数成正比。毕竟，如果数字中有 2,351 位，则 while循环将迭代 2,351 次。

所以问题归结为“N 中有多少位，渐近？”。带有 d 的数字数字介于 10^(d-1) 之间包括和10^d独家的。换句话说，让d是 N 中的位数，我们有不等式10^(d-1) <= N < 10^d .取对数，我们有 d-1 <= log(N) < d . (我们可以保持不等式，因为对数是单调的。)添加 1左边的不等式给出 d <= log(N) + 1 ，结合前面的结果，我们有log(N) < d <= log(N) + 1 .也就是说，我们设置了位数的上限和下限 d。按条款 O(log(N)) .

上面显示位数为O(log(N)) ，或更准确地说 Theta(log(N)) .时间复杂度是相同的，因为它与位数成正比。