这个for循环的java复杂性

Question

我对一个方法的运行时间感到困惑。方法如下：

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

有人能给我解释一下为什么这只会运行N/2次而不是N次吗

Answer 1

这是因为你在循环列表。大小（）条件。由于每个步骤都要删除一个元素，因此列表。大小（）将更小

如果要从列表中删除所有元素，可以使用list。清除（）

Answer 2

因为在每个循环中都要删除第0个元素，在N/2次迭代之后，“i”将是N/2，列表的大小也将是N/2。所以在那之后，循环将退出

请注意，列表大小下降了1，“i”增加了1，因此N/2次迭代

如果N是奇数，它将是（N/2）+1

Answer 3

实际上，循环执行M = (N+1)/2次，其中/是整数除法
运行这个测试程序，你就会明白为什么循环只运行M次
用这句话也可以试试lst.add("FFF");注释掉
这里的关键是list.size()值在删除元素时会发生变化

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);
        }
    }