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 / 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无论多大都无关紧要.