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

Question

代码如下：

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

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

    return sum;
}

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

即使有这样的解释： "A number with d digits can have a value up to 10^d. If n = 10^d, then d = log n. Therefore runtime is 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 次。

所以问题归结为，"how many digits are there in N, asymptotically?"。具有 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。也就是说，我们根据 O(log(N)).

项对位数 d 设置了上限和下限

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

Answer 2

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

Answer 3

你会记得：log(10) = 1，只要N<100，log(100) = 2，对数就保持小于2，依此类推。

出现的简单规则是：将特征加 1 以获得数字中的数字位数。

或者，在更简短的数学符号中，使用 floor 函数，D = ⌊log10N⌋+1

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

Explain why time complexity for summing digits in a number of length N is O(logN)

algorithm

runtime

time-complexity