[python3] 10. 빅오 표기법(big-O)

1. 빅오 표기법

 

 - 입력값이 무한대로 향할 때 함수의 상한을 설명하는 수학적 표기 방법

 

 

 

2. 파일 업로드 예시

 

 - 파일 크기(n) , 소요시간(O(n))

 - 파일 크기와 소요시간은 비례한다.

 - 접근적 실행 시간(시간복잡도 == 계산복잡도)

    ==> 비용(n) 고려 없이 파일(n)이 아주 클 때 물리적으로 비행기를 통해 배달하는 시간(항상 일정한 시간 소요)

 

 

 

3. 빅오로 시간복잡도 표현

 

 - 최고차항만을 표기한다.  상수항은 무시한다.

 

O(1)
 - 입력값(n)이 아무리 커도 실행시간은 일정함. 최고의 알고리즘이다.

O(log n)
- 입력값(n)에 영향을 받지만 log n은 큰 영향을 받지는 않는다.

O(n)
 - 입력값 만큼 실행 시간에 영향을 받는다.
 - 선형시간 (linear-time) 알고리즘
 - 정렬되지 않은 리스트에서 최댓값 또는 최솟값 얻을 때

O(n log n) 
 - 효율 좋은 정렬 알고리즘.
 - 한 번 이상 비교해야 할 때 최고 빠르다

O(n제곱)
 - 비효율적인 정렬
 - ex) 버블 정렬

O(2의 n승)
 - 피보나치 수 재귀로 계산하는 알고리즘

O(n!)    
 - 가장 짧은 경로를 찾는 외판원 문제(TPS) 풀이 시 사용

 

즉. 빅오 표기법은 최선/최악/평균 경우의 수행 시간의 상한을 나타낸다!!