解释为什么对长度为 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，则 value < 10^d == value < 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))。时间复杂度是相同的，因为它与位数成正比。

Answer 2

您混淆了N这里的两个定义。您的文本将其引用为数字本身；您的后一个描述视为N数字的数量。是的，该算法的复杂度为O(digits) ...但数字的数量大致为log10(N)，其中N是数字。