#2 시간복잡도(좋은 알고리즘?) / 최악의 경우는 Big-O

- 이전 글에서 자료구조에 따라 알고리즘이 달라지며 동일한 자료구조일지라도 구현할 수 있는 알고리즘은 천차만별이라는 것을 배웠다.

- 떠오르는 수 많은 알고리즘 중 가장 정확하고 효율적인 최선의 알고리즘을 구현하는 것이 중요하다.

 

- 그렇다면 좋은 알고리즘이라는 것은 무엇일까?

- 이는 주어지는 요구사항에 따라 달라진다.

- 누군가는 메모리 사용량의 최적화를 지향하는 알고리즘을 원할수도 있고 또 누군가는 메모리 사용량은 상관 없이 빠른 속도를 원할 수도 있다.

- 하지만 일반적으로는 알고리즘의 '속도'를 성능의 척도로 여긴다. 이를 시간복잡도라고 한다.

※ 시간복잡도 : 특정 알고리즘이 어떤 문제를 해결하는 데 걸리는 시간

 

- 문제는 이러한 시간을 측정하는 것이 사실상 불가능한데 그 이유는 사용자의 컴퓨터 성능이 제각기 다르기 때문이다.

- 동일한 알고리즘일지라도 사용자의 컴퓨터에 따라 10초 걸리는 알고리즘이 누군가에게는 30초가 걸릴수 있기 때문이다.

- 따라서 알고리즘을 평가할 때는 시간을 측정하는 방식이 아니라 코드의 성능에 많은 영향을 주는 부분을 찾아 실행시간을 예측하는 방식을 사용해야한다.

- 이때 코드의 성능에 많은 영향을 주는 부분이 바로 반복문이다. 반복문이 반복될수록 실행시간이 길어진다.(느려진다.)

- 즉, 알고리즘의 성능을 평가할 때는 해당 알고리즘의 반복문을 보고 성능을 평가한다.

---

ex)

[1, 3, 5, 7]

- 위의 배열에서 숫자 5를 찾으라고 했을 때 어떠한 알고리즘을 만드는 것이 좋을까?

- 간단하게 배열의 index = 0 부터 index = (배열의 길이 - 1)까지 순서대로 돌면서 검사를 하는 알고리즘을 생각할 수 있다.

- 위의 알고리즘을 이용하면 3번째 검사 때 5를 찾을 수 있다.

- 이때 해당 알고리즘의 성능을 어떻게 평가할 수 있을까? 총 4개 중 3번만에 찾아냈으니  3/4 인가?

- 그러면 좋겠지만 문제는 숫자 5가 배열의 어느 위치에 있느냐에 따라 매번 성능이 달라진다는 것이다.

1) 5가 index = 0 번째에 있다면 가장 best인 한 번의 검사만에 찾는다.
2) 5가 index = (배열의 길이 - 1) 번째에 있다면 가장 worst인 배열의 길이만큼 순회해야 찾을 수 있다.
3) 5가 index = (배열의 중간)에 있다면 평균의 경우이다.

출처 - 인프런, 그림으로 쉽게 배우는 자료구조와 알고리즘 (기본편)

 

- 위의 경우에서 볼 수 있듯이 때에 따라 성능이 매번 달라질 수 있다.

- 그렇기에 경우를 나누어서 성능을 평가해야하는데 이는 아래와 같이 구분할 수 있다.

출처 - 인프런, 그림으로 쉽게 배우는 자료구조와 알고리즘 (기본편)

- 최선의 경우는 Big-Ω(오메가) / 최악의 경우는 Big-O / 평균의 경우는 Big-Θ(세타)

- 이 중 Big-O와 Big-Θ를 주로 사용하는데 그 중에서도 가장 많이 사용하는 것이 Big-O 이다.

- 앞으로 자료구조와 알고리즘에 대한 글은 Big-O 개념을 주로 사용할 것이다.

---

● Big-O(선형시간 알고리즘)

[1, 3, 5, 7]

- 위 배열에서 5를 찾는 가장 최악의 경우는 5가 배열의 가장 마지막에 있어서 모든 배열을 순회해야하는 경우라고 했다.

- 이것을 일반화하면  →  배열에 데이터가 n개 있다면 n번 만에 원하는 데이터를 찾는 것이다.

- 이것을 Big-O 표기법으로 O(n) 이라고 표현하며 그래프는 아래와 같다.

출처 - 인프런, 그림으로 쉽게 배우는 자료구조와 알고리즘 (기본편)

- 일차함수의 모양을 띄며 O(n)의 n에 (1을 넣으면 계산량은 1), (5를 넣으면 계산량은 5)... (n을 넣으면 계산량은 n)이 되는 것이다.(이때 n은 '데이터의 수'를 의미한다.)

- 즉, 데이터가 많아질수록 그에 비례해서 계산량도 많아지는 것이다.

- 이러한 특징 때문에 O(n) 알고리즘을 선형시간 알고리즘이라고 부른다.

- 사실 Big-O 표기법으로는 성능을 정확하게 나타낼 수 없다.

- 단순히 해당 알고리즘에 주어지는 입력이 늘어날 때 계산량이 얼마나 늘어나는지를 표현하는 방법이기 때문이다.

---

● Big-O(최악의 경우) 표기법의 특징

- Big-O 표기법은 입력이 늘어날 때 계산량이 늘어나는 척도를 나타내기 위한 것이다.

n^2 + 2n + 100

- 만약 위와 같은 성능을 나타내는 알고리즘이 있다고 했을 때 이를 Big-O 표기법으로는 어떻게 나태내야 할까?

- 계산에 가장 많은 영향을 미치는 항만 표기하면 된다.

- 위의 식에서는 n^2 이 가장 많은 영향을 미치므로 O(n^2) 이라고 표현하면 된다.

3n^2 + 100n

- 위와 같은 성능은 어떻게 표기해야할까?

- 계산에 가장 많은 영향을 미치는 항이 3n^2 이므로 O(3n^2) 이라고 표기하고 싶지만 Big-O 표기법으로 표기할 때 상수는 큰 의미가 없으므로 제거해야 한다.(여기서의 상수 = 3)

- 즉, 다음과 같이 표기하면 된다.  →  O(n^2)

---

● O(1) - 상수시간 알고리즘

출처 - 인프런, 그림으로 쉽게 배우는 자료구조와 알고리즘 (기본편)

- 상수시간 알고리즘은 O(1) 으로 표현한다.

- 그래프에서도 볼 수 있듯이 입력의 크기에 상관없이 상수의 시간이 걸린다는 의미이다.

※ 주의 : 그림에 속으면 안 되는게 O(1) 이라고 해서 계산량이 반드시 한 번이라는 의미는 아니고 입력의 크기에 상관없이 항상 동일한 계산량이 걸리는 것을 얘기하는 것이다.

- 입력의 크기에 상관없이 문제를 해결하는데 항상 100번의 계산이 걸려도 O(1) 이고 항상 30번의 계산이 걸려도 O(1) 이라고 부르는 것이다.

- 말 그대로 계산량 = 항상 정해진 상수이기 때문에 상수시간 알고리즘이라고 부르는 것이다.

- 이 외에도 수 많은 알고리즘들이 있다(보라색으로 갈수록 성능이 좋지 않은 알고리즘)

출처 - 인프런, 그림으로 쉽게 배우는 자료구조와 알고리즘 (기본편)