python - while 循环之间的大 O 表示法

Question

帮助找到以下代码的大Oh符号:

i = n
while i > 0:
    k = 2 + 2
    i = i // 2

我认为它是n，因为n被分配然后循环。这是正确的吗？

Answer 1

思考这个问题的简单方法(可以用作通用方法)如下:

• i 的初始值为 n
• 一旦 i 达到 0，代码将停止循环(因此，当 i 为 1 时将执行最后一次迭代)

• 执行任意次数的迭代(将该次数称为c)后，i 的值为

   ((n / 2) / 2) / ... )     = n / (2 ^ c) 
       ^ divide by 2 c times 
  

因此，在循环结束时，我们需要 (n/(2 ^ c)) = 1。求解c 得到c = logn。

所以大复杂度是O(logn)。 (也就是说，假设 n 是整数而不是 float )。