02. 자료구조_java_빅오 표기법

1-3. 빅오 표기법

- 알고리즘의 효율성을 표시하는 표기법

- 위 그래프는 복잡도가  nn 인 알고리즘에 빅 오 표기법을 적용한 결과

- x축은 복잡도 n, y축은 필요한 일의 양이나 메모리를 의미함

- 다른 알고리즘이 이 그래프의 어떤 위치에 있는지에 따라 복잡도  n 인 알고리즘과 다른 알고리즘의 복잡도를 비교할 수 있습

- 다른 알고리즘이 복잡도  nn 인 알고리즘의 아래에 있다면, 같은 일을 하는 데 시간이 덜 들기 때문에 더 빠른 알고리즘

- 빅 오 표기법

   *  O (빅 오 복잡도) : 비교 대상인 그래프가 일치 혹은 아래에 있을 때. 비교 대상인 다른 알고리즘과 같거나 더 빠르다.

   *  θ (세타 복잡도) : 비교 대상인 그래프가 일치할 때. 비교 대상인 다른 알고리즘과 같다.

   *  Ω (빅 오메가 복잡도) : 비교 대상인 그래프가 일치 혹은 위에 있을 때. 비교 대상인 다른 알고리즘과 같거나 느리다.

   *  o (리틀 오 복잡도) : 비교 대상인 그래프가 아래에 있을 때. 비교 대상인 다른 알고리즘보다 더 빠르다.

   *  ω (리틀 오메가 복잡도) : 비교 대상인 그래프가 위에 있을 때. 비교 대상인 다른 알고리즘과 느리다.