알고리즘의 복잡도

(Complexity of algorithms)

시간 복잡도 : 문제의 크기(입력으로 주어지는 데이터 크기)와 이를 해결하는 데 걸리는 시간 사이의 관계

-> 데이터 크기가 커지면, 어떤 관계를 가지면서 시간이 증가하느냐

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

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

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

Big-O Notation

점근 표기법의 하나

: 어떤 함수의 증가 양상을 다른 함수와의 비교로 표현

: 수학적인 정의는 일단 차치하고, 입력의 크기가 n일때,

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

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

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

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

->n에 비례

최댓값 - 끝까지 다 살펴보기 전까지는 알 수 없음

average case : O(n)

worst case: O(n)

그보다 낮은 시간 복잡도로, logn에 비례하는

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

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

n에 비례하는것보다 더 빨리 소요시간이 증가하는,

비례관계보다 더 복잡한 알고리즘

이차 시간 알고리즘 - O(n2승)

예:insertion sort:삽입 정렬

하나의 원소를 집어넣을때 , n에 비례하는 만큼의 횟수를 비교해서 삽입할 위치를 정해야함.

그리고 n만큼 반복하니까 n*n 즉,

특징: 만약 처음에 주어진 배열(리스트)가 이미 다 정렬이 되어있다면, 확인만하고 삽입 한번도 안하고

n개를 살펴보기만 하고 끝나기때문에..

best case: O(n)

이 수들이 역순으로 늘어서 있을때, 삽입할때 모든 정렬된거 한칸씩 다 밀어야하기때문에

worst case: O(n제곱)

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

예: 병합 정렬(merge sort) - O(nlogn)

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