3장 빅 오 표기법

• 알고리즘의 효율성을 결정하는 주 요인은 알고리즘 수행에 필요한 단계 수
• 배열에 N개의 원소가 있을 때 선형 검색에 N단계가 필요하다고 표현하면…?
• 빅 오 표기법

1. 빅 오: 원소가 N개일 때 몇 단계가 필요할까?

• O(N)
  • “빅 오 엔”이라고 발음한다.
  • 보통 “빅”을 생략하고 “오 엔”이라고 부름.
  • 알고리즘에 N단계가 필요하다는 뜻
• O(1)
  • 1장에서 배열 읽기에 필요한 단계 수는 “배열의 크기와 상관없이” 딱 한 단계.
  • 이때의 표기를 O(1)이라고 한다.
  • 즉 배열에 원소가 몇 개든 한 단계만 필요할 때.
  • O(1)의 시간 복잡도를 갖는 알고리즘을 가장 빠른 알고리즘 유형으로 분류한다.
  • 상수 시간(constant time)을 갖는 알고리즘이라고도 표현한다.

2. 빅 오의 본질

• 빅 오가 진정으로 의미하는 것: 데이터가 늘어날 때 알고리즘의 성능이 어떻게 바뀌는지
• 즉 O(1)과 O(3)은 같다.
• 별도로 명시하지 않는 한 빅 오 표기법은 일반적으로 최악의 시나리오를 의미한다.
• “비관적인” 접근

3. 세 번째 유형의 알고리즘

• O(log N): 이진 검색의 시간 복잡도
  • 로그 시간(log time)의 시간 복잡도
• 로가리즘?

4. 로가리즘

• log는 logarithm의 줄임말이다.?
  • 헉
  • 진짜네
  • Logarithm - Wikipedia

5. O(logN) 해석

• 컴퓨터과학에서 O(logN)은 사실 밑이 2인 이진로그이다.
• O(logN)은 원소가 하나가 될 때까지 데이터 원소를 계속해서 반으로 줄이는 만큼의 단계수가 걸린다는 뜻이다.

이진로그