빅 오로 코드 속도 올리기
4-1. 버블 정렬
정렬되지 않은 배열이 주어졌을 때, 어떻게 오름차순으로 정렬할 수 있을까?
- 배열 내 첫 번째 원소부터 시작해서 연속된 두 원소를 가리킨다.
두 항목을 비교한다.
| 2 | 1 | 3 | 4 |
|---|---|---|---|
| ↑ | ↑ |
- 왼쪽 값이 오른쪽 값보다 크면, 두 항목의 자리를 바꾼다.
순서가 올바르다면 아무것도 하지 않는다.
- 포인터를 오른쪽으로 한 셀씩 옮긴다.
| 1 | 2 | 3 | 4 |
|---|---|---|---|
| ↑ | ↑ |
- 배열 끝까지 또는 정렬된 값까지 1단계부터 3단계를 반복한다.
첫 번째값부터 마지막 값까지 끝나면 첫 패스스루(pass-through)가 끝난 것이다.
| 1 | 2 | 3 | 4 |
|---|
- 다시 두 포인터를 첫 번째, 두번째 값으로 옮겨서 변경이 일어나지 않을 때까지 패스스루를 반복한다. 변경할 항목이 없으면 정렬이 완료된 것이다.
4-2. 버블 정렬 실제로 해보기
예제를 통해서 버블 정렬를 해보자!
배열 [4,7,2,1,9]
- 첫 번째, 두 번째 값을 비교해서 4 < 7이기 때문에 그대로 둔다.
| 4 | 7 | 2 | 1 | 9 |
|---|---|---|---|---|
| ↑ | ↑ |
- 오른쪽으로 한 셀씩 이동해서 비교한 후 순서를 바꾼다.
| 4 | 7 | 2 | 1 | 9 |
|---|---|---|---|---|
| ↑ | ↑ |
- 오른쪽으로 한 셀씩 이동해서 비교한 후 순서를 바꾼다.
| 4 | 2 | 7 | 1 | 9 |
|---|---|---|---|---|
| ↑ | ↑ |
- 끝까지 이동해서 비교 후 변경한다.
| 4 | 2 | 1 | 7 | 9 |
|---|
- 다시 첫 번째 값부터 시작해서 정렬이 완료될 때까지 패스스루(pass-through) 반복한다.
| 1 | 2 | 4 | 7 | 9 |
|---|
4-2-1. 버블 정렬 구현
- Javascript로 구현한 버블 정렬
function bubble_sort(list) {
let unsorted_until_index = list.length - 1;
let sorted = false;
while (!sorted) {
sorted = true;
for (let i = 0; i < unsorted_until_index; i++) {
if (list[i] > list[i + 1]) {
// 배열 요소를 교환할 때, 임시 변수 temp를 사용하여 두 값을 서로 교환
let temp = list[i];
list[i] = list[i + 1];
list[i + 1] = temp;
sorted = false;
}
}
// 반복문이 한 번 완료되면 가장 큰 값이 배열의 끝으로 이동했으므로
// 다음 반복에서는 마지막 인덱스는 무시해도 됩니다.
unsorted_until_index -= 1;
}
return list;
}4-3. 버블 정렬의 효율성
배열 N개의 원소가 있을 때 모든 값이 정렬되지 않았을 경우,
- 비교(comparison): (N-1)+(N-2)+(N-3)+ ・・・ +1번
- 교환(swap): (comparison): (N-1)+(N-2)+(N-3)+ ・・・ +1번 (최악의 경우)
비교와 교환이 원소 수가 증가할수록 기하급수적으로 증가한다. 다음 표로 원소 개수에 따라 최대 단계 수를 알 수 있다.
| 데이터 원소 N개 | 최대 단계 수 |
|---|---|
| 5 | 20 |
| 10 | 90 |
| 20 | 380 |
| 40 | 1560 |
| 80 | 6320 |
N이 증가할 때마다 대략 N^2만큼 늘어남을 알게 된다.
| 데이터 원소 N개 | 최대 단계 수 | N^2 |
|---|---|---|
| 5 | 20 | 25 |
| 10 | 90 | 100 |
| 20 | 380 | 400 |
| 40 | 1560 | 1600 |
| 80 | 6320 | 6400 |
버블 정렬의 시간 복잡도를 빅 오 표기법으로 나타내면, O(N^2)이라고 할 수 있다. 그래프에서 O(N)보다 더 가파른 기울기를 갖는다. O(N^2)을 이차 시간이라고 부른다.
4-4. 이차 문제
중첩 for문은 배열 N개 값이 있을 때, 1차 for문에서 N번, 2차 for문에서 N번 순회하기 때문에 O(N^2) 시간복잡도를 갖는다. 그렇기 때문에 중첩 for문을 사용할 때는 성능 면에서 좋지 않을 수 있다.
function checkDuplicate (array) {
for (let i=0; i<array.length; i++) {
for (let j=0; i<array.length; j++) {
if (i !==j && array[i] === array[j]) {
return true;
}
}
}
return false;
}4-5. 선형 해결법
중첩 for 문을 사용하지 않고 더 나은 시간복잡도가 나오도록 선형 해결법을 사용해보자.
- 'existingNumber'이라는 빈 배열을 만든다.
- for문을 통해 array를 순회하면서 값이 있으면 existingNumber의 array[i]번째 인덱스에 1를 넣고, 이미 해당 인덱스에 1이 있으면 중복이 있다는 것으로 알고 true를 반환한다.
- array의 모든 원소를 순회할 때까지 중복된 값이 없으면 false를 반환한다.
function checkDuplicate(array) {
let existingNumber = [];
for (let i=0; i<array.length;i++){
if (existingNumber[array[i]] === 1) {
return true;
} else {
existingNumber[array[i]] === 1
}
}
return false
}선형 해결법은 array를 모두 순회하기 때문에 O(N) 시간복잡도가 걸린다.
O(N)이 O(N^2)보다 효율적이다.
연습문제
- 원소 수가 100와 2000인 배열이 O(logN)과 O(N^2)일 때 각각 단계 수를 구하시오.
1. 100개일 때,
O(N) 7단계
O(N^2) 알고리즘이라면 약 10,000단계의 시간
2. 2000개일 때,
O(N) 11단계
O(N^2) 알고리즘이라면 약 4,000,000단계의 시간- 시간 복잡도가 O(N^2)인 알고리즘이 256단계가 걸렸다면, 이 배열의 크기는 얼마일까?
- 16개
256 = n^2
n^2 = 256
n = √256
n = 16- 중첩 for문을 사용한 알고리즘의 시간 복잡도를 구하시오.
- O(N^2), 중첩 for문을 사용해서 O(N^2)이 걸린다.
- 배열에서 제일 큰 숫자를 찾는 알고리즘을 O(N) 시간복잡도가 걸리도록 만드시오.
- (참고) Math.max() 매서드가 아래와 같은 로직을 갖는다.
function greatesNumber(array) {
let answer = 0;
for(let i=0; i<array.length; i++) {
if (answer < array[i]) {
answer = array[i];
}
}
return answer;
}
개발이 너무 좋다. 정말 잘 하고 싶다.