[자료구조&알고리즘] 알고리즘의 복잡도

※ 알고리즘의 복잡도 (Complexity of Algorithms)

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

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

평균 시간 복잡도(Average Time Complexity) : 임의의 입력 패턴을 가정했을 때 소요되는 시간의 평균

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

 

※ Big-O Notation

- 점근 표기법(asymptotic notation)의 하나로 어떤 함수의 증가 양상을 다른 함수와의 비교로 표현함

흔히 알고리즘의 복잡도를 표현할 때 쓰인다. O(logn), O(n), O(n^2), O(2^n) 등으로 표기가 가능하다

＊입력의 크기가 n 일 때, O(logn) - 입력의 크기의 로그에 비례하는 시간 소요/ O(n) - 입력의 크기에 비례하는 시간 소요 

 

※ 로그 시간 알고리즘 - O(logn)

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

 

※ 병합 정렬 (merge sort) - O(nlogn)

- 입력 패턴에 따라 정렬 속도에 차이가 있지만 정렬 문제에 대해 O(nlogn)보다 낮은 복잡도를 갖는 알고리즘은 존재할 수 없음을 증명함. 정렬할 데이터를 반씩 나누어 각각 정렬시키는 방식