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

概述这个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);,时间复杂度是O(n). 现在它是j = n /(n / 这个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);,时间复杂度是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无论多大都无关紧要.

总结

以上是内存溢出为你收集整理的c – 这个for循环的时间复杂度是多少(与`n`有关)？全部内容，希望文章能够帮你解决c – 这个for循环的时间复杂度是多少(与`n`有关)？所遇到的程序开发问题。

如果觉得内存溢出网站内容还不错，欢迎将内存溢出网站推荐给程序员好友。