3

麻省理工学院 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 为底的对数。

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

有人可以解释一下吗？

4

3 回答 3

6

花费的时间取决于x十进制数中的位数。正十进制数中的位数x是floor(log10(x)) + 1（维基百科对为什么这是真的有很好的解释）：

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

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

于 2013-10-11T13:31:28.557 回答
3

好吧，您实际上已经回答了您的问题：

复杂性实际上取决于列表 S 的长度，而不是 C 的选择变化

list 的长度S是 number 中的位数x。一个数字的位数是它的对数的底数加一。

Range of numbers   Range of log (base 10) value    Number of digits
           1 - 9                         [0, 1)                   1
         10 - 99                         [1, 2)                   2
       100 - 999                         [2, 3)                   3
     1000 - 9999                         [3, 4)                   4
   10000 - 99999                         [4, 5)                   5

因此，无论数字是多少，这里唯一重要的是其中的位数，并且该数字等于floor(log10(x)) + 1。

这可以推广到任何数字基数：整数的 -base 表示中n的位数等于plus的-base log 的下限值。bxbx1

例如，二进制数的位数为

Decimal range    Binary range    Range of log (base 2) value    Number of bits
            1               1                         [0, 1)                 1
        2 - 3         10 - 11                         [1, 2)                 2
        4 - 7       100 - 111                         [2, 3)                 3
       8 - 15     1000 - 1111                         [3, 4)                 4
      16 - 31   10000 - 11111                         [4, 5)                 5
于 2013-10-11T13:44:03.953 回答
2

他解释说（正如我能够理解的那样），每次循环迭代，C 可以是十位数字（0-9）之一，这使得以 10 为底的对数。

这不是原因。可以采用哪些值并不重要c。重要的是它需要多少个值 - 答案是：它为 中的每个数字取一个值x。并且x有 O(log 10 x ) 十进制数字。这就是数字表示的工作方式：任何基数b中的任何数字n的表示都有 log b n +1 位。

于 2013-10-11T13:33:01.830 回答