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

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

알고리즘의 복잡도를 표현할때, big-O notation을 많이 이용

• O(n) : 선형시간, ex)순차탐색
• O(logn) : 로그시간, ex)이진탐색
• O(nlogn) : ex)병합정렬
• O(n^2) : 이차시간, ex)삽입정렬

정렬 문제에 대해 O(nlogn)보다 낮은 복잡도를 갖는 알고리즘은 존재하지 않음