c – 这个for循环的时间复杂度是多少(与`n`有关)？

发布时间：2020-12-16 09:22:10 所属栏目：百科来源：网络整理

导读：这个for循环的时间复杂度是多少(与n有关)？ for(int i = 1,j; i = n; i = j + 1){ j = n / (n / i);} 请注意,i,j和n是整数变量,它们遵循整数运算.特别是,循环内的表达式n /(n / i)应解释如下：解决方法如果我们使用j = i;而不是j = n /(n / i);,时间复杂度

这个for循环的时间复杂度是多少(与n有关)？

for(int i = 1,j; i <= n; i = j + 1)
{
        j = n / (n / i);
}

请注意,i,j和n是整数变量,它们遵循整数运算.特别是,循环内的表达式n /(n / i)应解释如下：

enter image description here

解决方法

如果我们使用j = i;而不是j = n /(n / i);,时间复杂度是O(n).
现在它是j = n /(n / i);,假设n = i * k r,其中k和r都是整数,r = n％i.因此j =(i * kr)/((i * kr)/ i)=(i * kr)/ k = ir / k> = i,这意味着我将比你使用j = i的情况增加得更快;.所以至少时间复杂度小于O(n),我想这给你另一个O(n).

除了大O表示法之外,还有另外两种符号(Θ和Ω),这意味着O(n)的下限和上限.通过找到这两个边界,您可以获得时间复杂性.如果我没记错的话还有另一条规则,O(k * n)= O(n),系数k无论多大都无关紧要.

（编辑：李大同）

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