我对这些情况的时间复杂度是正确的吗？

Question

在分析这样的代码时间复杂度时，我有点怀疑我假设的正确性。在这段代码中，array.length() 被视为线性复杂度函数。最后一个细节很重要，最初的练习认为它只是一个常量存储值，但我想知道如果不是的话会发生什么）：

void printPairs(int[] array) {
   for (int i = 0; i < array.length(), i++) {
       for (int j = 0; j < array.length(), j++){
          print(array[i], array[j])
       }
   }
}

所以，如果 array.length 是数组中的一个变量，就像 java 中的那样，所有这些东西都只是 O(N^2)。但是如果 array.length() 是一个函数呢？他的实现应该是线性的……然后……起初我认为它应该成为一个 O(N^4) 代码，但现在更好地考虑它我认为只是 O(N^3)。但我也认为这可能是我对这两个假设都错了，它一直是 O(N^2)。

有人可以纠正我吗？谢谢！

Answer 1

j < array.length() 被调用 array.length()*array.length() 次。

如果 array.length() 是 O(1)，则 O(N^2)。（例如 C++）

如果array.length()是O(N)，那么O(N^3)。（例如 C strlen() 尽管代码可能会将其优化回 O(1)）

Answer 2

很有可能编译器可以做一个简单的优化：

void printPairs(int[] array) {
   int n = array.length();
   for (int i = 0; i < n, i++) {
       for (int j = 0; j < n, j++){
          print(array[i], array[j])
       }
   }
}

那就是 O(N^2)

我对这些情况的时间复杂度是正确的吗？

I'm right about the time complexity on these situations?

arrays

algorithm

time-complexity

pseudocode