빅 오로 코드 속도 올리기

빅 오를 사용하여 내가 만든 알고리즘 세상에 존재하는 범용 알고리즘을 비교하여 코드 속도를 늘릴 수 있다.

버블 정렬

단순 정렬이라고 알려진 알고리즘의 분류 중 하나이다.
버블 정렬은 주어진 배열의 값을 차례대로 비교하며 교환한다.

그림과 같은 배열이 있다면 버블 정렬을 어떻게 동작할까??
4와 2를 비교하고 4가 크다면 2와 교환한다. 이 작업을 배열의 마지막 인덱스까지 반복한다.
이러한 동작을 완료하면 마지막 인덱스 4에는 값은 기존 배열에 가장 큰 값을 가지게 된다.
그헣다면 인덱스를 4를 제외하고 위 작업을 반복한다. 이 작업을 반복하면 결국 오른차순 정렬이된다.

버블 정렬 코드

public class Bubble_Sort {
	public static void bubble_sort(int[] a) {
		bubble_sort(a, a.length);
	}
	private static void bubble_sort(int[] a, int size) {
		// round는 배열 크기 - 1 만큼 진행됨 
		for(int i = 1; i < size; i++) {
			// 각 라운드별 비교횟수는 배열 크기의 현재 라운드를 뺀 만큼 비교함
			for(int j = 0; j < size - i; j++) {
				/*
				 *  현재 원소가 다음 원소보다 클 경우
				 *  서로 원소의 위치를 교환한다. 
				 */
				if(a[j] > a [j + 1]) {
					swap(a, j, j + 1);
				}
			}
		}
	}
	private static void swap(int[] a, int i, int j) {
		int temp = a[i];
		a[i] = a[j];
		a[j] = temp;
	}
}

버블 정렬 효율성

버블 정렬의 중요한 두 단계는 다음과 같다.
바로 비교, 교환이다.
크기가 5인 배열의 버블 정렬의 비교는 몇 번이 일어 날까??
4 + 3 + 2 + 1 = 10 총 10번이 일어난다.
이를 N으로 표기한다면 (N-1) + (N+2) .... + 1이다. 교환 또한 비교와 똑같이 동작하므로 10번이 일어난다. 그럼 총 20단계를 거친다.
이를 표로 만들어 비교해보면

위 표와 같다. 대략 N^2만큼 작업 단계를 거치는 것을 확인 할 수 있다.
그러므로 버블 정렬의 빅 오는 O(N^2)이다.
이를 O(n)과 비교한다면, 다음과 같은 결과를 확인 할 수 있다.

데이터가 커지수록 단계 수가 매우 급격히 증가한다. 이러한 O(n^2)을 이차 시간이라고도 부른다.

이차 문제와 선형 해결법

아래와 같은 O(n^2) 코드를 O(n)으로 해결해보자.
배열에 중복되는 숫자가 있다면 중복 숫자를 알리는 코드가 있다.

for(int i = 0; i<arr.length(); i++){
	for(int j = i; j < arr.length(); j++{
    	if(arr[i] == arr[j]) return true;
    }
}
return false;

이 코드는 버블 정렬과 마찬 가지고 O(n^2) 동작한다. (n-1) + (n-2) + .... + 1
이 코드를 좀 더 빠른 알고리즘을 적용 해보자.

boolean[] ls = new boolean[1000];
for(int i = 0; i < arr.length(); i++){
	if(ls[i]) return true;
    else ls[i] = true;
}
return false;

이 코드를 사용하게 되면 for 단 한번으로 중복 숫자를 확인 할 수 있다.
보통 크기가 하나씩 증가하거나 감소하는 for문의 경우 O(n) 동작하고,
중첩 될 경우 O(n^2) 동작한다.
이를 통해 빅 오 방식으로 실제 코드의 효율성을 올리는 방법을 알 수 있었다.