python - 这个函数的大O表示法是什么

Question

 result = 0
 i = 0
 while i < 2**n:
      result = result + i
      i += 1
 # end while

我假设 O(2^n)。 Python 代码。

Answer 1

我认为你的代码的时间复杂度是 O(2^n log n) 因为你正在计算 2^n，对于 2^n 次。
a^b 可以在 O(log b) 中计算 exponentiation by squaring我认为 python 中的指数算法是 O(log n) 算法。
因此，时间复杂度为 O(2^n log n)。