Python MIT 讲座 : log(n) complexity of the example

Question

有来自 MIT python 编程类(class)第 8 课的代码。

def(x):
    assert type(x) == int and x >= 0
    answer = 0 
    s = str(x)
    for c in s :
        answer += int(c)
    return answer 

正如教授所说，此代码的复杂度是 (x) 的以 10 为底的对数。他解释说(正如我能够理解的那样)，每次循环迭代，C 可以是十位数字 (0-9) 之一，这使以 10 为底的对数成为对数。

但是我不明白，为什么会这样？原因复杂性实际上取决于列表 S 的长度，而不是 C 的选择变化。

谁能解释一下？

Answer 1

花费的时间取决于x中的位数为十进制数。正十进制数 x 中的位数是 floor(log10(x)) + 1(Wikipedia 对此有一个很好的解释):

>>> from math import log10
>>> 
>>> x = 12345
>>> int(log10(x)) + 1
5

因此，正如教授所说，时间复杂度为 log10。换句话说，随着 x 的增加，我们需要处理的数字的数量增加为 log10(x)。