알고리즘 강의

Java 알고리즘

시간 복잡도 : 문제를 해결하는데 걸리는 시간

int maxInt = 0;
        for (int i = 0; i < array.length; i++) {
            if (array[i] > maxInt) {
                maxInt = array[i];
            }
        }
        System.out.println(maxInt);

위와 같은 로직에서 변수를 할당하고, 출력하는 로직은 for문과 비교하면 무의미하기 때문에 무시하고, for문의 반복 횟수에 집중한다. 위에서는 array.lenght만큼 반복하기 때문에,  array.lenght = n 이라고 한다면 위 로직은 n만큼 시간을 쓴다고 하고, big-O 표기법을 쓰면 O(n)과 같이 표기한다. O(n)은 최악의 경우(가장 오래 걸리는 경우)를 고려해서 표기한다.

 

공간 복잡도 : 문제를 해결하는데에 대한 공간간의 상관관계 <- 크게 중요치 않아서 공간을 너무 헤프게 쓰지만 않는다면 알고리즘의 성능을 위해 공간을 더 쓰는 것을 주저하지 않아도 됨.

 

자료구조

ArrayList : 조회(index) - O(1), 첫번째,마지막 자료 삽입/삭제 - O(1), 정렬 - O(1), 가운데 자료 삽입/삭제 - O(n), 검색(value) - O(n)

LinkedList : 조회(index) - O(n), 어디에 있는 자료든 삽입/삭제 - O(1), 검색(value) - O(n)

Set : 조회 - O(1), 삽입/삭제 - O(1), 정렬 - Set은 해당 기능 지원X

Map : 조회 - O(1), 삽입/삭제 - O(1), 정렬 - Map은 해당 기능 지원X