這個循環的複雜性

Question

我很困惑，因爲方法的運行時間。方法如下：

public void remove(List<String> list){ 
     for(int i = 0; i < list.size(); i++) 
      list.remove(0); 
     } 

有人請向我解釋爲什麼這隻會運行N/2次而不是N次？

Answer 1

因爲在每一個循環中，您要刪除第0個元素，在N/2次迭代之後，「i」將是N/2，列表的大小也將是N/2。所以之後，循環將退出。

請注意，列表大小減少1，「i」增加1，因此N/2次迭代。

如果N是奇數，它將是（N/2）+1。

Answer 2

這是因爲你正在循環list.size（）條件。由於您在每一步都刪除了一個元素，因此list.size（）會更小。

如果你想刪除從列表中的所有元素，你可以使用list.clear（）

Answer 3

實際上，循環執行M = (N+1)/2倍，其中/是整數除法。
運行這個測試程序，你會發現爲什麼循環只運行M次。
請嘗試使用此線lst.add("FFF");註釋掉。
這裏的關鍵是，當您刪除元素時，值會更改。

import java.util.ArrayList; 
import java.util.List; 

public class Test036 { 

    public static void main(String[] args) { 
     ArrayList<String> lst = new ArrayList<String>(); 
     lst.add("AAA"); 
     lst.add("BBB"); 
     lst.add("CCC"); 
     lst.add("DDD"); 
     lst.add("EEE"); 
     lst.add("FFF"); 
     remove(lst); 

    } 

    public static void remove(List<String> list){ 
      for(int i = 0; i < list.size(); i++){ 
       String str = list.get(0); 
       list.remove(0); 
       System.out.println("Removed: " + str + " i = " + i + " size: " + list.size()); 
      } 
    } 
} 

Answer 4

既然你想刪除列表中的每一個成員，則需要執行循環的相同的次數作爲原尺寸列表。

public void remove(List<String> list){ 
    int numberOfListElements = list.size(); 
    for (int i = 0; i < numberOfListElements; i++) 
     list.remove(0); 
     } 
    }