[코딩 + 알고리즘 완주반] 13일차. 시간복잡도

# 알고리즘 시간 복잡도 계산이 필요한 이유

하나의 문제를 푸는 알고리즘이 다양함

다양한 알고리즘 중 어느 알고리즘이 더 좋은지를 분석하기 위해 

 

# 알고리즘 복잡도 계산 항목

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

공간 복잡도 :  알고리즘이 사용하는 메모리 사이즈

 

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

입력의 크기가 커지면 커질수록 반복문이 알고리즘 수행시간 지배

 

# 알고리즘 성능 표기법

Big O (빅 오) 표기법 : 최악의 시행 시간을 표기

오메가 표기법 :  최상의 실행 시간을 표기

세타 표기법 : 평균 실행 시간을 표기

 

# Big O (빅 오) 표기법

O(n)

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

O(𝑙𝑜𝑔𝑛)의 베이스는 2- log 2 n

 

O(1) < O(𝑙𝑜𝑔𝑛) < O(n) < O(n𝑙𝑜𝑔𝑛) < O(𝑛2) < O(2^n) < O(n!)

 

ex)

O(1) : 상수번 실행

O(n) : n, n+10, 3n+10 번 ...

O(𝑛2) : n^2, n^2+ 1000 ,100n^2-100 ... 

계수나 상수 제외, 가장 최고차항 기준