누구나 자료구조와 알고리즘 - (3) 빅 오 표기법

 

 

 

 

 

어떤 알고리즘을 "22단계의 알고리즘", "400단계의 알고리즘"이라고 표시할 수는 없다. 선형 검색의 효율성을 정량화하는 보다 효과적인 방법은 배열에 N개의 원소가 있을 때 선형 검색에 N단계가 필요하다고 표현하는 것이다. 그래서 수학적 개념을 차용하여 이러한 개념을 형식화한 표현을 빅 오 표기법이라 부른다. 이 표기법을 사용하여 주어진 알고리즘의 효율성을 쉽게 분류하고 이해시킬 수 있다.

 

선형 검색에는 배열의 원소 수만큼의 단계가 필요하다.

O(N)

• "빅 오 N"이라고 발음하며 "차수 N"이라고도 부른다.
• "알고리즘에 N단계가 필요하다"라는 뜻이다.
• 이 O(N)인 알고리즘을 선형 시간을 갖는 알고리즘이라고도 부른다.
• N이 얼마든 항상 상수 단계만 필요하기떄문에 상수 시간(constant time)을 갖는 알고리즘이라고도 표현한다.

 

그렇다면 항상 3단계가 걸리는 알고리즘을 O(3)으로 표현할까? 아니다. 실제로는 O(1)이다.

빅 오의 본질이란 빅오가 진정으로 의미하는 것, 데이터가 늘어날 떄 알고리즘의 성능이 어떻게 바뀌는지를 뜻한다. 빅 오는 단순히 알고리즘에 필요한 단계수만 알려주는게 아니라 데이터가 늘어날 때 단계수가 어떻게 증가하는지 설명한다.

• 데이터가 얼마나 많든 상관없이 단계 수가 일정하다 = O(1)
• 데이터가 많아질수록 단계 수가 늘어난다 = O(N)

 

이진 검색은 O(1)이라 표현할 수 없다. 또한, 검색하고 있는 원소 수보다 단계 수가 훨씬 적으므로 O(N)도 아니다. 빅 오는 이러한 시간복잡도를 이렇게 표현한다.

O(logN)

• "빅 오 로그 N"이라고 발음한다. 데이터가 두 배로 증가할 때 마다 한 단계씩 늘어나는 알고리즘을 설명한다.
• 가장 효율적인 순서대로 정렬하면 O(1) > O(logN) > O(N)이다.

 

이진 검색같은 알고리즘을 O(logN)이라고 표현하는 이유가 있다. log는 로가리즘의 줄임말이다.

log₂로 표현해야하지만 "₂"를 생략한다.

• O(log8) = O(3)
• O(log16) = O(4)
• O(log32) = O(5)
• O(log64) = O(6)

 

---

출처

제이 웹그로우, 누구나 자료구조와 알고리즘 (길벗, 2021)

 

 

 

 

---

개인적으로 공부한 내용을 정리하는 블로그로
잘못된 개념을 게시하지않도록 주의하고 있으나 오류가 있을 수 있습니다.