python – 这个函数的大O符号是什么

发布时间：2020-12-20 13:15:26 所属栏目：Python 来源：网络整理

导读：result = 0 i = 0 while i 2**n: result = result + i i += 1 # end while 我假设O(2 ^ n). Python代码. 解决方法我认为你的代码的时间复杂度是O(2 ^ n log n),因为你计算2 ^ n,持续2 ^ n次. a ^ b可以在O(log b)中计算 exponentiation by squaring,我认为p

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

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

解决方法

我认为你的代码的时间复杂度是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).

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!