알고리즘의 복잡도

시간복잡도(Time Complexity)

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

공간 복잡도(Space Complexity)

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

평균시간복잡도(Average Time Complexity)

임의의 입력 패턴을 가정했을때 소요되는 시간의 평균

최악 시간 복잡도(Worst-case Time Complexity)

가장 긴 시간을 소요하게 만드는 입력에 따라 소요되는 시간

Big-0 Notation

점근표기법의 하나

어떤 함수의 증가양상을 다른 함수와의 비교로 표현(알고리즘의 복답도를 표현할 때 흔히 쓰임)

O(log n), O(n), O(n^2), O(2^n)등으로 표기

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

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

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

최대값 - 끝까지 다 살펴 보기 전까지는 알 수 없음 Average case: O(n) Worst case: O(n)

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

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

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

삽입정렬(insert sort)

Best case: O(n) Worst case: O(n^2)

보다 나은 복잡도를 가지는 정렬 알고리즘

병합 정렬(merge sort) - O(nlog n)

입력 패턴에 따라 정렬 속도가 차이가 있지만 정렬 문제에 대해 O(nlog n)보다 낮은 복잡도를 갖는 알고리즘은 존재할 수 없음이 증명되어 있음

정렬할 데이터를 반씩 나누어 각각을 정렬시킨다. 정렬된 데이트를 두묶음씩 한데 합친다.