[알고리즘과 자료구조] 빅 오 표기법에 대해서

sangsang·2024년 1월 29일

누구나 자료구조와 알고리즘 알고리즘 자료구조

누구나 자료구조와 알고리즘

목록 보기

2/13

📖 '누구나 자료구조와 알고리즘' 책을 공부한 내용을 담고 있습니다.

빅 오 표기법

🤓 빅 오 표기법을 사용해 주어진 알고리즘의 효율성을 쉽게 분류하고 이해시킬 수 있다. 어떻게 빅 오 표기법으로 다양한 알고리즘을 표기하는지 알아보자.

3-1. 빅 오: 원소가 N개일 때 몇 단계가 필요할까?

빅 오는 특정 방식으로 알고리즘에 필요한 단계수를 고려함으로써 일관성을 유지한다. 다음과 같이 빅오 표기법으로 표현한다.

선형 검색

O(N)
: "빅 오 N" 또는 "오 N"으로 읽는다.
N개의 원소를 가진 배열에서 최대 N개의 단계가 필요하다는 것을 의미한다.

배열의 읽기

O(1)
: "빅 오 1" 또는 "오 1"으로 읽는다.
배열의 크기와 상관없이 항상 1단계가 걸리는 것을 의미힌다.

3-2. 빅 오의 본질

빅 오는 단순히 원소 N개에 대한 알고리즘의 단계 수가 아니라 데이터 증가에 따라 알고리즘의 성능이 어떻게 변화하는지를 나타낸다.

예를 들어, 데이터 증가에 상관없이 항상 3단계가 걸리는 알고리즘을 가정하자.
이 알고리즘은 빅 오 표기법이 O(3)이 아니라 O(1)이다. 데이터 증가에 영향을 받지 않아 항상 동일한 단계 수를 갖는 유형은 O(1) 로 표기한다. 그래프에서 완벽한 수평선을 그린다.

O(N)는 데이터가 하나씩 추가될 때마다 단계가 한단계씩 늘어난다. 즉, 데이터 수와 알고리즘의 효율성이 비례하는 관계이다. 그래프에서 완벽한 대각선을 그린다.

O(N)과 O(1)의 비교

항상 100단계가 걸리는 알고리즘 'O(1)'과 데이터 수와 단계 수가 비례하는 'O(N)'이 있다고 가정하자. 데이터 수가 100개 미만일 때 O(N)이 효율적이라고 볼 수 있지만, 100개가 넘어가면 O(1)이 효율적이다.
데이터가 무한으로 증가하면 O(1)가 효율적이게 된다. 그렇기 때문에 O(1)이 O(N)보다 효율적이라고 할 수 있다.

같은 알고리즘, 다른 시나리오

선형 검색의 시간 복잡도가 항상 O(N)이 아니다. 첫번째 인덱스에서 값을 찾았다면 O(1)이고, 마지막 인덱스에서 O(N)이다. 하지만 선형 검색의 시간 복잡도를 O(N)인 이유는 빅 오 표기법은 일반적으로 최악의 시나리오를 의미하기 때문이다.

3-3. 세 번째 유형의 알고리즘

이진 검색은 O(1)과 O(N) 사이의 시간 복잡도를 갖으며, O(LogN) 시간 복잡도를 갖는다. O(LogN)는 데이터가 두 배로 증가할 때마다 한 단계씩 늘어나는 알고리즘을 설명하는 빅 오 표기법이다.

O(LogN)
: "오 로그 N"으로 읽는다. 이 유형의 알고리즘은 로그 시간의 시간 복잡도이다.

시간 복잡도의 효율성

지금까지 살펴본 알고리즘에서 효율적인 순서는

O(1) < O(LogN) < O(N)

3-4. 로가리즘

로그는 로가리즘의 줄임말이다. 로그는 지수와 역의 관계다. log 2의 8는 2를 몇 번 곱해야 8이 나오는지를 뜻한다.

2³ = 2 × 2 × 2 = 8

log₂8 은 2³의 역
→ 2를 세 번 곱해야 8이므로 log₂8 = 3

더 쉬운 방법으로는 8이 1이 될 때까지 2를 계속해서 나눌 때 몇 번 나눠야 하는지 계산하면 된다.

