[누구나 자료구조와 알고리즘] 3장. 빅오표기법

빅오표기법: 시간 복잡도를 효율적으로 나타내기 위한 표기법

• 탄생배경
• 어떤 알고리즘을 "22단계의 알고리즘"과 같은 식으로 표기하는 방식은 원소수가 달라질 때마다 몇 단계가 필요한지 달라지기 때문에 부적절하다.
• 또한 "N개의 원소가 있을 때 선형 검색에 N단계가 필요하다"와 같은 표기는 너무 길다.

O(N): 데이터 원소가 N개일 때 알고리즘에 몇 단계가 필요한지 표기

• 빅오표기법은 최악의 경우를 상정해 표기한다.
• 위의 표기는 선형검색에서 최악의 경우를 고려하여 표현한 것이다.
• 빅오표기법은 "데이터 원소가 N개일 때 알고리즘에 몇 단계가 필요할까?"에 대한 답을 표현한 것이다.
• 그에 대한 답은 "알고리즘에 N단계가 필요하다"는 것이다.

O(1): 가장 빠른 알고리즘 유형 = 상수 시간을 갖는 알고리즘

• 읽기는 배열에 원소가 몇 개든, 항상 1단계만 소요된다.
• 데이터가 늘어나도 알고리즘의 단계수는 증가하지 않는다.

빅오로 구분하는 알고리즘 유형

• 빅오의 본질은 데이터가 늘어날 때 알고리즘의 성능이 어떻게 바뀌는지를 의미한다.
• 1) O(1)이든, O(3)이든 데이터 증가에 영향을 받지 않는 유형이므로, 둘을 구분할 필요가 없다. 즉, O(3)이라 표기하지 않고 O(1)로 표기한다.
• 2) O(N)은 데이터 증가가 성능에 영향을 미치므로, O(1)과는 다른 유형이다.
• 이러한 내용은 아래 그래프로 확인할 수 있다.

 

O(N)과 항상 100단계가 걸리는 알고리즘의 효율성 비교

• 아래 그래프를 보면, 특정 원소수를 기준으로, 100 미만은 O(N)이, 100 초과는 100단계 알고리즘이 더 낫다고 볼 수 있다.

 

 

이진검색의 빅오표기: O(logN) - 데이터가 두 배로 증가할 때마다 한 단계씩 늘어나는 알고리즘

• '로그 시간의 시간 복잡도'의 유형
• O(logN)
  • O(log2(N))에서 2를 생략한 것
  • 데이터 원소가 N개 있을 때 알고리즘에 log2(N) 단계가 걸린다는 의미이다.
  • 즉, O(logN)은 원소가 하나가 될 때까지 데이터 원소를 계속해서 반으로 줄이는 만큼의 단계 수가 걸린다.
• 알고리즘의 효율성 비교: O(1) > O(logN) > O(N)

- 로가리즘(로그)

• 로가리즘은 지수와 역의 관계다.
• log2(8) = 3
  • 2의 3제곱의 역으로, 2를 3번 곱해야 8을 얻을 수 있다.
  • 1이 나올 때까지 8을 2로 몇 번 나눠야 하는지 계산하면 구할 수 있다.

 

O(logN) VS O(N)

1) O(logN): 데이터 원소가 두 배로 늘어날 때마다 딱 한 단계만 더 필요하다.

2) O(N): 데이터 원소 수만큼의 단계가 필요

---

연습문제 - 각 함수의 시간복잡도 구하기

 

1. 

function isLeapYear(year) {
	return (year % 100 === 0) ? (year % 400 === 0) : (year % 4 === 0);
}

O(1)

- 어떤 수가 들어오든 항상 한 단계만 수행하므로(데이터가 늘어남에 따라 영향을 받지 않으므로) 상수 시간의 알고리즘이다.

 

2.

function arraySum(array) {
	let sum = 0;
    
    for(let i = 0; i < array.length; i++) {
    	sum += array[i];
    }
    
    return sum;
}

O(N)

- 배열의 길이에 따라 단계가 달라지므로 O(N)이다.

 

3. 

function chessboardSpace(numberOfGrains) {
	let chessboardSpaces = 1;
    let placedGrains = 1;
    
    while (placedGrains < numberOfGrains) {
    	placedGrains *= 2;
        chessboardSpaces += 1;
    }
    
    return chessboardSpaces;
}

O(logN)

- N이 두 배 늘어날 때마다 루프를 한 번 더 실행하므로 O(logN)이다.

 

4. 

function selectAStrings(array) {
	let newArray = [];
    
    for(let i=0; i < array.length; i++) {
    	if (array[i].startsWith("a")) {
        	newArray.push(array[i]);
        }
    }
    
    return newArray;
}

O(N)

- 어떤 배열이 오든, 배열의 모든 자리수를 검사해야 하므로 O(N)이다.

 

5. '정렬된' 배열의 중앙값 구하기 함수

function median(array) {
	const middle = Math.floor(array.length / 2);
    
    if (array.length % 2 === 0) {
    	return (array[middle - 1] + array[middle]) / 2;
    } else {
    	return array[middle];
    }
}

O(1)

- 한 번만 수행한다.