15_빅오

2019-10-14 이민예

Big-O 란 무엇일까?

이사님이 나에게 일을 시켰다. 언제까지 해주실수 있으시냐고 묻는다. 이때 나는 최대의 기간을 이야기 한다. 아 이사님, 다음주 화요일까지는 완료될 것입니다. 평균적인 것도 아니고, 가장 빨리 끝날 때도 아니다. 이런 저런 예기치 못한 상황이 발생했을 때를 다 고려해서 적어도 이 정도 안에 끝날 것이라고 말씀드린다. 즉, 나는 최악의 상황을 말씀드린 것이다.

빅오는 최악의 경우를 산정하여 말하는 것이다. 우리가 만든 알고리즘이 최소한 이것을 넘지 않아요 라고 주장하는 것이다.

빅오의 유래

빅오가 처음 나오게 된 배경은 2009년 미국의 한 시골이다. 미국은 그 당시에도 인터넷이 매우 느리어서, 인터넷이 빠를까, 비둘기가 빠를까? 실험을 했다.

허걱쓰!! 비둘기가 인터넷보다 빨랐다. 만약에 비둘기가 들고가야할 데이터의 양이 많을때에도 비둘기가 빠를까? 그때도 비둘기는 들고가야하는 짐에 상관없이 일정한 시간으로 전달하였다. 즉 비둘기의 시간복잡도는 O(1) 이다. 반면에 인터넷은 데이터의 양이 늘어날때마다, 속도도 O(N) 으로 느려졌다.

데이터가 많아질수록, 시간이 기하급수적으로 늘어나는 것이 피하는 것이 좋다

빅오의 정의

함수 f(n) 과 g(n) 의 자연수를 양의 실수로 대응시키는 함수라고 할 때, 다음을 만족시키는 양의 상수 c>0 와 정수 $n_0$ ≥1 이 존재하면 "f(n) is O(g(n))" 혹은 "f(n)∈O(g(n))" 이라고 쓰고, "f(n) is big-Oh of g(n)" 혹은 "f(n)is order of g(n)"으로 읽는다.
$f(n)≤cg(n)$ for $n≥n0$

$f ( n ) = a_0 + a_1 n + ⋯ + a_d n ^d ( a_ d > 0 )$ 에 대하여,

$a_ 0 + a_ 1 n + a_ 2 n^ 2 + ⋯ + a_ d n^ d ≤ ( | a_ 0 | + | a_ 1 | + | a_ 2 | + ⋯ + | a_ n | ) n^ d$

함수 f(n)의 빅오는 $O(n^d)$

$O(n)$ $O(n^2)$ 둘 중에 무엇이 더 빠를까?

위 함수들의 증가속도는 n→∞ 인 상황 (Asymptotic Analysis) 에서 비교하는 것이 맞다고 할 수 있다.

빠르면 2.5일에 끝나고 보통 3일에 끝나는 Task를 보고할때,

Big O

Big Omega

Big Theta

최악의 경우

최선의 경우

근접한 한계 성능 표시

늦어도 1주 안에 끝나요

빠르면 2.5일 안에 끝나요

2.5일에서 3.5일 안에 끝나요

Big Omega 정의

함수 f(n) 과 g(n) 의 자연수를 양의 실수로 대응시키는 함수라고 할 때, 다음을 만족시키는 양의 상수 c>0 와 정수 $n_0$ ≥1 이 존재하면 "f(n) is Ω(g(n))" 이라고 쓰고, "f(n) is big-Omega of g(n)" 으로 읽는다.
$f(n)≥cg(n), for n≥ n_0$

Big Theta 정의

함수 f(n) 과 g(n) 의 자연수를 양의 실수로 대응시키는 함수라고 할 때, 다음을 만족시키는 양의 상수 c′>0,c′′>0 와 정수 $n_0$ ≥1이 존재하면 "f(n) is Θ(g(n))" 이라고 쓰고, "f(n) is big-Theta of g(n)" 으로 읽는다.
$c′g(n) ≤f(n) ≤c′′g(n), for n≥n_0$