시간복잡도 빅오(big-O)

이 글은 파이썬알고리즘 인터뷰(박상길 지음)을 리뷰하였습니다.

---

1) 빅오?

• 입력값이 커질때 알고즘의 실행시간(시간복잡도), 공간요구사항(공간복잡도)가 어떻게 증가하는지 판별 
• 입력값이 주어진 (최선/최악/평균)의 경우의 수행시간의 상한을 설명
• ex) 화물의 크기가 어쨋든 항상 일정시간으로 물건을 나르는 비행기와 화물의 크기에 비례하여 소요시간이 달라지는 온라인을 비교했을때, 일정 크기 이상에서는 비행기의 소요시간이 더 짧을수 있다. 

2) 표기방법

• 최고차항만 고려
• 계수 무시

1. O(1)

• 입력값이 아무리커도 실행시간 일정. 최고의 알고리즘

2. O(log n) 

• 실행시간이 입력값에 영향을 받으나 크지는 X

3. O(n)

• 입력값만큼 실행시간에 영향을 받음. 
• Linear-time 알고리즘 
• ex) 정렬되지 않은 알고리즘에서 max/min 찾기 

4. O(nlogn) 

5. O(n^2)

• 비효율적 알고리즘
• ex) 버블정렬 

6. O(2^n) 

• 재귀알고리즘. O(n^2)보다도 계산량 큼. 
• ex) 피보나치수 

7. O(n!)

• 가장느린 알고리즘. 입력값이 조금만 커져도 계산이 어려움. 
• ex) 외판원문제(Travelling Salesman Problem) 

3) 대부분의 알고리즘의 특징

• 시간과 공간의 트레이드오프 관계를 가짐(실행시간이 빠르면 메모리를 많이차지하고, 실행시간이 느리면 메모리를 적게차지함)