누구나 자료 구조와 알고리즘 | 빅 오 표기법

✔️빅 오가 무엇인가?

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

• 빅 오의 본질
  • 빅 오는 데이터가 늘어날 때 단계가 어떻게 증가하는 지를 설명한다.
    즉, 데이터가 늘어날 때 알고리즘 성능이 어떻게 바뀌는지

• O(N) = 알고리즘에 N단계가 필요하다.
  • N은 항상 상수
• O(1) = 가장 빠른 알고리즘 단계
  • 배열 읽기에는 딱 한 단계만 필요
    

• O(1) VS O(N)
  • 데이터가 증가할수록 O(N)이 O(1)보다 덜 효율적인 어떤 지점에 반드시 다다르게 됨
• 선형 검색의 효율성을 빅 오로 표기해보자!
  • 찾고자 하는 항목이 첫 번째 있다면 : 최선의 시나리오 O(1)
  • 찾고자 하는 항목이 마지막에 있다면 원소N개를 모두 검색해야 하기 때문에 : 최악의 시나리오 O(N)
  • 별도로 명시하지 않는 한 빅 오 표기법은 최악의 시나리오를 의미함
• 이진 검색의 빅 오 표기법
  • O(1)과 O(N) 사이 어디쯤 = O(logN) = 로그 시간의 시간 복잡도
  • O(logN) : 데이터가 두 배로 증가할 때마다 한 단계씩 늘어나는 알고리즘을 설명하는 빅 오의 방법
  • 가장 효율적인 순서 : O(1) > O(logN) > O(N)
• 왜 O(logN)이라 부르는가? ⇒ 로가리즘
  • 로그 : 로가리즘의 줄임말
  • 원소가 N개 있을 때 logN단계가 필요하다.
  • 즉, O(logN)은 원소가 하나가 될 때까지 데이터 원소를 계속해서 반으로 줄이는 만큼의 단계 수가 걸린다는 뜻