알고리즘이 얼마나 효율적인가, 얼마나 잘 설계 되었는가를 말할 때 실행 시간, 시간복잡도(Big - O, Big - Ω)에 대해 말한다.

시간복잡도는 마치 어린아이한테 저번에 봤던 곰인형의 크기가 얼마만큼 컸는지 물었을 때 "이~~만했다." 라고 손으로 은유적으로 그리고 직관적으로 표현함과 같다.

그림의 n과 n/2는 무한대의 case에서는 결국 의미가 없다. 따라서 두 경우 다 O(n)이다. 시간을 손짓과 같이 대략적으로 표현했다고 설명한 부분이 이해가 가는가? (Big O의 O는 'on the order of' 라고 한다.)

Big O

Big O는 알고리즘 실행 시간의 상한, 즉 최악의 경우(worst)를 뜻한다. 예를 들어

1, 2, 7, 1, 9

위의 행렬이 있다고 생각해보자 9를 선형 검색(linear search)로 찾고싶다면 행렬을 5번 모두 검사해야 할 것이다. 즉, O(n)이다. 빠르면 빠를수록 O(n)의 n대신 더 작은 수가 들어갈 것이고 느리면 느릴수록 n대신 더 큰 수가 들어갈 것이다.

Big Ω

Big Ω는 알고리즘 실행 시간의 하한,즉 최고의 경우(best)를 뜻한다. 다시 아까의 예를 보자

1, 2, 7, 1, 9

위의 행렬에서 1을 선형검색으로 찾고 싶으면 웬일인가 1번만에 찾을 수 있을 것이다. 즉, Ω(1)이다.

누가 더 중요한지?

아마도 Big O,Big Ω 둘 다 사용하기에는 귀찮을 것이고 직관성도 떨어질 것이다. 그렇다면 누가 더 중요할까? 경우에 따라 다르겠지만 Big O 일 것이다. Big Ω의 예시처럼 정말 운이 좋은 경우 한번에 맞출 수 있었는데 이게 좋은 알고리즘을 뜻할 수 있을까? 그건 아닐 것이다.

위의 정리는 cs50의 week4 알고리즘을 정리한 자료이다.