빅오 표기법(Big O notation)

빅오 표기법은 알고리즘이 얼마나 빠른지 표시하는 특별한 방법입니다.

예를 들어, 리스트의 크기가 n이라고 가정해 봅시다. 단순 탐색은 원소를 하나씩 확인하기 때문에 n번을 연산해야 합니다. 그래서 빅오 표기법에 따른 실행 시간은 O(n)입니다. 빅오 표기법은 속도를 시간 단위로 세지 않습니다. 빅오 표기법은 연산 횟수를 비교하기 위한 것입니다. 빅오 표기법을 사용하면 수행해야 할 일이 많아질 때 알고리즘에 걸리는 시간이 어떤 식으로 증가하는지를 알 수 있습니다.

다른 예를 들어보자면, 이진 탐색은 크기가 n인 리스트를 확인하기 위해 log n번의 연산이 필요합니다. 빅오 표기법으로는 O(log n)입니다.

 

빅오 표기법은 알고리즘이 동작하기 위해 필요한 연산 횟수를 나타냅니다. 이 연산 횟수 앞에 커다란(Big) 알파벳 O를 쓰기 때문에 빅오 표기법이라고 불립니다.

최악의 실행 시간을 나타내는 빅오 표기법

전화번호부에서 사람을 찾기 위해 단순 탐색을 사용하고 있다고 가정한다면, 단순 탐색의 실행 시간이 O(n) 시간이라는 것은 최악의 경우, 즉 전화번호부의 모든 사람의 이름을 확인해야 하는 경우를 뜻합니다. 단순 탐색이 절대로 O(n) 시간보다 느려지지 않는다는 일종의 보장이 되는 것입니다.

많이 사용하는 빅오 실행 시간의 예 (빠른것부터 느린것까지)

• O(log n), 로그 시간 ex) 이진 탐색
• O(n), 선형 시간 ex) 단순 탐색
• O(n * log n) ex) 퀵 정렬과 같이 빠른 정렬 알고리즘
• O(n²) ex) 선택 정렬과 같이 느린 정렬 알고리즘
• O(n!) ex) 정말 느린 알고리즘

정리하자면,

• 알고리즘의 속도는 시간이 아니라 연산 횟수가 어떻게 증가하는지로 측정합니다.
• 이렇게 하면 입력 데이터의 크기가 늘어날 때 알고리즘의 실행 속도가 얼마나 증가하는지 알 수 있습니다.
• 알고리즘의 실행 시간은 빅오 표기법으로 나타냅니다.
• O(log n)는 O(n)보다 빠르고, 찾으려는 리스트의 원소의 개수가 증가하면 상대적으로 더 빨라집니다.
• 이진 탐색은 단순 탐색보다 아주 빠릅니다.

참고 출처: Bhargava, Aditya Y.  김도형, 『그림으로 개념을 이해하는 알고리즘』, 서울 : 한빛미디어, (2017), p.13-22

이미지 출처: https://www.geeksforgeeks.org/analysis-algorithms-big-o-analysis/

Analysis of Algorithms | Big-O analysis - GeeksforGeeks

https://towardsdatascience.com/introduction-to-big-o-notation-820d2e25d3fd

Introduction to Big O Notation