首页
学习
活动
专区
圈层
工具
发布
首页
学习
活动
专区
圈层
工具
MCP广场
社区首页 >问答首页 >这个代码片段的时间复杂度是多少?

这个代码片段的时间复杂度是多少?
EN

Stack Overflow用户
提问于 2022-10-15 15:03:55
回答 1查看 82关注 0票数 1

考虑到迭代器上的增量的问题,我通过用自己的日志值递增它的值来实现。这个片段的大O时间复杂度是什么?

代码语言:javascript
运行
复制
i = 10
while(i<n) {
    i=i+log(i);
}
EN

回答 1

Stack Overflow用户

发布于 2022-10-15 18:14:15

让我们稍微看看g(N)= O(f(n))的定义:说函数g是O(f(N))表示存在一个数n0和一个常数c,使得对于所有n>n0,它是g(n)<=cf(n)。

在最坏的情况下,while将运行n次,这意味着我们可以说您的代码是O(n)顺序的。

现在让我们假设while循环中的代码是

代码语言:javascript
运行
复制
(*) while(i<n) {
       i = i + i ;
   } 

显然应该跳过更多的迭代,而不是原来的迭代。所以我们可以用这个代码来估计一个下界。检查(*)我们看到,在每一次迭代中,计数器都是双倍的,如果我们稍微考虑一下,我们就会发现,对于n次迭代,每次有一半的输入会被丢弃。因此,(*)中的代码将有最坏的情况渐近运行时O(log )。

现在我们估计原码应该介于两者之间,所以我们可以说它的渐近下界是Ω(log ),它的渐近上界是O(n)。

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

https://stackoverflow.com/questions/74080580

复制
相关文章

相似问题

领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档