[알고리즘개념]Big O

알고리즘 문제를 풀 때 제한시간, 제한용량이 있기 때문에 이 범위 내에서 문제를 해결하기 위해서는 내가 짜는 코드의 시간복잡도(소모하는 시간)나 공간복잡도(소모하는 용량)가 기준을 충족하는지 파악해야 할 필요가 있다. 이를 나타내는 방식으로 Big O 표기법을 주로 사용한다.

 

알고리즘 문제는 주로 데이터를 탐색해서 정답을 찾아내는데, 이 탐색하는 과정은 데이터의 수가 많아질 수록 길어지고 데이터 탐색 방식이 어떤것인지에 따라 효율이 달라진다. for문을 통해 리스트를 탐색할 때 리스트의 첫 항부터 마지막 항까지 전부 탐색하는 것과 반씩 쪼개어 가며 이분탐색하는 것은 리스트의 길어질 수록 그 연산에 걸리는 시간 차이가 명확히 드러난다.

 

가령 길이가 N인 리스트를 M번 반복해서 탐색해야 한다면 일반적으로는 N*M회를 반복하지만 M을 이분탐색할 시에는 N*log M회만 반복하면 된다. 이를 Big O 표기법으로 각각 O(NM)과 O(Nlog M)으로 나타낼 수 있다. 즉 알고리즘의 시간복잡도를 n의 크기에 따라 달라지는 running time(연산 길이)의 상한인 O(x)로 표현한다.

 

주요 함수별 input size-running time 그래프는 다음과 같다.

https://www.geeksforgeeks.org/analysis-algorithms-big-o-analysis/

따라서 시간 및 용량 제한이 있는 알고리즘 문제를 풀 때 Big O 개념을 이용해 어떤 알고리즘을 사용할지 선택할 수 있다.