자료구조에서 빅오 (Big O)란 무엇인가요
- zoojjang
- 2005.04.01 10:50
- 답변
- 3
- 조회
- 8,023
자료구조에서 빅오 (Big O) 표기법이 무엇인가요
좀 자세히 설명좀 부탁드려요.
- 신고
질문자 채택된 경우, 추가 답변 등록이 불가합니다.
질문자 인사
<<>>
for (int i = 0; i < n; i++)
{
명령...
}
이런 문장은 n번 수행을 하기 때문에 O(n)입니다. i < 2n도 마찬가지로 1차이므로 O(n)입니다.
------------------------------------
for (int i = 0; i < n; i++)
{
for (int k = 0; k < n; k++)
{
명령...
}
}
이 문장은 O(n^2)입니다. 즉 n의 제곱에 비례해서 명령이 반복되게 되는 거죠.
버블소트를 구현하면 두번째와 같은 명령어 구조를 띠기 때문에 버블소트의 계산복잡도는 O(n^2)이 되는 겁니다.
머 리쓰는 게임 중에 특수한 마방진(5 X 5)이 있다고 합시다. 어떤 사람은 25개의 수열이 모두 들어가는 경우(25!)를 감안하여 풀도록 프로그램하였다면 이것은 O(n!)이 되는 겁니다. 그에 반해 어떤 사람은 특수한 요령을 알아내서 5개씩 묶어서 5번 안에 해결되게 프로그램을 구현한다면 O(n^2)이 되는 겁니다.
즉 길이가 n인 프로그램에서 명령을 수행할 때 n에 얼마나 비례하여 명령이 수행되는가가 계산복잡도입니다.
- 지식/in icarte 님의 답변내용
질문자 인사
<<>>
출력하는 프로그램입니다. 그렇다면 이 프로그램의 라이프사이클중 가장
많은 부분을 차지하는 것이 n번의 for문 일 것입니다.
즉, 프로그램의 실행속도에 가장 지대한 영향을 끼치는 부분은 n회 for문!
어떻게 해도 프로그램의 실행속도는 최대 n번을 넘지 못합니다.
n번을 넘기는 컴퓨터가 있다면 미친 컴퓨터이거나 고장난 컴퓨터겠지요~! ^^;
이렇듯 빅오는 다음과 같이 해석하시면 쉽습니다.
O(n) : 최악의 경우 n번까지 돌면 프로그램은 끝낼 수 있다!
즉 힘껏 돌려봐야 최대 n번이면 끝낼 수 있다는 뜻이지요.
O(1), O(log n), O(n^2), .... 등등 다 마찬가지입니다. 그 이상은 안 넘긴다는
말입니다.
예를 들어.... 어떤 코드를 가중치에따라 측정해보니 "2n^3 + 4n + 7" 이렇게
나왔고, 이 것의 최대 한계 값인 O()를 알아보라고 했습니다.
보아하니 n^3이 있네요! 삼중루프가 있었나 봅니다. 그렇다면 4n이고 7이고
다 필요없지요~! 프로그램의 실행속도에 가장 많은 영향을 끼치는 것은 n^3
입니다. 따라서 위 식의 Big O는 O(n^3)이라고 말할 수 있는 것입니다.
n이 각각 10 정도면 그저그렇겠지만... 만약 1000번 정도만 된다고 생각하면
삼중루프일때... 약 1000000000! 헉! 1억번을 실행해야 하죠! 물론 중간에
끝날 수도 있지만, 최악의 경우에는 1억번을 돌고돌아야 합니다...
시간이 많이 걸리겠지요... 실제 상용프로그램이 이렇게 돌아간다면 사람들
분명 짜증날겁니다. 또 이 프로그램 안쓰겠지요... ^^; 누가 쓰겠습니까? ㅎㅎ
그래서 알고리즘의 개선은 중요합니다. 빅오는 이런 알고리즘을 개선하기 위한
척도를 제공해 주는 것입니다. 빅오 이외에 몇가지 더 있죠? 그 것들도 마찬가지
입니다.
두서없이 적었습니다... 어떻게 이해가 되시는지요? ^^
| notation은 단어 의미대로 '표기법' 이라고 생각하시면 됩니다. 그러니까
Big-O notation 은 '대문자 O 표기법' Omega 는 'Ω 표기법', (Big-omega 라고 하기도 합니다) Theta는 'Θ 표기법' (역시 Big-Theta라고 합니다)
이라고 생각하시면 됩니다.
수업을 들으셨다니 O(n), O(log n) 같은 것들을 이미 보셨으리라 생각합니다. O 대신에 Ω나 Θ가 있을 수도 있죠. 이것들이 바로 그 notation들입니다.
세 가지 다 님께서 말씀하신 '알고리즘 효율'을 함수가 얼마나 빠르게 증가하는가를 나타내는 것으로 설명할 때 쓰입니다.
예를 들어 T(n) = 2n^2 + 5n + 6 이라는 함수가 있다고 합시다. n이 점점 커진다면, 5n이나 6에 비해 2n^2 가 더욱 큰 비율로 늘어나고, 결국 n이 증가할 때 T(n)이 얼마나 빠른 속도로 증가하느냐는 것을 결정하는 것은 n^2입니다. 그렇기 때문에, 이 T(n)의 효율성을 Big-O notation으로 표현할 때
O(n^2) 라고 씁니다.
컴퓨터 프로그래밍으로 생각을 해 보겠습니다. n개의 숫자가 있는 정렬되지 않은 배열이 있고, 이 중에 가장 큰 숫자를 찾는 배열을 찾는 함수를 만든다고 생각해봅시다. 정렬이 되지 않았으므로 n개의 숫자를 일일이 체크해야하겠죠? 그렇다면 이 함수의 효율성은 그 숫자 n에 의해 좌우가 되므로 (10개면 10번을 체크해야하고, 20개이면 20번을 체크해야하죠) 이 함수의 효율은 O(n)이 됩니다.
반대로 정렬이 되어있는 배열에서 제일 큰 숫자를 찾는다고 합시다. 그럼 숫자가 몇 개든 상관없이 맨 뒤에 있는 숫자를 보면 되겠죠. n=10이든 n=20이든 걸리는 시간은 똑같습니다(constant). 이럴 땐 O(n)이 아니고 O(1)이겠죠.
이런 식으로 아래와 같은 Big-O notation들이 존재합니다. 보통 정렬할 때 걸리는 시간이라던가, 검색할 때 걸리는 시간등을 나타낼 때 가장 많이 나옵니다.
Big-O notation 은 알고리즘이 얼마나 오랜 시간이 걸릴지 측정하는 데 도움이 되며, 또 같은 분류에 속하는 알고리즘들은 대충 비슷한 시간이 걸릴 것이라는 암시도 해 줍니다.
Big-O, Big-Omega, 그리고 Big-Theta의 미묘한 차이에 대해 서술하려면 수학적인 정의를 내려야합니다. (위에선 쉽게 설명했는데, 정확한 정의를 내리면 조금 복잡해집니다)
1. Big-O Notation 정수 (integers) 또는 복소수(real numbers)를 복소수로 변환하는 함수 f, g가 있다. 만약 |f(x)| ≤ C|g(x)|, x > k 를 만족시키는 상수 C와 k가 존재할 때, f(x)는 O(g(x)) 라고 한다.
2. Big-Omega Notation 정수 (integers) 또는 복소수(real numbers)를 복소수로 변환하는 함수 f, g가 있다. 만약 |f(x)| ≥ C|g(x)|, x > k 를 만족시키는 상수 C > 0와 k가 있을 때, f(x)는 Ω(g(x)) 라고 한다.
3. Big-Theta Notation 위와 같은 상황에서 f(x) 가 동시에 O(g(x)) 이고 Ω(g(x)) 일 때 f(x)는 Θ(g(x)) 라고 한다.
다시 말하면, Big-O Notation은 upper-bound, 즉 x가 증가할 수록 f(x) 보다 항상 스케일이 큰 g(x)를 찾는 것이고, Big-Omega Notation은 x가 증가할 수록 f(x)보다 항상 스케일이 작은 g(x)를 찾는 것이죠.
예를 들어보겠습니다.
f(x) = 8x^3 + 5x^2 + 7 이라고 합시다.
이것을 O(x^2) 라고 할 수 있을까요? 아닙니다. C가 아무리 크다고 해도, x가 무한으로 커지면 8x^3이 Cx^2 보다 커질 수 있기 때문이죠. 하지만 이것을 Ω(x^2) 라고 할 수 있을까요? 예, 그렇습니다. 바로 위와 같은 이유로, x가 무한으로 커지면 C가 아무리 커도 Cx^2보다 커질 수가 있기 때문이죠. 하지만 O(x^2)는 아니기 때문에 Θ(x^2)라고는 말할 수 없습니다.
그럼 x^3은 어떨까요? 잘 보시면 O(x^3)는 C가 8보다 큰 경우 성립하먀, Ω(x^3)는 C가 8과 같거나 작은 경우 성립한다는 것을 아실 수 있습니다. 그러므로 Θ(x^3)이라고도 할 수 있습니다.
쉽게 설명하자면, x^3을 주체(?)로 하는 함수가 f(x)의 아래와 위를 막고 있다는 얘기지요. 그러므로 x^3이 이 함수의 특성을 설명하기엔 적합한 겁니다.
이런 이유로, 알고리즘이나 함수, 또는 프로그램의 효율을 나타낼때는 Θ(Big-Theta)를 사용하는 것이 가장 강력한 힘(?)을 가지고 있다고 볼 수 있습니다.
조금 복잡한 설명이 되었지만 이 중 한 마디라도 도움이 되었으면 좋겠습니다. 덕분에 저도 복습할 기회가 되었군요. 그럼.... |
