List의 removeAll() 과 clear() 비교

removeAll()과 clear() 시간 복잡도 비교 먼저 removeAll()의 시간복잡도는 반복문이 1개라면 O(n) 선형 알고리즘이고, 반복문이 2개 중첩되있다면 O(n^2)이 된다. 반복문이 몇번 실행되었는지 주목해야한다!⭐️ 예를 들어 길이가 n인 리스트가 있고, 제거할 요소가 m개라면 이 때 removeAll()의 시간복잡도는 O(nm)이다. 하지만 길이가 n인 리스트에서 제거할 요소 또한 n개라면 시간 복잡도는 O(n^2)이 되겠다.

1. removeAll() : 전체 리스트 중에서 특정 Collection에 포함된 요소들만 제거한다! removeAll(Collection<?> c) > batchRemove(Collection<?> c, boolean complement) > contain() 아래 코드에서 li.removeAll(m)은 li에서 특정 Collection인 m에 포함된 요솓들만 제거하는 것이다!

public class Main{
    public static void main(String[] args){
        List<Integer> li = new ArrayList<>();
        Set<Integer> m = new HashSet<>();
        for(int i=0;i<100000;i++){
            li.add(i);m.add(i);
        }
        li.removeAll(m);
    }
}

2. clear() : 전체 리스트를 비운다! 시간복잡도는 O(n)

컬렉션 별 add, remove, contain, get 메서드 시간 복잡도 비교 =>특히 Set > HashSet의 contain()은 key값으로 바로 찾아버리기 때문에 O(1)로 매우 빠르다!

https://unordinarydays.tistory.com/194