[알고리즘/Algorithm]Big O notation, 점근 표기법_하

안녕하세요. Air-8입니다. 상편에 이어서 성능분석에 따른 빅오 표기법을 바로 진행하겠습니다.

아래 그림은 순서대로 O(1), O(logn), O(n), O(nlogn), O(n^2)입니다. 참고로 logn의 밑은 크게 중요하지 않습니다.

여기 시간복잡도 5개가 흔히 나오는 경우입니다. n^2까지만해도 그럴 수 있다고 봅니다. 같은 알고리즘이라고 가정할 때 보여지는 시간 복잡도는 그래프만 봐도 확연히 차이가 납니다. 그럼 이제부터 다시 고쳐야 하는 수준의 시간복잡도를 알려드리겠습니다.

순서대로 O(n^3), O(n^k), O(2^n), O(n!)-팩토리얼형 입니다. n^3까지만 가급 고쳤으면 좋겠는 수준이고 n^k나 2^n은 뭔가 잘못됐음을 직감해야됩니다. 심지어 팩토리얼형까지 나온다면 연산수는 말할 필요도 없을만큼 늘어납니다.

빅오메가 표기법과 빅세타 표기법을 말씀드리겠습니다.

오메가는 점근적 하한선을 표기하기 위해서 사용하는 것입니다.(세타와 다르게 아래가 비어있는 모양이죠)

세타 표기법은 점근적 상한선과 하한성을 정해주는 것입니다.

여기서 많은 분들이 쉬운 얘기에 혼란을 겪었습니다. 빅오메가/세타 표기법은 빅오의 옵션이라던가 빅오와 같이 존재하는 그런 걸로 생각하기 때문입니다. 아닙니다. 빅 오메가/빅 세타/빅 오는 같이 공존하지 않습니다.

빅 오 표기법을 점근적 표기법이라고 해석한 이유를 보면 정말 정확한 해석이라고 봅니다.

점근적, 이런 양상을 띌 것이다. 막연한 느낌으로 해석되는 것이죠. 그래서 빅 오는 최악의 퍼포먼스를 뜻합니다.

빅 오메가는 최선의 퍼포먼스를 뜻하고, 빅 세타는 최악의 퍼포먼스와 최선의 퍼포먼스 사이에 있다고 하는 것입니다.

이를 수학적으로 다시 얘기를 하겠습니다.

 

알고리즘 성능 분석의 수학적 표기 [빅 오 표기법] - 퍼포먼스 상한선 지정 두 개의 함수 𝑓(𝑛) 과 𝑔(𝑛) 이 주어졌을 때, 모든 𝑛 > 𝑛0 에 대하여 |𝑓(𝑛)| ≤ 𝑐 * |𝑔(𝑛)| 을 만족하는 2개의 상수 𝑐 와 𝑛0 가 존재하면 𝑓(𝑛) = 𝑂(𝑔(𝑛)) 이다.   |𝑓(𝑛)| ≤ 𝑐 * |𝑔(𝑛)| 이 부분이 무엇이냐면 𝑓(𝑛) = 2𝑛+4라고 한다면 𝑔(𝑛) = 𝑛입니다. 거기다 임의의 상수 𝑐를 10으로 설정하면, 2𝑛+4 ≤ 10 * 𝑛 입니다. 10 * 𝑛이 늘 크니까 조건은 성립합니다. 그러기에 𝑓(𝑛) = 𝑂(𝑔(𝑛)) 즉, 𝑐 * |𝑔(𝑛)| 이 𝑓(𝑛)이 낼 수 있는 최악의 범위까지 상한을 그어줌으로 빅 오 표기법입니다.   [빅 오메가 표기법] - 퍼포먼스 하한선 지정 주어진 두 함수는 같으나 이번에는 하한을 지정하는 것입니다. |𝑓(𝑛)| ≥ 𝑐 * |𝑔(𝑛)|,  𝑓(𝑛) = 2𝑛+4라고 한다면 𝑔(𝑛) = 𝑛입니다. 여기서 임의의 상수 𝑐를 조금 단적으로 0.001을 주겠습니다. 2𝑛+4 ≥ 0.00𝑛 입니다. 퍼포먼스의 가장 빠른 순간을 지정하는 것이다보니 적당한 상수를 넣어도 되지만 이렇게 보시는 것처럼 빅 오메가는 크게 의미가 없게 만들 수도 있습니다.   [빅 세타 표기법] - 퍼포먼스 상/하한 지정(평균) 상/하한이기 때문에 이번에는 상수가 c1, c2 두 개가 존재합니다. 𝑐1 * |𝑔(𝑛)| ≤ |𝑓(𝑛)| ≤ 𝑐2 * |𝑔(𝑛)|이죠 마찬가지로 c1은 0.001, c2는 10으로 설정하면 𝑐1 * |𝑔(𝑛)|은 앞에서 설명한 빅 오메가와 같고 𝑐2 * |𝑔(𝑛)| 또한 빅 오와 같습니다.   결국 빅 오/오메가/세타에서 바뀌지 않던 것은 𝑔(𝑛)입니다. 표기법의 규칙대로 제일 차수가 큰 항만 남기고 거기서 계수를 제거한 것이 𝑔(𝑛)입니다. 𝑓(𝑛) = 2𝑛^3 + 3𝑛^2 + 4𝑛 + 100이라는 함수에서 𝑔(𝑛) = 𝑛^3입니다. 이 것을 빅 오/오메가/세타 방식으로 표현하면, 𝑂(𝑔(𝑛)), Ω(𝑔(𝑛)), Θ(𝑔(𝑛)) -> 𝑂(𝑛^3), Ω(𝑛^3), Θ(𝑛^3)입니다.   결국 표기법은 𝑐라는 상수와 𝑛이라는 입력값으로 만들어지는 타임 복잡도를 분석한 것이지 아주 섬세한 틀에 갇혀있는 것이 아닙니다.

 

끝