빅오 표기법

알고리즘을 구현하는 법을 학습하기 전에 알고리즘이 얼마나 효과적인지 분석하는 법을 이해해야 한다.

빅오 표기법이란?

빅오(Big-O) 표기법은 시간 및 알고리즘 공간 복잡도를 분석하기 위한 개념인데, 알고리즘의 최악의 경우 복잡도를 측정하여 효율성을 표기한다고 생각하면 된다.
빅오(Big-O) 표기법에서 n은 입력의 개수를 나타내는데, 빅오와 관련된 질문으로 "n이 무한으로 접근할 때 어떻게 될까?"가 있다.
빅오 표기법은 알고리즘을 구현할 때 해당 알고리즘이 얼마나 효율적인지 나타내기 때문에 중요하다고 볼 수 있다

빅오 표기법 규칙

알고리즘의 시간 복잡도를 f(n)이라고 표현하면 n은 입력의 개수 , f(n)time 은 필요한 시간 , f(n)space 는 필요한 공간(추가적인 메모리)을 나타낸다.
알고리즘 분석의 목표는 f(n) 을 계산함으로써 알고리즘의 효율성을 이해하는것이다.
하지만 f(n)을 계산한다는 것은 굉장히 어려울 수 있는데, 이를 위해 개발자 형님들이 f(n)를 계산하는데 도움이 되는 기본적인 규칙을 제공한다.

• 계수 법칙: 상수 k가 0보다 크다고 할 때 ( k>0), f(n) 이 O(g(n))이면 kf(n)은 O(g(n))이다.

f(n) 이 O(n^2) 이면   kf(n) 도 O(n^2) 라는 뜻인듯

• 합의 법칙: f(n) 이 O(h(n)) 이고 g(n)이 O(p(n)) 이면 f(n) + g(n) 은 O(h(n)+p(n)) 이다.
  즉 두 개의 알고리즘이 있고 각각의 시간복잡도 가 있을 때 빅오 표기법 더할수 있다는 뜻.

• 곱의 법칙: (n) 이 O(h(n)) 이고 g(n)이 O(p(n)) 이면 f(n) g(n)은 O(h(n)p(n))
  마찬가지로 두 개의 알고리즘이 있고 각각의 시간복잡도 가 있을 때 빅오 표기법 역시 곱해진다.

• 전이 법칙: f(n)이 O(g(n)) 이고 g(n)이 O(h(n)) 이면 f(n)은 O(h(n)) 이다.
  눈물이 날거같음

• 다항 법칙: f(n)이 k차 다항식이면 f(n)은 O(n^k) 이다.

계수, 합, 곱, 다항 법칙이 일반적으로 많이 쓰인다고 한다.

자세한건 다음 시간에..