시간 복잡도, Big-O 표기법

알고리즘이란

알고리즘이란 어떤 목적을 달성하기 위해/문제를 해결하기 위해 수행해야 하는 과정들이다.
목적을 향한 길은 여러가지가 있을 수 있고,
상황에 맞춰 가장 빠르고 자원은 적게 쓰는 알고리즘을 선택해야 한다.
= 가장 효율적인 알고리즘을 선택해야 한다.

효율적인 알고리즘

효율적인 알고리즘이란
1) 수행 시간이 짧고
2) 자원을 덜 사용하는 알고리즘이다.

위 두 가지 관점에서 알고리즘의 성능을 분석하기 위해
수행 시간과 관련된 것은 -> 시간 복잡도
사용 자원과 관련된 것은 -> 공간 복잡도로 구분한다.

복잡도를 표현하는 방법

점근 표기법
함수를 단순화하여 증가율을 다른 함수와 비교하는 방법

알고리즘이 복잡할수록 어느 알고리즘이 효율적인지 비교하는 것이 어렵다.
그래서 함수를 단순화, 비교하기 위해 점근 표기법을 사용한다.

이미지의 함수가 각각 알고리즘의 복잡도를 나타낸다고 했을 때,
n에 들어가는 수가 적을 때만 본다면 각 함수의 값의 차이가 크지 않아 어떤 함수를 선택하는 것이 가장 좋을지 판단이 어렵다.

하지만 n이 점점 커지면 커질수록 함수 간 격차가 커진다.
이렇게 함수를 비교하고나면 작업량이 많아져도 복잡도가 큰 폭으로 늘지 않는 상수함수(1) 혹은 로그 함수(log n)를 선택해야 한다는 것을 알 수 있다.

빅오 표기법

알고리즘의 복잡도를 표기하는 방법에는 아래 세 가지 가 있다.

• 빅 오메가 표기법(Big-Ω)
• 빅 세타 표기법(Big-Θ)
• 빅오 표기법(Big-O)

이 세 표기법은 각각 최선/최선, 최악의 범위/최악 중 어떤 상태에 초점을 맞췄는지가 다르다.

빅 오메가는 최선의 상황
빅 세타는 최선과 최악의 사이 범위
빅오는 최악의 상황에 기준을 둔다.

빅 오메가는 점근적 하한을 통해
'알고리즘의 성능이 아무리 빨라도 ~ 이하'라는 정보를 준다.

빅 세타는 점근적 상한 및 하한을 통해
'어떤 상황에서도 알고리즘 성능이 ~ 이상 ~ 이하'라는 범위 정보를 준다.

빅오는 점근적 상한을 통해
'알고리즘의 성능이 최악의 경우라도 ~ 이상'이라는 정보를 준다.

🤔알고리즘을 선택할 때,
최선의 경우만 고려할 수는 없다.
최악의 경우에도 비교적 일관적인 성능을 내는지를 고민해야한다.
💣빅오 표기법을 통해서는
아무리 작업량이 많아져도, 최악의 경우에도 이 정도는 한다!는 내용을 보장 받을 수 있다.
💥때문에 빅오 표기법을 가장 많이 쓴다.

빅오 표기법 성능 비교

빅오 표기법은 증가율에 영향이 크지 않은 항을 무시하고
지배적 항으로 값을 표현한다.
$O(N^2 + 2N + 3) -> O(N^2)$

그리고 빅오 표기법의 성능을 비교하면 아래 이미지와 같다.

n의 값에 따라 수치가 증가하는 정도는 아래와 같이 커진다.
$O(1),O(logn) < O(n) < O(nlogn) < O(n^2) < O(2^n) < O(n!)$
되도록이면 낮은 증가율을 갖는 상수함수, 로그함수 복잡도의 알고리즘을 선택해야 한다.

복잡도를 어떻게 알지?

시간 복잡도 구하는 요령

이 블로그에 시간 복잡도 구하는 예시와 요령이 잘 설명되어 있어서 이해에 도움이 됐다👍
지배적 항이 무엇인지 파악해서 연산!

정렬 알고리즘 복잡도

NaverD2에 정렬 알고리즘별 복잡도와 개념이 잘 설명되어 있다.
🙅‍♂️버블 정렬, 삽입 정렬은 느린 정렬
🙆‍♂️병합 정렬, 힙 정렬, 퀵 정렬은 빠른 정렬