[누구나 자료구조와 알고리즘] 3장. Big O 표기법

빅 오란?

• 시간 복잡도를 쉽게 소통할 목적으로 자료 구조와 알고리즘의 효율성을 간결하고 일관된 언어로 설명하기 위해 수학적 개념을 차용한 것.
• 위 개념을 형식화한 표현을 Big O 표기법이라 부른다.
• 빅 오 표기법을 사용해 주어진 알고리즘의 효율성을 쉽게 분류하고 이해시킬 수 있다.
  
  
• O(N)은 알고리즘에 N단계가 필요한 것 => "선형 검색"이 대표적 (linear time 선형 시간을 갖는 알고리즘)
• O(1)은 배열에 원소가 몇개든 한 단계에 해결되는 것 => "가장 빠른" 알고리즘 유형으로 분류 됨 => 배열의 검색 =>
  상수시간(constant time)을 갖는 알고리즘이라고도 표현
•  

Big O의 본질

• 빅오의 진정한 의미는 데이터가 늘어날 때 알고리즘의 성능이 어떻게 바뀌는지를 뜻한다.
• O(1)의 경우 데이터의 증가는 성능에 영향을 미치지 않는다.
  O(N)의 경우 데이터의 증가는 성능에 영향을 미친다. 정확히 데이터 증가에 비례하여 단계 수가 증가한다.
• 선형검색의 경우 최선의 시나리오는 O(1)[처음에 값이 있을 시] 최악의 경우는 O(N)[가장 끝에 값이 있을 시]
  위와 같은 경우 빅오의 표기법은 항상 최악의 시나리오를 가정해야 한다.
  즉, 선형검색의 빅오는 O(N)이다.
  최악의 시나리오에서 알고리즘이 얼마나 비효율적인지 정확히 알면 최악을 대비함과 동시에 알고리즘의 선택에 중요한 영향을 미칠 수 있다.
  
  

O(logN)

• 데이터가 두배로 증가할 때마다 한 단계씩 늘어나는 알고리즘이다.
• O(logN)은 데이터 원소가 N개 있을 떄 알고리즘에 log2N단계가 걸린다는 뜻 
  => 원소가 8개이면 log28 = 3이므로 이 알고리즘은 3단계가 걸린다.
• 간단히 말해 O(logN)은 원소가 하나가 될 때까지 데이터 원소를 계쏙 반으로 줄이는 만큼의 단계수가 걸린다는 뜻이다.
• 대표적인 알고리즘으로 앞에 봤던 이진검색(binary search)이 있다.

각 빅오(알고리즘)의 요소에 따른 단계 변화