빅 오(Big O) : N개의 원소일 때, 몇 단계가 필요한가?

  빅 오(Big O)

Computer Scientist들은 서로간에 시간 복잡도를 쉽게 소통할 목적으로 자료구조와 알고리즘의 효율성을 간결하고 일관된 언어로 설명하기 위해 수학적 개념을 차용했다.

 

이러한 개념이 빅 오(Big O) 표기법이다.

 

  빅 오(Big O)가 의미하는 것

  - 데이터 원소가 N개일 때, 알고리즘에 몇 단계가 필요한가?

 

[배열 읽기에 필요한 단계 수] : O(1)  → (N과 무관하게) 배열에 원소가 몇 개든 배열에서 읽기는 항상 한 단계면 된다. 

[N개 배열의 선형 검색 단계 ] : O(N) → 배열의 선형 검색에는 N단계가 필요하다

[이중 배열의 선형 검색 단계] : O(N^2) →  이중 for문을 사용하므로 N의 2승 단계가 필요하다.

 

 

  빅 오(Big O)가 나타내는 또다른 깊은 의미

  - 빅 오가 진정으로 의미하는 것, 데이터가 늘어날 때 알고리즘의 성능이 어떻게 바뀌는지를 뜻한다.