问简单2例算法分析
EN

Stack Overflow用户

提问于 2017-11-16 15:04:45

回答 1查看 47关注 0票数 0

嗯，我正在为即将到来的考试学习算法，我很难验证下面的练习是否正确。

 i=1
 while(i<=n)
      j=1
      while(j<i)
            j=j+1
      i=i*2

我对这个问题的回答是O(n.log n)

i=1
 while(i<=n)
      j=1
      while(j<i)
            j=j*2
      i=i+1

我再一次回答为O(n.log n)

有人能证实我的回答是否正确吗？另外，任何关于分析未来实践的建议都是受欢迎的。

回答已采纳

发布于 2017-11-16 18:25:56

是的，每一个都是O(n log )。您有一个循环，它是线性迭代，即O(n)。您有另一个指数型循环；相反的是log，所以这个循环是O(log )。由于它们是嵌套的，所以您需要多重复杂性，并得到O(n log )。

票数 0

页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持

原文链接：

https://stackoverflow.com/questions/47332963

复制

相似问题

问简单2例算法分析EN