(알고리즘) Big-O, 시간복잡도와 공간 복잡도

알고리즘의 시간과 공간을 측정할 때는 시간복잡도와 공간 복잡도라는 말을 많이 쓴다.

 

 

그런데 시간 복잡도는 무엇이며, 공간 복잡도는 무엇일까?

 

 

시간 복잡도는 '어떤 일을 수행할 때, 그 일이 완료되기까지 걸리는 시간이 얼마나 복잡한가' 라고 생각하면 편하다.

 

공간 복잡도는 '어떤 일을 수행할 때, 그 일이 완료되기까지 필요한 공간(메모리)가 얼마다 되는가' 라고 생각하면 된다.

 

 

복잡도의 개념에 대해 알았으면, 이를 표기할 방법이 필요하다.

 

얼마나 복잡한지를 어떻게 표현할 것인가?

 

(하늘만큼 땅만큼 복잡해요)

 

이때 Big-O의 개념이 등장한다.

 

🧐Big-O만 있는게 아니다?

---

많은 사람들이 시간 복잡도라고 하면 Big-O를 떠올릴 것이다.

 

하지만 시간복잡도와 공간복잡도를 나타내는 방법에서는 Big-O만 존재하지 않는다.

 

Big-O외에도 Big-Θ(빅 세타), Big-Ω(빅 오메가) 가 있다.

 

 

먼저 기준이 되는 Big-O는 시간의 상한을 나타낸다. 시간의 상한이 뭐냐? 

 

예를 들어 시간복잡도가 O(n)인 알고리즘이 있다면, 이 알고리즘의 속도는 O(n)이하의 시간을 보장한다는 것이다. 

그렇기 때문에 O(n)을 O(n^2), O(N^3)으로 표기하는 것도 옳은 표현이다.

 

Big-Ω(빅 오메가)는 학계에서 등가 개념 혹은 하한을 나타낸다. 이게 무슨 말인가? 만약 시간복잡도가 Ω(N)인 알고리즘이 있다면, 이 알고리즘의 시간은   Ω(N)보다 빠를 수 없다는 것을 의미한다. 

 

Big-θ는 오메가와 O를 동시에 의미한다. 빅 오메가에서도 Ω(N)이고,  O(n)이라면 θ(N)이라고 표현한다.

 

 

🧐최악, 최선, 평균?

---

알고리즘 수행 시간에는 최악의 경우, 최선의 경우, 평균적인 경우가 있다.

 

가장 흔히 볼 수 있는 퀵정렬을 예로 들자면

 

퀵 정렬이 최선의 수행시간을 보여줄 때는, 배열의 원소가 모두 동일한 경우이다. 

퀵 정렬은 자신보다 작은 원소를 왼쪽, 큰 원소를 오른쪽으로 보내는데, 모든 원소가 동일하기 때문에 한번 순회하고 끝날 것이다.

 

이때의 시간 복잡도는 배열의 길이가 N이라면 O(N)이 된다.

 

그럼 최악의 경우는 어떨까? 

최악의 경우는 배열에서 가장 큰 원소가 pivot이 되는 경우이다. 이럴 경우 시간 복잡도는 O(n^2)이 된다.

 

 

평균적인 경우는?  평균의 경우 퀵 정렬은 O(nlogN)을 보장한다.

 

이렇게 알고리즘 수행 시간에는 최선, 최악, 평균 이라는 개념이 있다.

 

혼돈하지 말아야할 것이  Big-O, Big-Θ(빅 세타), Big-Ω(빅 오메가) 와는 특별한 관련성이 없다.

 

 

최악, 최선, 평균은 수행 시간이고, 빅오, 빅세타, 빅오메가는 그 시간을 표기한 방법이니 말이다.