python - 我这个时间复杂度计算哪里出错了？

Question

我在 Python 中有这个函数:

digit_sum = 0
while number > 0:
   digit_sum += (number % 10)
   number = number // 10

为了确定时间复杂度，我应用了以下逻辑:

第 1 行: 1 个基本操作(赋值)，执行 1 次因此得到值 1

第 2 行:2 个基本操作(读取变量“number”并与零进行比较)，执行了 n+1 次，因此得到的值为 2*(n+1)

第3行:4个基本操作(读取变量'number'，%10，求和，赋值)，执行n次，得到4*n的值

第 4 行: 3 个基本操作(读取变量 'number'，//10 和赋值)，执行了 n 次，因此得到的值为 3*n

这使我总共有 1 + 2n+2 + 4n + 3n = 9n+3

但是我的课本上有8n+3的解。我的逻辑哪里出了问题？

谢谢，

亚历克斯

Answer 1

当谈论复杂性时，您真正关心的是 asymptotic complexity .在这里，O(n)。 8 或 9 或 42 并不重要，尤其是因为您无法知道。

因此计算“操作”是没有意义的。它公开了底层处理器的架构细节(无论是实际的硬件过程还是解释器)。实际获得“真实”操作数的唯一方法是查看特定实现(例如，CPython 3.6.0)并查看它从您的程序生成的字节码。

这是我的 CPython 2.7.12 所做的:

>>> def test(number):
...     digit_sum = 0
...     while number > 0:
...         digit_sum += (number % 10)
...         number = number // 10
...
>>> import dis
>>> dis.dis(test)
  2           0 LOAD_CONST               1 (0)
              3 STORE_FAST               1 (digit_sum)

  3           6 SETUP_LOOP              40 (to 49)
        >>    9 LOAD_FAST                0 (number)
             12 LOAD_CONST               1 (0)
             15 COMPARE_OP               4 (>)
             18 POP_JUMP_IF_FALSE       48

  4          21 LOAD_FAST                1 (digit_sum)
             24 LOAD_FAST                0 (number)
             27 LOAD_CONST               2 (10)
             30 BINARY_MODULO
             31 INPLACE_ADD
             32 STORE_FAST               1 (digit_sum)

  5          35 LOAD_FAST                0 (number)
             38 LOAD_CONST               2 (10)
             41 BINARY_FLOOR_DIVIDE
             42 STORE_FAST               0 (number)
             45 JUMP_ABSOLUTE            9
        >>   48 POP_BLOCK
        >>   49 LOAD_CONST               0 (None)
             52 RETURN_VALUE

我让您自己得出自己的结论，即您希望将什么实际算作基本操作。 Python 解释器一个接一个地解释字节码，因此可以说您的循环中有 15 个“基本操作”。这是您可以获得的最接近有意义的数字。尽管如此，其中的每个操作都有不同的运行时间，因此 15 个操作没有任何有值(value)的信息。

此外，请记住这是特定于 CPython 2.7.12 的。另一个版本很可能会生成其他内容，利用新的字节码，可能使以更简单的方式表达某些操作成为可能。