알고리즘의 복잡도
- 시간 복잡도 (Time Complexity)
문제의 크기와 이를 해결하는 데 걸리는 시간 사이의 관계
- 공간 복잡도 (Space Complexity)
문제의 크기와 이를 해결하는데 필요한 메모리 공간 사이의 관계
- 평균 시간 복잡도 (Average Time Complexity)
임의의 입력 패턴을 가정했을 때 소요되는 시간의 평균
- 최악 시간 복잡도 (Worst-case Time Complexity)
가장 긴 시간을 소요하게 만드는 입력에 따라 소요되는 시간의 평균
Big-O Notation
점근 표기법(입력 크기가 커질 경우, 알고리즘의 성능을 어떻게 변하는지를 표현) 중 하나다.
어떤 함수의 증가 양상을 다른 함수(보통 n으로 표현, 일반적으로 함수로 입력의 크기만큼 성능을 보이는 함수를 의미한다)와의 비교로 표현한 것이다. → 내가 알고자하는 함수의 성능을 일반(선형)적인 함수 성능과 비교한다.
선형 시간 알고리즘 - O(n)
- 최대값을 찾기위한 선형탐색 알고리즘Worst case : O(n)
- Average case : O(n)
로그 시간 알고리즘 - O(logn)
- 크기 순으로 정렬된 수에서 특정 값을 찾기 위한 이진 탐색 알고리즘
이차 시간 알고리즘 - O(n^2)
- 순차적으로 탐색범위에 값을 삽입한 후 탐색범위 내에서 한번더 정렬을 시도하는 삽입 정렬 알고리즘.Worst case : O(n^2) → 모든 수가 역순으로 정렬되어있었을 경우.
- Best case : O(n) → 이미 정렬되어 있는 경우.
보다 낮은 시간 복잡도를 가지는 알고리즘 - O(nlogn)
- 리스트를 반복적으로 반으로 나누어 각각을 정렬한 뒤, 그 정렬된 리스트들을 다시 두 묶음씩 합치는 합병 정렬
- 정렬 문제애 대해 O(nlogn)보다 낮은 복잡도를 갖는 알고리즘이 없다고 증명되어 있음.