알고리즘의 효율성
알고리즘의 수행 시간 또는 알고리즘이 수행하는 동안 사용되는 메모리 공간의 크기로 나타낼 수 있음
Big-O, Big-Theta, Big-Omega에 대해 설명
- Big-O
- 최악의 경우, 점근적 상한.
- n이 증가해도 이 경우보다 클 수 없음을 나타냄
- Big-Omega
- 최선의 경우, 점근적 하한.
- n이 증가해도 이 경우보다 작을 수 없음
- Big-Theta
- O와 Omega 표기가 같은 경우
- n이 증가하며 이 경우와 같은 증가를 보임
다른 것을 사용하지 않고 Big-O를 사용해서 표기하는 이유
Big-O 표기는 최악의 경우를 나타내는데 설계를 할 때 최악의 경우에 맞춰 설계를 해야하기 때문에
O(1)은 O(N) 보다 무조건적으로 빠른가
복잡도를 계산할 때 입력 크기 N이 무한대로 향한다고 생각하기 때문에 상수는 무시됨
O(3+N) = O(N) 이고 O(1000) = O(1) 이다.
이 경우 실제 O(1000)인 알고리즘은 N<1000인 경우 O(N)보다 느리다.
ㅡ/ㅡ