효원이가 물어 봤을 때, 정확하게 몰랐었다가, 동우가 소개해준 책의 첫번재 페이지에 설명 되어 있는 것을 보고, 자세히 보게 되었다가, 정리하게 된다.

big O 표기법은, 전산학자들이 어떤 하나의 함수의 복잡도를 정의하는데 즐겨 사용하는 표기법이다. 표기는 다음 처럼 한다. O(함수); 식으로 표현 한다.

괄호안의 함수는 (n) 또는 (c) 로 표기하는데, c는 상수를 뜻한다. (즉 1, 2, 3, 4 등..)


함수의 복잡도란 무엇일까?

복잡도를 해결하기 위해서, n 번의 연산을 한다면, 그것은 n 번의 복잡도를 가졌다고 말할 수 있고, 표기하면, O(n) 으로 표기 된다. 어떤 일을 처리함에 있어, 그 처리의 복잡도를 뜻한다. 라고 해석 해도 될 듯 싶다.


예를 들자면, 내가 상자 1000개를 가지고 있는데, 이 상자들 중 한 상자에 만원이 들어 있다고 가정 했을때, 내가 이 만원을 찾기 위해선, 최대 1000개의 상자를 열어 봐야 할 것이다. 이것을 빅오(big O) 표기법으로 표현하자면, 만원을 찾는 함수는 O(n)의 복잡도를 가졌다고 볼 수 있는 것이다.


그렇다면, O(c)의 복잡도는 무슨 뜻인가?

어떠한 경우에서도 c번의 횟수만으로 일을 처리 할 수 있음을 뜻하는데, 위의 상자 1000개에서 만원을 찾는데, 무조건 2번만에 찾을 수 있다면, O(2)로 표기 될 수 있으며, O(2)의 복잡도를 가지고 있다고 말 할 수 있다.

무척 가벼운 연산임을 알 수 있을 것이다.


한가지 중요한 사실은 빅 오(Big O)는, 최악의 경우일 때, 복잡도를 나타낸다.


이렇게 복잡도를 표현함에 있어, 가장 복잡하지 않은 순으로 정렬하자면,

상수,  log₂n,  n, nlog₂n,  n²  ,n²  ,2ⁿ 순으로 정렬 할 수 있겠다.


신고
posted by 농사를 짓는 게임 프로그래머 최익필

댓글을 달아 주세요

  1. 최익필안티 2009.01.13 21:10 신고  Addr  Edit/Del  Reply

    배신자

  2. 엄효원 2009.02.11 23:27 신고  Addr  Edit/Del  Reply

    빅오 기법을 표기시 상수와 n 의 차이점이 모냐 -_-;;; 조금 설명이 어렵네 -_-a 가서 물어볼께

  3. Favicon of http://www.interoasis.net interoasis 2011.06.28 09:29 신고  Addr  Edit/Del  Reply

    안녕하세요. Big O notation에 대해 검색하다가 여기 들르게 됐습니다.
    한가지 궁금한게 있는데 위에서 들어주신 상자의 예는 상자의 개수가 1000개라는 상수로 표현됐기때문에 O(1)로 표현돼야 맞는것 아닌가요? 만약 상자의 개수가 그때 그때 달라지는 변수의 형태라면 O(N)이 되는거구요. 제가 잘못 이해하고 있는건지...

    • Favicon of http://ikpil.com 농사를 짓는 게임 프로그래머 최익필 2011.06.28 14:16 신고  Addr  Edit/Del

      예를 들어서, 100개의 상자 중 한 상자에 만원이 들어 있고, 상자에 든 만원을 찾는 특별한 방법이 없어, 모든 상자를 열어봐야 만원을 찾을 수 있을 경우, 빅 오 표기법은 O(100) 이 됩니다. 이때 상자의 갯수에 따라 표기법이 달라지므로, O(n) 이 됩니다.

      만약 특별한 방법이 있어, 한번만 상자를 열어도 찾을수 있다면, O(1) 이 됩니다. 즉, 한번 상자를 열어 보고, 만원이 있는지 확인하는 시간을 1 이라고 보는 것입니다.