在分析這樣的代碼的時間復雜度時，我對我的假設的正確性有點懷疑。在這段代碼中，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)。
有人可以糾正我嗎？謝謝！
uj5u.com熱心網友回復：
j < array.length()被稱為array.length()*array.length()次。
如果array.length()是 O(1)，則 O(N^2)。（例如 C ）
如果array.length()是 O(N)，則 O(N^3)。（例如 Cstrlen()盡管代碼可能會將其優化回 O(1)）
uj5u.com熱心網友回復：
編譯器可能會做一個簡單的優化：
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)
轉載請註明出處，本文鏈接：https://www.uj5u.com/ruanti/344355.html
上一篇：具有1個回圈的函式的復雜性