빅오 표기법, 시간 복잡도, 공간 복잡도

이진 탐색 트리 O(log n)

노드의 수는 8이므로 O(log 8) = 3이다. 만약 위와 같은 이진 탐색 트리에 1을 삽입하려면 1은 5보다 작으므로 왼쪽(1번), 1은 3보다 작으므로 왼쪽(2번), 1은 2보다 작으므로 왼쪽(3번)으로 가게 되고 3번의 비교만에 2의 자식 노드가 된다.

퀵 정렬, 병합 정렬, 힙 정렬 O(n log n)

6 4 3 1 을 하나의 원소가 될 때까지 나누려면 2번 나누면 된다. O(log 4) = 2, 원소의 개수만큼 버퍼에 원소를 넣어야 하므로 병합하려면 4번 해야한다. 병합 정렬의 시간 복잡도는 O(n log n)이다. 병합 정렬은 어떤 상황이던 O(n log n)의 시간 복잡도를 갖는다. 정렬이 어느 정도 되어 있는 배열이라면 다른 소트를 사용해야 한다.

삽입 정렬, 버블 정렬, 선택 정렬 O(n^2)

버블 소트 https://github.com/minsuk-heo/problemsolving/blob/master/sort/BubbleSort.py

6531

5631

5361

5316

3516

3156

1356 이런 식이다.

선택 정렬 https://github.com/minsuk-heo/problemsolving/blob/master/sort/SelectionSort.py

461352 에서 첫번째 원소인 4가 가장 작은 값이라고 가정하고 이보다 작은 값이 나타나면 그 값을 가장 작은 값에 넣는다. 배열을 끝까지 탐색하고 가장 작은 값과 첫번째 원소를 스와핑한다. 두번째 인덱스로 이동하여 반복한다.

461352 포인트 1번째, 초기 최소값 4, 4랑 1의 위치 바꿈

164352 포인트 2번째, 초기 최소값 6, 6이랑 2의 위치 바꿈

124356 포인트 3번째, 초기 최소값 4, 4랑 3의 위치 바꿈

123456 포인트 4번째, 초기 최소값 4, 그대로

123456 포인트 5번째, 초기 최소값 5, 그대로

123456 포인트 6번째, 초기 최소값 6, 그대로

삽입 정렬 https://github.com/minsuk-heo/problemsolving/blob/master/sort/InsertionSort.py

461352 에서 정렬되지 않은 데이터를 정렬된 데이터에 삽입하는 것이다. 데이터가 정렬된 데이터보다 작다면 그 앞에 넣고 나머지는 뒤로 미는 것이다.

461352 포인트 1

461352 포인트 2

461352 포인트 3

146352 포인트 4

134652 포인트 5

134562 포인트 6

123456 끝