循环时间有限的循环复杂度分析
Complexity analysis of loop with limited looping time
我想知道下面代码的 big-o 复杂度应该是 o(1) 还是 o(n)。
for(int i=0;i<n && n<100;i++){sum++;}
这是我的想法：
由于 n 被限制为低于 100，最坏情况将是 O(99) + O(98) + ... + O(1) = 99 * O(1) = O(1)
然而，凭直觉，由于循环，代码在某种程度上是 O(n)。
如果有人能就此向我提出建议，我将不胜感激。
谢谢！
直觉上它是 O(1)，因为随着 n 的增加，运行时间在某个点后不会增加。然而，这是一个边缘情况，因为 n 受一个更大的数字的限制，比如 int 的最大值，这似乎与 n 完全没有限制的情况没有什么不同。但是，在使用复杂性理论考虑运行时时，我们通常会忽略诸如 int 的最大大小之类的东西。
另一种思考方式是，迭代次数随 n 线性增长，对于 n in (0,100)，否则为常数。然而，当考虑 n 可以是任何值时，算法肯定是 O(1)
这都是假设循环的每次迭代都需要恒定的时间。
有关更多信息，请查阅刘维尔定理。
我想知道下面代码的 big-o 复杂度应该是 o(1) 还是 o(n)。
for(int i=0;i<n && n<100;i++){sum++;}
这是我的想法： 由于 n 被限制为低于 100，最坏情况将是 O(99) + O(98) + ... + O(1) = 99 * O(1) = O(1) 然而，凭直觉，由于循环，代码在某种程度上是 O(n)。
如果有人能就此向我提出建议，我将不胜感激。 谢谢！
直觉上它是 O(1)，因为随着 n 的增加，运行时间在某个点后不会增加。然而，这是一个边缘情况，因为 n 受一个更大的数字的限制，比如 int 的最大值，这似乎与 n 完全没有限制的情况没有什么不同。但是，在使用复杂性理论考虑运行时时，我们通常会忽略诸如 int 的最大大小之类的东西。
另一种思考方式是，迭代次数随 n 线性增长，对于 n in (0,100)，否则为常数。然而，当考虑 n 可以是任何值时，算法肯定是 O(1)
这都是假设循环的每次迭代都需要恒定的时间。
有关更多信息，请查阅刘维尔定理。