Python/ 알고리즘 복잡도

어서와! 자료구조와 알고리즘은 처음이지? 6강 

알고리즘 복잡도란?

문제를 푸는 데 있어 얼마만큼의 컴퓨팅 자원이 드는가

컴퓨팅 자원은 크게 두 가지로 나뉜다. 

(1) 시간 복잡도 

문제의 크기와 이를 해결하는 데 걸리는 시간 사이의 관계. 즉, 데이터가 커지면 어떤 식으로 소요 시간이 커지나 

- 평균 시간 복잡도 : 임의의 입력 패턴을 가정했을 때 소요되는 시간의 평균

- 최악 시간 복잡도 : 가장 긴 시간을 소요하게 만드는 입력에 따라 소요되는 시간

알고리즘의 복잡도를 표현할 때 점근 표기법의 하나인 'Big-O Noation'을 많이 사용한다. 

입력의 크기가 n일 때, 

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

- 입력의 크기의 로그에 비례하는 시간 소요. 

- ex) n개의 크기 순으로 정렬된 수에서 특정 값을 찾기 위해 이진 탐색 알고리즘 적용

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

- 입력의 크기에 비례하는 시간 소요

- ex) n개의 무작위로 나열된 수에서 최댓값을 찾기 위해 선형 탐색 알고리즘을 적용

• 이차 시간 알고리즘 - O(n^) 

- ex) 삽입 정렬 (insertion sort)의 worst case

• O(nlong n)

- ex) 병합 정렬 (merge sort) : 정렬할 데이터를 반씩 나누어 각각 정렬시킨다, O(log n) --> 정렬된 데이터를 두 묶음씩 한데 합친다, O(n) 

- 정렬 문제에 대해 O(nlog n)보다 낮은 복잡도를 갖는 알고리즘은 존재할 수 없다는 게 증명됐다.

이해 못 한 문제) 

(2) 공간 복잡도

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