Python MIT讲座:log(n)示例的复杂性

Question

有麻省理工学院python编程课程的代码,第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带到logarythm.

但是我无法理解,为什么会这样呢？原因复杂性实际上取决于列表S的长度,而不是C的选择变化.

有人可以解释一下吗？

Answer 1

花费的时间取决于x作为十进制数的位数.正十进制数的位数x是floor(log10(x)) + 1(维基百科有一个很好的解释,为什么这是真的):

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

因此,时间的复杂性与log10一样,正如教授所述.换句话说,随着x增加,我们需要处理的位数增加为log10(x).