Big-O

calendar 2022-10-18

content

연산을 수행하는 비용(시간, 공간)의 상한을 대략적으로 표기하는 방법

  • 비용이 어떤 비율로 증가하는지(상수, 선형, 로그, 지수 등)에만 관심있어서 지배적이지 않은 항은 무시한다
    • O(2N) == O(N)
    • O(log_2(N)) == O(log_10(N))

refs