什么时候循环内的语句会影响复杂性？
when would a statement inside a loop affect the complexity?
例如，如果我有
for(int i = 1; i < 500; i++){
for (int j = 0; j < N; j++){
if (array[j] == someNumber && i == someNumber)
counter++;
}
}
如果数组中的所有数字都相同，因此每个数字的计数器都会增加，这会使复杂度为 O(2N)、O(N 的平方) 还是仍然只是 O(N)，而它永远不会变成了 O(2N)？我希望这个问题是有道理的。我发现很难理解语句如何影响复杂性。
由于循环内的语句需要常数时间，因此它们对算法的整体复杂性没有任何影响。您发布的代码的复杂性仅为 O(N)，因为您的外循环执行了常数次，而您的内循环执行了 N 次。
一个重要的示例是，如果您在循环内执行某些操作，例如调用一个函数来搜索数组中的值，或对列表进行排序。由于这些操作取决于数组（或列表）的大小，因此在计算算法的复杂性时必须将它们考虑在内。
例如，如果我有
for(int i = 1; i < 500; i++){
for (int j = 0; j < N; j++){
if (array[j] == someNumber && i == someNumber)
counter++;
}
}
如果数组中的所有数字都相同，因此每个数字的计数器都会增加，这会使复杂度为 O(2N)、O(N 的平方) 还是仍然只是 O(N)，而它永远不会变成了 O(2N)？我希望这个问题是有道理的。我发现很难理解语句如何影响复杂性。
由于循环内的语句需要常数时间，因此它们对算法的整体复杂性没有任何影响。您发布的代码的复杂性仅为 O(N)，因为您的外循环执行了常数次，而您的内循环执行了 N 次。
一个重要的示例是，如果您在循环内执行某些操作，例如调用一个函数来搜索数组中的值，或对列表进行排序。由于这些操作取决于数组（或列表）的大小，因此在计算算法的复杂性时必须将它们考虑在内。