[자료구조 · 알고리즘] 알고리즘의 복잡도 (Complexity of Algorithms)

어서와! 자료구조와 알고리즘은 처음이지? 강의 수강 후 내용을 정리한 글입니다.

 

알고리즘의 복잡도란 문제를 해결하는 데에 있어서 얼마만큼의 자원을 요구하는 가를 파악하는 것이다.

크게 시간 복잡도와 공간 복잡도로 나눌 수 있다.

 

시간 복잡도 (Time Complexity)

 

문제의 크기와 이를 해결하는 데 걸리는 시간간의 관계이다.

문제 해결을 위해 입력(input)으로 들어오는 것을 문제의 크기라고 말한다.

 

• 평균 시간 복잡도

데이터 입력이 랜덤하게 들어왔을 때, 즉 임의의 입력 패턴을 가정했을 때 걸리는 시간의 평균

 

• 최악 시간 복잡도

가장 긴 시간을 소요하게 만드는 입력에 따라 걸리는 시간 (최악의 경우)

 

 

공간 복잡도 (Space Complexity)

 

문제의 크기와 이를 해결하는 데 필요한 메모리 공간 사이의 관계이다.

 

 

Big-O Notation - 빅오 표기법

 

점근 표기법 중의 하나로, 알고리즘의 복잡도를 표현할 때 주로 사용된다.

함수의 증가 양상을 다른 함수와의 비교를 통해 표현한다.

 

입력의 크기가 n이라고 가정할 때, O(log n), O(n) 등으로 표현할 수 있다.

계수는 중요하지 않다.

빅오 표기법 종류에 대해 알아보겠다.

 

• O(n) : 선형 시간 알고리즘

앞에서부터 끝까지 하나하나 살펴보는 것이므로 실행 시간은 n에 비례한다. 

즉, 평균/최악의 경우가 모두 같은 O(n)이다.

 

• O(log n) : 로그 시간 알고리즘

이진 탐색 알고리즘이 대표적인 예시이다. 이진 탐색 알고리즘은 이미 정렬되어 있다는 가정 하에 진행돼야 한다는 것을 앞서 확인하였다. 따라서 해당 알고리즘은 앞선 알고리즘보다 더욱 시간을 단축할 수 있다.

 

• O(log n^2) : 이차 시간 알고리즘

삽입 정렬의 방법이 해다 알고리즘의 예시이다. 개수 n만큼을 제곱한 값이다.

삽입 정렬의 경우, 이미 주어진 리스트가 찾는 순서대로 정렬되어 있다면 베스트 케이스는 O(n)이다.

하지만 찾는 순서와 다르게 역순으로 되어 있다면 워스트 케이스는 O(n^2)이다.

 

• O(nlogn)

현재 O(nlogn) 보다 낮은 복잡도를 가지는 알고리즘은 존재하지 않는다는 증명이 나와있다.

병합 정렬이 해당되며 정렬할 데이터를 반씩 나누어 각각 정렬한 다음, 가장 앞에 놓일 것부터 골라나가는 O(log n)과

정렬된 데이터를 앞에서부터 하나하나 확인하여 두 묶음씩 다시 합쳐나가는 O(n) 과정을 통해 결과적으로 O(nlog n)로 나타낼 수 있다.