[Algorithm] 복잡도 표기와 비트

TOC

• 시간복잡도 표기법
  • Big-Oh 표기
  • Big-Omega 표기
  • Theta 표기
• 수와 표현
  • 비트와 logn
  • logn이란

시간복잡도 표기법

Big-Oh 표기

• 복잡도의 점근적 상한
• "최대 이만큼의 시간이 걸린다."

Big-Omega 표기

• 복잡도의 점근적 하한
• "최소 이만큼의 시간이 걸린다."

Theta 표기

• Big-Oh와 Big-Omega가 같은 경우에 사용
• n이 증가함에 따라 동일한 증가율을 가진다.
• "항상 이만큼의 시간은 걸린다."

수와 표현

비트와 logn

• k개의 비트를 사용하면 **0부터 2^(k-1)**까지 표현 가능
• n을 표현하기 위해서는 몇 개의 비트가 필요할까
• 2^(k-1)-1 >= n이 성립해야 한다.
• k >= log(n+1)이므로 약 logn 비트가 필요

logn이란

• 2의 몇 승이 n이 되느냐의 답
• n을 표현하는 데에 몇 비트가 필요한가
• 1로 시작해서 계속 두 배를 할 때 몇 번 해야하는가
• n을 2로 계속 나눌 때 몇 번 나누면 거의 1이 되는가