8 / 2 / 2 / 2 = 1
→ 8을 2로 3번 나누면 1이 된다.

3-5. O(logN) 해석

O(logN)는 O(log₂N)에서 2를 생략한 것이다.
이진 검색 값을 찾을 때까지 배열의 크기를 반으로 나누며 범위를 좁혀 나가는 방식을 통해 O(logN)를 쉽게 이해할 수 있다. 원소가 하나가 될 때까지 데이터 크기를 반으로 줄이는 만큼의 단계 수가 걸린다는 뜻이다.

O(N)과 O(logN)의 비교

O(N)는 최대 N단계가 필요한 반면, O(logN)는 데이터 원소가 두 배로 늘어날 때마다 1단계가 더 필요하다. 그렇기 때문에 O(logN)이 O(N)보다 더 효율적이다.

3-6. 실제 예제

다음은 리스트 내 모든 항목을 출력하는 전형적인 파이썬 코드다.
이 알고리즘을 빅 오 표기법으로 어떻게 표기할 수 있을까?
<예제 1>

things = ['apples','baboons',;cribs', 'dulcimers']

for thing in things: 
	print("Here's a thing: %s" % thing)

이 예제의 알고리즘은 for 루프에서 4단계가 걸린다. 하지만 things의 크기가 100개라면 for 루프는 100단계가 걸린다. 그렇기 때문에 이 알고리즘의 시간 복잡도는 O(N)이라 할 수 있다.

<예제 2> number가 소수인지 알아보는 알고리즘이다.

def is_prime(number):
	for i in range(2, number):
    	if number % i == 0:
        	return False
    return True

number를 인수로 받아 2부터 number까지의 모든 수로 나눠서 나머지를 확인한다. 나머지가 없으면 소수가 아니므로 False, 나머지가 있으면 True를 반환한다.

함수로 전달된 number에 비례해 단계 수가 증가하므로 O(N)에 해당한다.

연습 문제

주어진 해가 윤년인지 밝히는 다음 함수의 시간 복잡도를 빅 오 표기법으로 나타내자.

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

O(1), 입력값 모두 계산 시간이 동일하기 때문이다.

주어진 배열의 모든 수를 합하는 다음 함수의 시간 복잡도를 빅 오 표기법으로 나타내자.

function arraySum(array) {
let sum = 0;

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

O(N), 배열의 크기만큼 for 문의 루프가 실행되기 때문이다.

3.다음 함수는 복리의 무서움을 보여주는 오랜 비유를 재현한 것이다. 체스판 한 칸에 쌀 한 톨을 놓는 상상을 해보자. 두번째 칸에는 이전 칸에 놓았던 쌀 양보다 두 배 더 많은 쌀 두 톨을 놓는다. 세 번째 칸에는 쌀 네 톨을 놓는다. 네 번째 칸에는 쌀 여덟 톨을 놓고 다섯 번째 칸에는 쌀 열여섯 톨을 놓는 식으로 이 과정을 반복한다. 함수는 몇 번째 칸에 일정한 수의 쌀을 놓아야 하는지 계산한다. 가령 쌀이 열여섯 톨이면 다섯 번째 칸에 놓아야 하니 함수는 5를 반환한다. 다음과 같이 구현한 이 함수의 시간 복잡도를 빅 오 표기법으로 나타내자.

function solution (number) {
let spaces = 1;
let placedGrains = 1;

while (placedGrains < number) {
placedGrains *=2;
spaces += 1;
}

return spaces;
}

O(logN), while 반복문이 placedGrains가 입력값보다 작을 때 반복되는데, placedGrains가 2의 거듭제곱만큼 증가하기 때문이다.

다음 함수는 문자열 배열을 받아 "a"로 시작하는 문자열만 포함시킨 새 배열을 반환한다. 이 함수의 시간 복잡도를 빅 오 표기법으로 나타내자.

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), 선형 검색 유형에 해당. 배열 크기에 비례하여 단계 수가 증가한다.

다음 함수는 정렬된 배열의 중앙값을 계산한다. 이 함수의 시간 복잡도를 빅 오 표기법으로 나타내자.

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];
}}