알고리즘의 복잡도 (Complexity of Algorithms)
문제를 푸는데 있어 얼만큼의 자원을 필요로하는가이다.
1) 시간 복잡도(Time Complexity) **
문제의 크기와 이를 해결하는데 걸리는 시간 사이의 관계
2) 공간 복잡도(Space Complexity)
문제의 크기와 이를 해결하는데 필요한 메모리 공간 사이의 관계
3) 평균 시간 복잡도 (Average Time Complexity)
임으의 입력 패턴을 가정했을 때 소요되는 시간의 평균
4) 최악 시간 복잡도 (Worst-case Time Complexity)
가장 긴 시간을 소요하게 만드는 입력에 따라 소요되는 시간
Big-O Notation
점근 표기법(asymptotic notation)의 하나
어떤 함수의 증가 양상을 다른 함수와의 비교(알고리즘의 복잡도를 표현할 때 흔히 쓰임)
O(logn), O(n), O(n^2), O(2^n)등으로 표기
- 입력의 크기가 n일 때,
O(logn) : 입력의 크기의 로그에 비례하는 시간 소요
O(n) : 입력의 크기에 비례하는 시간 소요
(계수는 그다지 중요하지 않다.)
선형 시간 알고리즘 - O(n)
예 : n개의 무작위로 나열된 수에서 최댓값을 선형탐색 알고리즘을 적용
최댓값- 끝까지 다 살펴보기 전까지는 알 수 없음
Average case : O(n)
Worst case : O(n)
로그 시간 알고리즘 - O(logn)
예 : n개의 크기 순으로 정렬된 수에서 특정 값을 찾기위해 이진 탐색 알고리즘 적용
이차 시간 알고리즘 - O(n^2)
예 : 삽입 정렬 (insertion sort)
하나의 원소를 집어넣을 때 n에 비례하는 횟수를 비교해서 원소의 갯수 n개만큼 비교해서 넣어야하기때문에 n의 제곱에 비하는 시간이 걸린다.
Best case : O(n)
Worst case : O(n^2)
보다 낮은 복잡도를 가지는 정렬 알고리즘
예 : 병합 정렬 (merge sort) - O(nlogn)
입력 패턴에 따라 정렬 속도에 차이가 있지만 정렬 문제에 대해 O(nlogn)보다 낮은 복잡도를 갖는 알고리즘은 존재할 수 없음이 증명되어있다.
- 정렬할 데이터를 반씩(2로 나눈==> log) 나누어 각각을 정렬시킨다. O(logn)
- 정렬된 데이터를 두 묶음씩 한데 합친다. O(n)
- 전체적으로 O(nlogn)만큼 걸린다.
꽤나 복잡한 문제
예 : 배낭 문제 (Knapsack Problem)
어떤 배낭이 있고 배낭안에 넣을 수 있는 최대 무게를 K라 하자. 배낭에 넣을 수 있는 N개의 물건이 각기 다른 가치 V를 가지고 있ㄱ 각 물건바다 다른 무게 W를 가지고 있을 때 배낭에 최대한 가치가 높은 물건들을 담을 수 있는 조합을 찾아라.
1) Brute Force Approcah
만약 n개의 물건이 있을 때 가능한 모든 조합을 만들기 위해서는 2^n개의 경우의 수를 모두 시도해 보아야한다. 가지고 있는 물건의 갯수가 늘어날수록 경우의 수가 2의 n승으로 늘어나며 O(n^2)의 시간이 걸린다.
2) Dynamic Programming
