시간 복잡도

1. 시간 복잡도 : 알고리즘 실행 속도 

2. 공간 복잡도 : 알고리즘이 사용하는 메모리 사이즈  (요즘은 잘안함)

 

알고리즘의 시간복잡도 주요요소는?

반복문!

 

 

알고리즘 성능 표기법

Big O (빅-오) 표기법 : O(N)

• 알고리즘 최악의 실행시간을 표기
• 가장 많이/일반적으로 사용함
• 아무리 최악의 상황이라도, 이정도의 성능은 보장한다는 의미이기 때문

Ω (오메가) 표기법 :  Ω(N)

• 오메가 표기법은 알고리즘 최상의 실행시간을 표기

Θ (세타) 표기법 :  Θ(N)

• 오메가 표기법은 알고리즘 평균 실행 시간을 표기

 

시간 복잡도 계산은 반복문이 핵심 요소임을 인지하고,

계산 표기는 최상, 평균, 최악 중, 최악의 시간인 Big-O 표기법을 중심으로 익히면 됨

 

대문자 O 표기법

입력 n에 따라 결정되는 시간 복잡도 함수

 

logN의 시간 복잡도가 나오는 이유는 그리 어렵지 않다.

예를 들어서 2개의 자식 노드를 가지는 이진 트리(binary tree)를 이용해서 M개의 값들 중에서 원하는 값을 찾는다고 해 보자.

처음에는 M개의 값들 모두 탐색 대상이지만, 루트 노드에서 첫 번째 자식 노드 층으로 이동하게 되면 그 수가 절반으로 줄게 된다.

이제 M/2개의 값들이 남게 되는데, 다시 한번 다음 자식 노드 층으로 넘어가게 되면 M/4개의 값들이 남게 된다.

이런 식으로 매번 층을 내려갈 때마다 남은 값의 수들이 절반이 되게 된다.

 

만약 탐색을 해야 하는 자료의 수가 2^n 개라면, 이진 트리를 사용할 경우 n번의 탐색을 통해서 원하는 값을 찾을 수 있게 된다.

log_2(2^n) = n 이기 때문에, 이진 탐색 트리(Binary Search Tree)를 이용한 이진 탐색 기법의 시간 복잡도가 log_2(N)이 되는 것이다.

 

다시 말해서, 자식 노드의 수가 m개인 트리로 N개의 자료에서 원하는 값을 탐색하는 알고리즘의 시간 복잡도는 log_m(N)이 된다.

출처: https://neos518.tistory.com/145 [As I've always been]