[Big O notation]
Big O notation이라는 것은
알고리즘이 작동하는데 소요되는 시간 혹은 공간의 상한선을 의미하는 것임
근데 알고리즘(Algorithm)이란 무엇인지 를
먼저 읊어봄
Algorithm이라는 것은
작업 계획서임
요리로 치면 요리법이고
운전으로 치면 운전법이고
사람이나 기계가 뭔 일을 하든
일에는 순서가 있게 마련인데
그 순서를 꼼꼼하게 적어놓으면
그것을 알고리즘이다 라고 부름
3+4(5+1) 을 계산하려면
괄호 안에 꺼를 먼저 해갖고 3+4 * 6 을 만든 다음에
더하기보다 곱하기를 먼저 계산해야지
그래서 3+24 해놓고
더하기를 해야지
그래서 27 뙇 하는것임
순서있게 일을 했으므로 이것도 알고리즘임
그러면 순서가 없는 일도 알고리즘인가
하는 철학적인 질문이 있을 수 있는데
시간이 소요되지 않는 일은 세상에 없음
모든 일은 시간이 걸림
근데 시간이 소요된다면 거기에는 순서가 있음
그래서 순서가 없는 알고리즘은 없음
모든 일은 변화를 만드는데
변화에는 반드시 시간이 걸리기 때문임
근데 일을 할 때
우리는 이 세상에 산다는 이유로
두 가지 제약을 항상 껴안게 됨
시간적인 제약이랑
공간적인 제약임
혹은 시간적인 자원(resource)이랑
공간적인 자원(resource)라고 보아도 됨
일을 하는데
시간을 많이 쓰고 대신 공간을 덜 써도 되고
시간을 적게 쓰고 대신 공간을 많이 써도 됨
컴퓨터가 계산 을 할 때는
CPU가 계산을 하는 시간이 걸리고
계산을 메모리에 썼다 지웠다 하는 메모리 공간도 걸림
근데 메모리는 모자라면 돈으로 때울 수가 있는데
시간은 모자란다고 돈으로 때울 수가 없음
그래서 보통은 컴퓨터가 일하는 시간을 기준으로
알고리즘의 성능을 판단함
가끔은 공간 소요를 기준으로
알고리즘의 성능을 판단할 때도 있기는 있음
이번 편에서는
알고리즘의 성능 을 구분하는 문제를 다뤄봄
같은 목적의 일을 하는데
오래 걸리는 놈은 일을 못하는거고
빨리 하는 놈은 일을 잘 하는 거겠음
일을 잘 하는 놈들을 모아서 맛난 밥을 사주고
일을 못 하는 놈들을 모아서 채찍맛을 보여주자
그렇게 여러 종류의 알고리즘(작업) 들을
일잘하는 순서대로 분류를 해놓는 개념임
여기서는
그런 뻔한 개념을
어떻게 엄밀하게 정의하는가를 살펴볼 것임
엄밀하다는 것은 무엇이냐면
예외가 없다는 뜻임
예외가 있더라도 ‘예외임’ 하고 적어도 구분은 해놓음
잘 보길
f라는 것이 알고리즘 이름인데
n를 입력으로 받아서 f라는 일을 하는 놈임
그래서 f(n)라고 표기함
g라는 알고리즘 이름을 읽는데
n을 입력으로 받아서 g라는 일을 한다고 읽음
그래서 g(n)라고 표기함
성능을 평가한다 라는 것은
그러니까 어느놈이 잘했네 못했네 따지는 것은
‘비교'를 할 수가 있어야지
잘했다 못했다를 알 것이 아님
그래서 g를 보통 상식적인(잘 알려진) 일로 놓고
f를 내가 테스트 하려는 일로 두고서
같은 기계가 같은 입력을 가지고
f일도 하고 g 일도 한다고 했을 때
f는 g가 하는 일 기준으로 최대 얼마나 걸림?
이라는 말에 대답하는 것으로
g보다 느린놈 빠른놈 으로 분류가 나눠지는 것임
어려운 일을 할 수록 시간이 오래 걸리겠지
그래서 여러가지 일을
그게 얼마나 어려운지 하는 등급으로 나누는 방법도 됨
g(n)는 보통
g(n) = log(n) 이런 로그 식으로 보든가
g(n) = n, n^2, n^3, … 이런 다항식으로 보든가
g(n) = 2^n 이런 지수 식으로 보는데
그래서
f(n) = O(n) 이라는 말을 읽어보면
f는 n이라는 입력을 받으면 최대 n만큼의 시간이 걸려서 일을 끝냄 (더 빨리 끝낼수도 있지만 ‘최대’가 그렇다는 말임)
f(n) = O(n^2) 이라는 말을 읽어보면
f는 n이라는 입력을 받으면 최대 n^2만큼의 시간이 걸려서 일을 끝냄 (더 빨리 끝낼수도 있지만 ‘최대’가 그렇다는 말임)
f(n) = O(2^n) 이라는 말을 읽어보면
f는 n이라는 입력을 받으면 최대 2^n만큼의 시간이 걸려서 일을 끝냄 (더 빨리 끝낼수도 있지만 ‘최대’가 그렇다는 말임)
그림에서는 f(n)와 O(1) 사이에
삼지창 오른쪽으로 뉘여놓은거 같은 기호를
사용했는데
저것은 f(n)이 O(1)이라는 집합의 원소 라는 뜻임
f(n) = O(1)
이 표기는 사실은 약간 어폐가 있는 것이고
관용적으로 많이 사용하는 표현임
원래는 f(n)이 O(1)성능 집단 클래스 안에
들어가는 원소 라고 보는 것임
n은 입력의 크기 이고
같은 n에 대해서라면
log(n) < n^2 < 2^n 임
Big O notation이라는 것은
알고리즘이 작동하는 시간 혹은 공간의 상한선을 의미하는 것 이라고 했음
‘더 빨리 끝낼수도 있지만 ‘최대’가 그렇다는 말임’
이것을 수학적으로는
그림 아래의 흰색 띠 안에 들어있는 말처럼 표현함
[(f(x) = O(g(x)))]
f(x)는 O(g(x))라는 집합의 원소인데
[as]
언제 그렇냐면
[there exists c>0 and x_0]
0보다 큰 c라는 상수와 x_0 라는 지점이 존재할때인데
[such that]
그게 어떤 지점이냐면
[f(x) <= cg(x) whenever x>= x_0]
x_0보다 큰 모든 입력에 대해서
f(x)라는 알고리즘이 답을 내는데 걸리는 시간이
g(x)라는 알고리즘이 답을 내는데 걸리는 시간의 상수배(=2배, 3배, 4배, …)
보다 작으면
그럴 때
f(x)는 O(g(x))라는 집합의 원소이다
라는 것임
대충보면 이게 뭔 말? 하는 것인데
매우 세심하게 살피어 보길
그러면 말이 된다는 것을 알 수가 있음
한두가지 유의할 점이 있는데
여기서 말하는 ‘시간’ 이라는 것은
상식적인 의미에서의 시계 째깍째깍 하는 그런 시간이 아니고
컴퓨터가 연산 하나를 처리할 때를 1단위가 지난 것으로 함
사람의 세월은 단위가 초, 분, 시간 그런 것인데
컴퓨터한테는 세월이라는 개념이 없을 것이기 때문임
또 하나 유의할 것은 뭐냐면
Big O notation을 사용할 때는
‘일하는데 사용하는 시간의 상한선이 같은 알고리즘의 집단’을 의미하기 때문에
정확한 값, 소소한 값을 일일이 지칭하는 것이 의미가 없음
가령
O(7n+3+3)은 O(n)과 같은 클래스임
그러므로 퉁쳐서 O(n)만 사용함
O(n^3+7n+3+3)은 O(n^3)과 같은 클래스임
왜냐면 n의 3제곱이라는 것이 7n이라는 것보다 훨 크고
그래서 계산이 가장 오래 걸리기 때문에
상한선을 지칭하는 의미로 사용하는
Big O notation에서는
어떤 항보다 작은게 뻔한 항들은 개무시를 함
그러므로 퉁쳐서 O(n^3)만 사용함
오늘의 문서는 이것을 참고로 하였음
https://en.wikipedia.org/wiki/Big_O_notation
