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

빅 오 란 입력값 N이  커질때, 함수의 실행 시간의 추이를 말한다. 

예를들어 숫자 1부터 N까지 출력하는 알고리즘을 작성했을 때 N 값이 100일때보다 1000000000000일때 실행시간이 커질 것이다. 

이처럼 입력값이 커졌을 때의 알고리즘 효율성이 중요한데, 이를 미리 판단할 수 있는 수학식이다. 

빅 오 표기법의 종류

• O(1): 입력값이 커져도 실행 시간이 일정함으로 가장 좋은 알고리즘 (거의 발견할 수 없음) 
• O(log n):  매우 큰 입력값에도 큰 영향을 받지 않음 (대표 알고리즘: 이진 검색)
• O(n): 입력값에 수행 시간이 비례함 (대표 알고리즘: 정렬되지 않은 리스트에서 최대값, 최솟값) 
• O(n log n): 병합 정렬을 비롯한 대부분의 효율 좋은 정렬 알고리즘이 이에 해당함. 
• O(n제곱): 버블 정렬같은 비효율적인 정렬 알고리즘이 여기에 속함
• O(2의 n제곱):피보나치 수를 재귀로 계산하는 알고리즘이 이에 해당한다. 

 

 

빅오 이미지 출처 링크