6강: 알고리즘의 복잡도
알고리즘의 복잡도 (Complexity of Algorithms)
알조리즘의 복잡도란?
-
문제 풀이의 방식이 얼마나 복잡하냐 단순하냐를 나타내는 말이 아니다
-
알고리즘이 실행함에 있어, 문제의 크기(일반적으로 데이터 원소의 개수)가 커짐에 따라서 얼마나 큰 시간(또는 공간)을 요구하느냐를 뜻함
-
시간 복잡도(Time Complexity)
- 문제가 커짐에 따라 이 문제를 해결하는 데 소요되는 시간이 어떤 양상으로 증가하는가를 말한다
-
공간 복잡도(Space Complexity)
- 문제가 커짐에 따라 이 문제를 해결하는 데 소요되는 기억 공간(메모리)의 필요가 어떤 양상으로 증가하는가를 말한다
- 이 강의에서는 시간 측면에서 논의
평균 시간 복잡도와 최악 시간 복잡도
- 평균 시간 복잡도(Average Time Complexity)
- 임의의 입력 패턴을 가정했을 때 소요되는 시간의 평균
- 최악 시간 복잡도(Worst-case Time Complexity)
- 가장 긴 시간을 소요하게 만드는 입력에 따라 소요되는 시간
알고리즘의 복잡도 표현
- 점근 표기법(asymptotic notation)을 흔히 이용
- 그 중
Big-O notation이라고 불리는 것을 많이 이용하는데 , 영문 대문자O를 이용하여 기호로 표현하기 때문에 붙은 이름이다.- 이 표기법은 함수의 증가 양상을 대강 파악할 수 있도록 하는데 목적이 있다.
- 예를들어 데이터 원소의 개수가 n_개라고 할 때, _O(n) 복잡도를 가지는 알고리즘은 원소의 개수에 비례하여 소요 시간이 증가한다.
- 계수는 그다지 중요하지 않다
선형 시간 알고리즘 - O(n)
- _n_개의 무작위로 나열된 수에서 최댓값을 찾기 위해 선형 탐색 알고리즘을 적용
- Average case: O(n)
- Worst case : O(n)
- 모든 수를 다 돌아봐야 하기 때문에 동일하다
로그 시간 알고리즘 - O(logn)
- _n_개의
크기 순으로 정렬된 수에서 특정 값을 찾기 위해 이진 탐색 알고리즘을 적용 - O(logn)의 복잡도를 가지고 문제를 풀 수 있으면 굉장히 효율적이다
이차 시간 알고리즘 - O(n^2)
- 삽입 정렬
- 정렬할 요소를 정렬된 요소 중 어느곳에 넣어서 정렬된 상태를 유지할지
- Best case: O(n)
- 이미 정렬이 된 상태
- Worst case: O(n^2)
- 역순으로 늘어서 있을 때
보다 나은(낮은) 복잡도를 가지는 정렬 알고리즘
- 병합정렬 - O(nlogn)
- 입력 패턴에 따라 정렬 속오데 차이가 있지만 정렬 문제에 대해 O(nlogn)보다 낮은 복잡도를 갖는 알고리즘은 존재할 수 없음
- 정렬할 데이터를 반씩 나누어 각각을 정렬시킴 : O(logn)
- 정렬된 데이터를 두 묶음씩 한데 합친다 : O(n)
- 전체적으로 O(nlogn)이 된다
- 입력 패턴에 따라 정렬 속오데 차이가 있지만 정렬 문제에 대해 O(nlogn)보다 낮은 복잡도를 갖는 알고리즘은 존재할 수 없음
꽤나 복잡한 문제
- 배낭 문제(Knapsack Problem)
- 모든 경우의 수를 다 해볼 경우 O(n^2)
- DP를 이용하면 간단하게 풀 수 있다.
요약
- 병합정렬, 즉 divide-and-conquer : O(nlogn)
- 이진탐색 : O(logn)
- 선형탐색 : O(n)
- N*N행렬의 모든 원소쌍 비교 : O(n^2)
- 행렬 A, B의 곱인 C의 행렬 계산 : O(n^3)
본 문서는 프로그래머스 어서와! 자료구조와 알고리즘 강의를 수강하고 정리했습니다.
