시간복잡도

QuickSort? - 말 그대로 빠른 정렬이다. - 퀵 소트는 평균적인 시간복잡도는 O(NlogN), 최악의 경우 O(N^2) 이다. - 따로 메모리를 저장하여 정렬하지 않아서 공간복잡도는 O(1)이다! - 이러한 불규칙적 성질 때문에 불안정 정렬이라 한다. - 일단 이론이 굉장히 어려우므로 바로 설명을 가보도록 하자 과정 1. 리스트 안에 있는 한 요소(pivot)를 고르자! 2. pivot을 기준으로 큰 값은 오른쪽, 작은 값은 왼쪽으로 정렬하자~! 3. pivot의 왼쪽 부분과 오른쪽 부분을 다시 재귀로 정렬하자! 4. 단 리스트의 크기가 0, 혹은 pivot 자신만 있을 때 (1) 이면 하지 않는다! Quick 정렬에 대한 고찰 - 파티션을 나누는 과정이 MergeSort와 동일하게 2분할이다...

배열? - 배열은 연속된 자료를 저장하기 위한 선형 자료 구조다 - 배열은 기본적으로 지역적 특성을 가지고 있기 때문에 CPU가 지역 참조를 할 때 속도가 빠르다 - 다시말해서, Cache Hit 의 가능성이 커진다! - 우리는 이미 배열을 사용하는 법 을 알고 있다!! But.... new int[1000] 는 한계성이 있다. * 입력으로 들어오는 개수가 N(미지수)일 때, 어떠한 근거로 메모리를 확보해야 되는가? 에 대한 문제점 --> 정적 배열을 동적 배열로 사용하면 된다!! -> ArrayList ArrayList? - 배열의 크기를 들어오는 자료의 양에 따라서 조절할 수 있다!! - 데이터를 추가하는 데에 시간복잡도는 O(1) 에 처리할 수 있다 ▶ 하지만.... - 동적으로 메모리가 늘어나는 ..