Big O

Big-O

Big-O란?

• 알고리즘의 효율성을 나타내는 지표
• 시간 복잡도
  • 해당 알고리즘으로 동작시, 점근적으로 실행시간이 어떻게 되는가?
  • n개의 데이터가 input으로 주어질 경우, 얼마나 시간이 지나야 알고리즘이 완료되는가?
  • O(1), O(logN), O(N), O(NlogN), O(N^2), O(2^N) 등

• 공간 복잡도
  • 메모리를 얼마나 썼는가?
  • n개의 데이터가 input으로 주어질 경우, 메모리는 얼마나 사용을 하는가?
  • 단지 n번 호출했다고 O(n)의 공간을 쓰는 건 아님
    • 해당 함수들이 호출 스택에서 공간을 별도로 사용하지 않으면 O(1)일 수 있다

덧셈 vs 곱셈

• 덧셈: A일을 모두 끝마친 후에 B일을 수행하라
• 곱셈: A일을 할 때 마다 B일을 수행하라

재귀 함수에서의 시간 복잡도

• O(분기^깊이)

주의할 점

• 같은 N을 서로 다른 두 가지 경우에 혼용해서 쓰지 않을 것
• 시간 복잡도를 구할 때, 해당 코드의 목적이 무엇인지 생각해 볼 것
  • 아무리 재귀라도, 2의 배수에서만 재귀 호출이 호출된다면 수행시간은 O(logN)이 된다