파이썬) 알고리즘의 복잡도와 Big-O 표기법

알고리즘의 복잡도는 문제를 푸는데 있어서 얼만큼의 자원을 요구하는지에 대한 지표이며 두가지로 나뉘는데

 

• 시간 복잡도 : 문제의 크기와 이를 해결하는데 걸리는 시간 사이의 관계

• 공간 복잡도 : 문제의 크기와 이를 해결하는데 필요한 메모리 공간 사이의 관계

컴퓨터의 성능이 발전되면서 공간 복잡도보단 시간 복잡도의 중요성이 높아보일 수 있지만 자료주고 특성상 고려해야하는 경우도 있다.

 

 

 

빅오(Big-O) 표기법이란 

빅오는 점근 표기법중의 하나이며, 어떤 함수의 증가양상을 다른 함수와의 비교로 표현한다. 알고리즘의 복잡도를 표현하는 흔히 쓰이고 이름처럼 영문 대문자 O를 이용해 표기한다. ex) O(n), O(1) ..

 

만약 입력의 크기가 n일 때 빅오표기법을 사용한다면 

O(logn) : 입력의 크기의 로그에 비례하는 시간 소요

O(n) :  입력의 크기에 비례하는 시간 소요

... 

 

빅오표기법을 사용규칙으로 입력크기의 가장 높은 차수만 남기고, 계수는 표기하지 않는다.

만약 입력의 크기가 3n² + 2n에 비례할 때 빅오표기법을 사용하면 O(3n² + 2n)  -> O(n²)으로 표기한다.

 

시간 복잡도의 일반적인 순서는 다음과 같다.

O(1) < O(log n) < O(n) < O(n log n) < O(n²) < O(2ⁿ) < O(n!) < O(nⁿ)

오른쪽으로 갈수록 시간 복잡도는 증가한다.

 

 

 

선형 탐색 알고리즘의 빅오 표기법

 

n개의 무작위로 나열된 리스트에서 최댓값을 찾을 때 모든 원소를 다 살펴보는 선형 탐색 알고리즘을 이용해야 한다.

모든 원소를 다 살펴봐야하기 때문에 리스트의 크기 n에 비례하는 시간이 소요된다. 따라서 시간 복잡도를 빅오 표기법으로 표기하면 O(n)이 된다.

 

이진 탐색 알고리즘의 빅오 표기법

 

이진 탐색은 크기순으로 정렬된 리스트에서 특정값을 찾기 위한 알고리즘이다. 앞선 포스팅에서 보았듯이 중앙값과 찾고자 하는 값을 비교하고 같지 않다면 중앙값 이상,이하의 원소들을 날려보내는 방식이다. 

 

시간 복잡도를 빅오 표기법으로 표기하면 O(logn)이 된다.

 

n 개의 수가 입력으로 주어져있을 때, 모든 원소들 사이의 대소 관계를 비교하여 n X n 행렬로 나타내고자 하는 문제가 있을 때, n개의 원소를 n번씩 비교하는 문제이기 때문에 시간 복잡도를 빅오 표기법으로 표기하면 O(n²)이 된다.

 

 

이 외에도 n*log n이나 n!에 비례하는 시간 복잡도를 가진 알고리즘들이 존재한다.  알고리즘의 시간 복잡도와 이를 표기하는 빅오 표기법에 대해 알아두면 코드의 시간적 효율을 높일 수 있는 능력을 기를 수 있다.