알고리즘의 효율성을 결정하는 주된 요인은 알고리즘 수행에 필요한 단계 수이다.
하지만, 단순히 어떤 알고리즘을 22단계의 알고리즘, 또 400단계의 알고리즘이라 표시할 수 없다.
알고리즘에 필요한 단계 수를 하나의 수로 못 박을 수 없기 때문이다.
예를 들어, 선형 검색의 경우 배열의 원소 수가 20개라면 20단계의 선형 검색이 필요하다.
물론 400개의 원소를 가진 배열의 선형 검색은 400단계가 필요하다.
이처럼 같은 선형 검색임에도 불구하고 원소 수에 따라 단계 수가 다르다.
위와 같은 선형 검색을 20단계의 선형검색, 400단계의 선형 검색으로 부를 순 없다.
좀 더 정형화하는 효과적인 방법으로 표현하기 위해 빅 오 표기법이 등장한다.
빅 오 표기법
컴퓨터 과학자는 서로 간에 시간 복잡도를 쉽게 소통할 목적으로 자료 구조와 알고리즘의 효율성을 간결하고 일관된 언어로 설명하기 위해 수학적 개념을 차용한다.
이러한 개념을 형식화한 표현을 빅 오 표기법이라 부르며, 빅 오 표기법을 통해 알고리즘의 효율성을 쉽게 분류하고 이해시킬 수 있다.
빅 오의 본질
빅 오의 본질이란 빅 오가 진정으로 의미하는 것, 즉 데이터가 늘어날 때 알고리즘의 성능이 어떻게 바뀌는가를 뜻한다.
배열에 N개의 원소가 있을 경우 N단계가 필요
빅오 표기법은 위 같은 경우를 O(N)으로 표현한다.
O(N)은 "빅 오 N" 또는 "차수 N" 이라고 부른다.
선형 검색을 예로 들자면, 배열의 원소가 N개 일 때, 선형 검색은 몇 단계가 필요할까?
선형 검색은 N단계가 필요하므로 O(N)이라고 표현한다.
- O(N)인 알고리즘을 선형 시간(Linear time)을 갖는 알고리즘이라고도 부른다.
데이터 갯수와 상관없이 정해진 단계가 필요
빅오 표기법은 위 같은 경우를 O(1)으로 표현한다.
데이터가 몇 개이든 항상 3단계가 걸리는 알고리즘이라고 가정했을 때, 원소가 N개이면 항상 3단계가 필요하다.
그래서 O(3)이라고 생각할 수 있지만, 위 내용 중 빅 오의 본질을 이해하면 빅 오는 단순히 알고리즘에 필요한 단계 수만 알려주기 보다는 데이터가 늘어날 때 단계 수가 어떻게 증가하는 지 설명한다.
즉, 데이터의 갯수와 상관없이 정해진 단계만큼만 걸리는 알고리즘의 경우 O(1)로 표현한다.
그러므로 O(1)의 알고리즘을 "가장 빠른 알고리즘" 유형으로 분류한다.
- O(1)인 알고리즘을 상수 시간(constant time)을 갖는 알고리즘이라고 부른다.
그렇다면 정말 O(N)인 알고리즘보다 O(1)인 알고리즘이 빠를까?
데이터 수와 상관없이 100단계를 거치는 O(1)알고리즘과 O(N) 알고리즘을 선형 검색으로 비교해보자.
위 그림처럼 데이터 원소가 100개 미만인 O(N)알고리즘은 O(1) 알고리즘보다 빠르다.
또 O(N)알고리즘에서 데이터 원소 수가 많더라도 1 ~ 2 번의 검색만에 검색 값을 찾을 경우 O(N)이 100단계를 거치는 O(1)보다 빠를 수 있다.
하지만 빅 오 표기법은 별도로 명시하지 않는 한 최악의 시나리오를 기준으로 표현한다.
O(N)인 선형 검색을 기준으로 비교해보면 최선의 시나리오일 경우 O(1), 최악의 시나리오의 경우 O(N)이라 할 수 있다.
이렇게 최악의 시나리오를 기준으로 하기 때문에, 빅 오 표기법에서 O(1)이 O(N)보다 효율적인 알고리즘으로 분류한다.
데이터가 두 밸 증가할 때마다 +1 단계가 필요한 경우
이 경우는 O(logN) "오 로그 N"이라고 읽는다.
이러한 유형의 알고리즘을 로그 시간의 시간 복잡도라고도 말한다.
이진 검색을 예로 들자면, 이진 검색의 경우 데이터가 늘어남에 따라 단계 수가 늘어나지만 데이터 갯수보다 단계 수가 훨씬 적으므로 O(N)이라고 표현하기도 애매하다.
ex) 100개의 원소일 경우 이진 검색은 최대 7단계만 걸린다.
이진 검색의 경우 O(1)과 O(N)사이 어딘가에 있다.
이진 검색의 경우 O(logN)으로 표현한다.
간단히 말해 O(logN)은 데이터가 두 배로 증가할 때마다 한 단계씩 늘어나는 알고리즘을 설명하는 빅 오의 방법이다.
이 같은 알고리즘을 왜 O(logN)로 표현하는지 이해하려면 먼저 로가리즘(logarithm)을 알아야한다.
:https://velog.io/@yjw8459/%EB%A1%9C%EA%B0%80%EB%A6%AC%EC%A6%98
위 세 종류의 알고리즘을 비교해보자면,
- O(1)은 완벽한 수평선을 그린다.
- O(logN)은 아주 조금씩 증가하는 곡선을 그린다.
- O(N)의 경우는 완벽한 대각선을 그린다.
세 종류의 알고리즘을 가장 효율적인 순서대로 정렬하면
1. O(1)
2. O(logN)
3. O(N)
위와 같이 정렬할 수 있다.
O(logN)의 해석
로가리즘을 접목해서 빅 오 표기법을 다시 논해보자면, 컴퓨터 과학에서 O(logN)은
을 줄여서 부르는 말이다.
빅 오 표기법에서는 편의를 위해서 첨자 2를 생략한다.
