4장 빅 오로 코드 속도 올리기

1. 버블 정렬

• 정렬 알고리즘: 정렬되지 않은 배열이 주어졌을 때, 어떻게 오름차순으로 정렬할 수 있을까?
• 2 1 3 5
• 위와 같은 배열이 있을 때, 포인터 1은 2를, 포인터 2는 1을 가리킨다.
• 포인터 1 > 포인터 2 일 때, 두 항목을 교환한다.
• 포인터들은 한 칸씩 이동하며 두 항목을 비교하고 필요시 두 항목을 교환한다.
• 이렇게 한 번 배열 전체를 pass through하고 나면, 다시 맨 왼쪽으로 포인터를 옮겨 교환이 일어나지 않을 때까지 반복한다.

2. 버블 정렬의 구현

• 생략
• 파이썬 코드 예쁘다

3. 버블 정렬의 효율성

• 버블 정렬 알고리즘에서 중요한 단계는 비교와 교환이다.
• 비교: 배열 크기가 N이라고 했을 때, 비교는 N - 1 + N - 2 + N - 3 + … + 1번 실행된다.
• 교환: 내림차순으로 정렬된 배열(최악의 시나리오)에서 교환의 실행 횟수를 셀 때는 비교할 때마다 교환을 실행해야 한다. 즉, 비교의 실행 횟수와 같다.
• 최악의 시나리오에서 비교와 교환의 횟수는 대략 N^2이다.
• O(N^2)

4. 이차 문제

• O(N^2) 알고리즘을 O(N) 알고리즘으로 대체할 수 있을까?
• 숫자로 이루어진 배열에 중복되는 숫자가 들어 있는지 확인하는 함수
• for(i in 0 until list.size){ for(j in i + 1 until list.size){ if(list[i] == list[j]){ return true } } } return false
• 위 코드는 O(N^2) 알고리즘이다.

5. 선형 해결법

var existingNum = IntArray()
for (i in 0 until arr.size){
	if(existingNum[arr[i]] == 1)
		return true
	else
		existingNum[arr[i]] = 1
}
return false

• existingNum이라는 배열에 중복 여부를 표시하게 한다.
• 위 코드는 O(N) 알고리즘이다.

6. 마무리

• 빅 오 표기법은 대부분의 알고리즘의 속도를 비교하고 판별할 수 있다.
• 그러나 빅 오 표기법으로 판별이 불가능한 경우가 존재한다.
• 5장에서는 빅 오 표기법으로는 유의미한 차이를 발견할 수 없는 알고리즘의 효율성을 어떻게 판단하는지 살펴본다.