빅 오 표기법

참고: 누구나 자료 구조와 알고리즘(개정2판) 3장

 

3.1. 빅 오 표기법: 원소가 N개일 때 몇 단계가 필요할까? 에 대한 답

1장과 2장에서는 알고리즘의 효율성을 결정하는 주된 요인이 알고리즘 수행에 필요한 단계 수임을 밝혔다.
그러나 어떤 알고리즘은 '7단계의 알고리즘' '120단계의 알고리즘'으로 표시하기엔 장황하므로 알고리즘의 시간 복잡도(효율성)를 일관되고 정량화하여 나타내기 위한 방법으로 빅 오 표기법을 사용하게 되었다.

앞에서 배운 선형 검색을 빅 오 표기법으로 표현해보자.
배열에 원소가 N개가 있을 때, 선형 검색에서 최악의 경우 배열의 원소 수만큼의 단계가 필요했다.
빅 오 표기법으로 '빅 오 N', '차수 N' , '오 N' 이라 표현한다.

O(N)

O(N)은 알고리즘에 N단계가 필요함을 표현하고, O(N)인 알고리즘을 선형 시간을 갖는 알고리즘이라고도 한다.

1장에서 살펴본 배열 읽기에 필요한 단계수는 배열의 크기와 상관없이 딱 하나이므로 O(1), '오 1'로 나타낸다.
즉, 배열에 원소가 몇 개든 배열에서 읽기는 항상 한 단계면 된다.
이러한 이유로 O(1)을 '가장 빠른' 알고리즘 유형으로 분류한다. 데이터가 늘어나도 단계 수는 증가하지 않고 N이 얼마든 항상 상수 단계만 필요하다. 그래서 O(1) 알고리즘을 상수 시간을 갖는 알고리즘이라고도 표현한다.

 

3.1.2. 분석 방법에 따른 시간 복잡도 표기법

• 최악의 경우: big-O (빅 오 표기법) : O( ) 
• 최선의 경우: big-Omega (빅 오메가 표기법) : Ω( ) 
• 평균의 경우: big-Theta (빅 세타 표기법) : Θ( )
  
  

3.2. 빅 오의 본질

ex. 데이터가 몇 개든 항상 3단계가 걸리는 알고리즘을 빅 오로 표현하면?
O(3)일 것 같지만, O(1)이다. 이유는 빅 오의 본질에 있다.

빅 오의 본질이란 빅 오가 진정으로 의미하는 것, 즉 데이터가 늘어날 때 알고리즘의 성능이 어떻게 바뀌는지를 뜻한다.
빅 오는 단순히 알고리즘에 필요한 단계 수만 알려주지 않는다. 데이터가 늘어날 때 단계 수가 어떻게 증가하는지 설명한다.
O(1), O(3)은 모두 데이터 증가에도 단계 수가 변하지 않으므로, 본질적으로 같은 알고리즘 유형이다.
반면 O(N) 알고리즘은 데이터에 비례해 단계 수가 증가하는 알고리즘 유형으로 데이터 증가가 성능에 영향을 미친다.

그럼 항상 100단계가 걸리는 상수 시간 알고리즘은 O(N)알고리즘보다 성능이 우수한 것일까?
그래프에서 보듯이 원소가 100개 이하인 데이터 셋에서는 O(1)보다 O(N)알고리즘의 단계수가 더 적다.

 

핵심은 100보다 큰 모든 배열에서는 O(N)알고리즘에 더 많은 단계가 걸린다는 것이다. 백만 단계가 걸리는 O(1) 알고리즘이 있다하더라도 데이터가 증가할수록 결국 O(N)이 O(1)보다 덜 효율적인 어떤 지점에 반드시 다다르게 되며, 이 지점부터 데이터 양이 무한대로 갈때까지 바뀌지 않는다.

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

선형 검색이 항상 O(N)은 아니다. 원하는 값을 배열 첫 번째 셀에서 찾았다면 O(1)이다. 그러나 빅 오 표기법은 일반적으로 최악의 시나리오를 의미하므로, 최선의 시나리오는 O(1)일 수 있음에도 대부분 O(N)이라 설명한다.

3.3. 세 번쨰 유형의 알고리즘: O(logN)

데이터가 커질수록 단계 수는 늘어나지만, 데이터 수보다 단계 수가 훨씬 적은 이진 검색은 빅 오로 어떻게 표현할까?
O(1)과 O(N)의 사이 어디쯤일 것이다.
빅 오는 이진 검색의 시간 복잡도를 아래와 같이 '오 로그 N'으로 표현한다.

O(logN)

이러한 유형의 알고리즘을 로그 시간의 시간 복잡도라고 한다. 간단히 말해 O(logN)은 데이터가 두 배로 증가할 때마다 한 단계씩 늘어나는 빅 오의 방법이다.

3.5. O(logN) 해석

O(logN)은 데이터 원소가 N개 있을 때, 알고리즘에 log₂N단계가 걸린다는 의미다. 만약 원소가 8개이면 log₂8=3이므로 이 알고리즘은 3단계가 걸린다. 바꿔말해 원소 8개를 절반으로 계속 나누면 원소가 하나 남을 때까지 3단계라는 것이다.
ex. 8 / 2 / 2 / 2 = 1
이진 검색이 정확이 위와 같이 동작한다. 특정 값을 찾을 때 배열의 셀을 계속해서 반으로 나누며 범위를 줄여간다.
즉, O(logN)은 원소가 하나가 될 때까지 데이터 원소를 계속해서 반으로 줄이는 만큼의 단계 수가 걸린다는 뜻이다.