BigO 표기법으로 최적화하기

BigO 표기법?

- 시간 복잡도를 쉽게 소통하기 위해서 자료구조와 알고리즘의 효율성을 일관되게 설명하는 수학적 개념을 형식화한 표현
- 일관되게 어떤 알고리즘이든 분석할 수 있다.
- 알고리즘의 성능이나 복잡성을 분석할 때 사용된다.
- 시간 복잡도 혹은 공간 복잡도를 나타낼 때 사용된다.
- 데이터가 늘어날 때 알고리즘의 성능이 어떻게 변화하는지 추세를 나타낸다.
- 대문자 O에 괄호 안에는 수식을 넣어 표기한다. Ex.) O(N), O(1), O(logN)

 

BigO를 사용하는 이유

---

빅오 표기법은 알고리즘의 효율성을 평가하는 데 중요한 도구이다. 빅오 표기법을 사용하여 알고리즘의 수행 시간을 예측하고 비교할 수 있다. 빅오 표기법을 이용하여 실행 시간이 더 적은 알고리즘을 선택하여 처리 시간을 단축할 수 있다.

 

또한, 빅오 표기법은 알고리즘의 성능을 분류하고 이해하는 데 도움이 된다. 알고리즘이 실행될 때 필요한 단계수를 예측하고 알고리즘을 최적화하거나 개선할 수 있다.

빅오 표기법 종류

✔️O(1): 상수 시간 (데이터 수에 상관 없이 연산 횟수 고정)

✔️O(logN): 로그 시간 (데이터 수 증가율 > 연산횟수 증가율)

✔️O(N): 선형 시간 (데이터 수와 연산 횟수 비례)

✔️O(N*logN): 로그 선형 시간 (데이터 수 2배 증가 -> 연산 횟수 2배 조금 넘게 증가)

✔️O(c^n): 지수 시간 (지수적으로 증가)

 

 

O(N)

---

선형 검색은 배열에서 특정 원소를 찾기 위해서 앞에서부터 하나씩 원소를 확인해가면서 값을 찾는다. 예를 들어 아래 배열에서 3이라는 값을 찾고자 했을 때, 컴퓨터의 입장에서는 3이라는 값이 어디에 있는지 알 수 없다. 그래서 배열의 앞에서부터 하나씩 값을 찾아야하기 때문에 3이라는 값을 찾기 위해서 총 6단계가 걸린다. 만약 배열의 크키가 10이고 3이 맨 마지막 셀에 위치해 있었다면 3이라는 값을 찾기 위해 총 10번을 비교해야 한다.

배열에 원소가 N개일 때 선형 검색에서는 N단계가 필요하다. 빅오로 표현한다면 O(N)이고 이를 선형 시간을 갖는 알고리즘이라고 한다. O(N) 알고리즘은 데이터의 크기가 늘어나게 되면 알고리즘의 실행 단계도 비례해서 증가한다. 데이터가 하나 추가 될 때마다 알고리즘도 한 단계씩 더 걸리기 때문에 O(N) 알고리즘을 그래프로 보면 완벽한 대각선을 이룬다.

O(1)

---

배열의 읽기를 할 때에는 한 번의 단계로 바로 값을 읽을 수 있다. 컴퓨터는 모든 메모리 주소에 한 번에 갈 수 있고 배열을 할당할 때 어떤 메모리 주소에서 시작하는 기록도 해두기 때문이다. 예를 들어, 컴퓨터 인덱스 5에 있는 값을 찾으려고 할 때 컴퓨터는 인덱스 0의 메모리 주소를 가져와 5를 더해서 값을 한 번에 찾아낸다. 그래서 배열의 읽기의 빅오는 O(1)이라고 한다. 데이터가 늘어나도 알고리즘의 단계수는 늘어나지 않기 때문에 0(1)은 상수 시간을 갖는 알고리즘이라고 한다.

 

데이터가 늘어나도 단계 수가 한 단계로 일정하기 때문에 0(1) 알고리즘을 그래프로 보면 완벽한 수평선을 이룬다.

O(logN)

---

O(logN)으로 표기하는 대표적인 예는 이진 검색이다. 원소가 하나가 될 때까지 데이터 원소를 계속해서 반으로 줄이는 만큼의 단계 수가 걸리기 때문에 O(logN)이다. 즉, 데이터 원소가 N개가 있을 때 알고리즘에 logN 단계가 걸린다는 의미이다.

 

O(logN) 알고리즘은 데이터가 두 배로 증가할 때 마다 한 단계씩 늘어난다. 그래서 O(logN) 알고리즘의 그래프는 아주 조금씩 증가하는 곡선을 그린다.

 

세 종류의 알고리즘을 비교하는 그래프

---

 

Ex.)

중복된 값이 있으면 ture를 중복된 값이 없으면 false를 리턴하는 이중루프 함수이다.

const hasDuplicatedNumber = (number) => {
	for(let i = 0; i < numbers.lenght; i++){ // O(N)
    	for(let j = 0; j < numbers.length; j++){ O(N)
        	if(i !== j && numbers[i] === numbers[j]){
            	return true;
            }
        }
    }
    
    return false;
}

// O(N*N)
// O(N^2)

 

위에와 같이 O(N^2)의 알고리즘을 가진 함수를 O(1)의 알고리즘으로 변경해보자.

 

const hasDuplicatedNumber = (numbers) => {
	const existingNumbers = [];
    
    for(let i=0; i < numbers.length; i++){ //O(N)
    	if(existingNumbers[numbers[i]]) {
        	return true;
        } else {
        	existingNumbers[numbers[i]] = true; // O(1)
        }
    }
    
    return false;
}

//O(N*1)

 

빅오 표기법을 이해하면 처음에 만들었던 O(N^2)과 비교했을 때 훨씬 더 빠르다는 것을 알 수 있다.