[자료구조] 04. Big O 표기법 (Big 0 notation) - python

09 Oct 2019 in Computer-Science

Big O 표기법 (Big 0 notation)의 정의와 특징에 대하여 알아보고 사용예시를 살펴본다.

04. Big O 표기법 (Big 0 notation) - python으로 구현하기

1. 정의

알고리즘의 시간 복잡도(알고리즘 실행 속도)를 표기할때 쓰이며 알고리즘의 최악의 실행 시간을 표기한다. 즉 알고리즘 효율성을 상한선 기준으로 표기하기 때문에 가장 일반적으로 사용된다.

2. 특징

Big O 표기법은 알고리즘에서 영향력 있는 항 이외에는 무시하고 가장 영향력이 있는 항을 표기한다. 예를 들어 O(8$n^2$ + 5n + 4)라고 하면 O($n^2$)으로 표기한다.
그 외에도 O(1), O(logn), O(n), O(nlogn), O(n²), O(2ⁿ), O(n!)등으로 표기함

3. 성능비교 및 사용예시

일반적으로 그림과 같이 O(1) < O(logn) < O(n) < O(nlogn) < O(n²) < O(n³) < O(2ⁿ) 순으로 시간이 오래 걸린다. 즉, O(1)이 가장 성능이 좋다.

사용예시

두 알고리즘의 성능을 비교할때 O(logn)과 O(n²)가 있다면 Big O 표기법에 의해 O(logn)의 성능이 더 좋다고 볼 수 있다