해당 글은 <누구나 자료구조와 알고리즘_제이 웬그로우>책을 읽고 정리한 내용입니다.
빅오 : 단계 수 계산
- 빅 오는 시간 단위가 아닌 알고리즘에 필요한 단계 수만을 고려함으로써 일관성을 유지한다.
- O(N)은 배열 내에 N개의 원소가 있을 때 알고리즘을 끝내는 데 N개의 단계가 필요함을 표현하는 "빅 오"의 방법이다.
O(1)은 데이터가 아무리 커지더라도 단계 수가 변하지 않는 모든 알고리즘을 표현하는 방법이다.
상수로 유지되는 세 단계가 걸리는 알고리즘을 O(1)이라 본다면, 심지어 상수 100단계가 걸리는 알고리즘도 O(1)이라 표현할 수 있다.
100단계가 걸리는 알고리즘이 한 단계가 걸리는 알고리즘보다 덜 효율적이지만 O(1)의 의미는 어떤 O(N)알고리즘보다도 더 효율적이라는 뜻이다.
원소가 100개 이하인 배열에서는 O(N)알고리즘이 100단계가 걸리는 O(1)알고리즘보다 단계 수가 적게 걸린다.
원소가 정확히 100개인 배열에서는 두 알고리즘이 동일하게 100단계가 걸린다. 
하지만 핵심은 100보다 큰 모든 배열에서는 O(N)알고리즘에 더 많은 단계가 걸린다.
변화가 생기는 일정량의 데이터가 항상 있을 것이고 O(N)은 그 순간부터 무한대까지 더 많은 단계가 걸리므로 O(N)은 전반적으로 O(1)보다 덜 효율적이라 할 수 있다.
항상 백만 단계가 걸리는 O(1)알고리즘이라도 마찬가지다. 데이터가 증가할 수록 O(N)이 O(1)보다 덜 효율적인 어떤 지점에 반드시 다다르게 되며, 이 지점부터 데이터 양이 무한대로 갈 때까지 바뀌지 않는다.
상수 무시하기
빅 오 표기법은 상수를 무시한다.
빅 오 표기법은 지수가 아닌 수는 포함하지 않는다는 것을 단순히 수학적으로 표현한 문장이다.
O(2N)도 O(N)이고, O(N/2)도 O(N)이다.
O(N)보다 100배나 느린 O(100N)이라 해도 마찬가지로O(N)이다.
