한 페이지 머신러닝

[Big O notation]: 소요시간(or공간)의 상한선

[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

댓글

댓글 본문
작성자
비밀번호
  1. Woneui Hong
    ㅎㅎ 방문 감사합니다. 저는 아직 어떤 표현을 사용해야 읽는 분이 좀더 와닿는 글이 되는지를 몰라 고민하는 단계라서요.. 이렇게도 해보고 저렇게도 해보는 실험 중이랍니다.
    대화보기
    • 폭스킴
      글은 굉장히 캐주얼(?)하게 쓰셨는데 이해는 잘 되네요~^^
    버전 관리
    Woneui Hong
    현재 버전
    선택 버전
    graphittie 자세히 보기