[알고리즘][빅오] 빅오표기법

출처 : 누구나 자료구조와 알고리즘 (제이웬그로우 지음, 심지현 옮김)

 

3장 빅 오 표기법 중

알고리즘에 필요한 단계 수를 하나의 수로 못 박을 수 없기 때문이다.

빅 오 표기법은 수학에서 유래하지만 이 책은 수학 용어 없이 컴퓨터 과학과 연관 지어 설명한다.

 

3-1. 빅 오 : 단계 수 계산

빅 오는 시간 단위가 아닌 알고리즘에 필요한 단계 수만을 고려함으로써 일관성을 유지한다.

O(N)은 배열 내에 N개의 원소가 있을 때 알고리즘을 끝내는데 N개의 단계가 필요함을 표현하는 "빅 오"의 방법이다.

 

 

3-2. 상수 시간관 선형 시간

빅 오 표기법이 알고리즘에 걸리는 단계 수를 단순히 22나 400같은 고정된 수보다 더 의미 있게 표현한다는 것을 알았다.