빅 오(Big O)
Computer Scientist들은 서로간에 시간 복잡도를 쉽게 소통할 목적으로 자료구조와 알고리즘의 효율성을 간결하고 일관된 언어로 설명하기 위해 수학적 개념을 차용했다.
이러한 개념이 빅 오(Big O) 표기법이다.
빅 오(Big O)가 의미하는 것
- 데이터 원소가 N개일 때, 알고리즘에 몇 단계가 필요한가?
[배열 읽기에 필요한 단계 수] : O(1) → (N과 무관하게) 배열에 원소가 몇 개든 배열에서 읽기는 항상 한 단계면 된다.
[N개 배열의 선형 검색 단계 ] : O(N) → 배열의 선형 검색에는 N단계가 필요하다
[이중 배열의 선형 검색 단계] : O(N^2) → 이중 for문을 사용하므로 N의 2승 단계가 필요하다.
빅 오(Big O)가 나타내는 또다른 깊은 의미
- 빅 오가 진정으로 의미하는 것, 데이터가 늘어날 때 알고리즘의 성능이 어떻게 바뀌는지를 뜻한다.