파이썬 알고리즘 인터뷰 | 4장. 빅오(Big O)

시간 복잡도

어떤 알고리즘을 수행하는 데 걸리는 시간을 설명하는 계산 복잡도

 

빅오

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

점근적 실행시간을 표기할 때 가장 널리 쓰이는 수학적 표기법

 

O(1)

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

 

O(logn)

실행 시간은 입력값에 영향을 받는다 로그는 매우 큰 입력값에도 크게 영향을 받지 않는 편 

대표적으로 이진 검색

 

O(n)

입력값만큼 실행시간에 영향을 받음, 선형 시간 알고리즘,

정렬되지 않은 리스트에서 최댓값 또는 최솟값을 찾는 경우

모든 입력값을 적어도 한번 이상은 살펴봐야 함

 

O(nlogn)

병합정렬을 비롯한 대부분 효율 좋은 정렬 알고리즘 

입력값이 최선인 경우, 비교를 건너뛰어 O(n)이 될 수 있으며 팀소트가 이런 로직을 갖고 있음 

 

O(n^2)

버블정렬 같은 비효율적인 정렬 알고리즘

 

O(2^n)

피보나치수를 재귀로  계산하는 알고리즘

 

O(n!)

각 도시를 방문하고 돌아오는 가장 짧은 경로를 찾는 외판원 문제를 브루트 포스로 풀이할때

가장 느린 알고리즘