我正在練習 Codility。有一個簡單級別的問題，但我被困在性能上。測驗結果分析將此代碼標記為O(N**2)，但顯然沒有任何嵌套回圈。誰能告訴我為什么我的代碼是 O(N**2)？
public static int solution(int X, int[] A) {
List<Integer> temp = new ArrayList<>();
for (int i = 1; i <= X; i ){
temp.add(i);
}
int counter = 0;
int res = -1;
for (int i: A){
if (temp.contains(i)) {
temp.remove(new Integer(i));
}
if (temp.size() == 0){
res= counter;
break;
}
counter ;
}
if (temp.size() != 0){
res = -1;
}
return res;
}
uj5u.com熱心網友回復：
那是因為使用了contains. temp是ArrayList，并contains執行線性查找。在 for 回圈中，這將變為O(N2)。
uj5u.com熱心網友回復：
測驗結果分析將此代碼標記為O(N**2)，但顯然沒有任何嵌套回圈。誰能告訴我為什么我的代碼是 O(N**2)？
漸近復雜性不僅僅是關于回圈計數。您在 的元素上有一個回圈A，并在其中temp.contains()有條件地呼叫temp.remove()。對于ArrayList，其中每個的成本與 中的元素數量成正比temp。
總的來說，如果N是A.length那么你的方法的漸近復雜度是 O(X * N)。那么，Codility 的分析并不完全正確，但是如果X不能被視為以常數為界，那么您的代碼仍然比O(N). 如果 Codility 進行了啟發式分析，在X和之間引入了人工關系N，那么根據該函式關系，您的方法確實可以是 O(N 2 )。
uj5u.com熱心網友回復：
另一個回圈隱藏在 的 remove 方法中ArrayList。的 remove 方法ArrayList是 O(N)，因為它必須移動元素以填充間隙。
for (int i: A){ // ===> O(N)
if (temp.contains(i)) {
temp.remove(new Integer(i)); //===> O(N)
}
if (temp.size() == 0){
res= counter;
break;
}
counter ;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/net/383711.html
上一篇：來自Peggy生成的決議器的回呼
下一篇：使用后綴增量運算子將值添加到陣列