Big-O로 연산 횟수 세기

대회에서는 속도가 중요합니다. 코드를 직접 측정하는 대신 코드가 수행하는 단계 수를 추정합니다. 이 추정치를 시간 복잡도라고 합니다. 🚀

빅오는 입력 크기 n이 커질 때 연산 횟수가 어떻게 증가하는지 나타냅니다. 작은 세부 사항은 무시하고 지배적인 추세에 집중합니다.

작업량이 n에 전혀 좌우되지 않으면 O(1)입니다. 리스트 원소 하나를 읽거나 덧셈 한 번을 수행하는 데 걸리는 시간은 항상 같습니다.

n개의 항목을 한 번 순회하는 단순 반복문은 O(n)입니다. 입력 크기를 두 배로 늘리면 작업량도 대략 두 배가 됩니다. 일상적으로 가장 많이 쓰이는 방식입니다.

n개의 항목을 대상으로 반복문 안에 반복문이 있으면 O(n^2)입니다. n = 1000이면 백만 단계이며, 그 이후로 빠르게 증가합니다.

각 단계에서 문제 크기가 절반으로 줄어들면 O(log n)을 얻습니다. 이진 탐색은 약 30단계만으로 10억 개의 항목을 처리할 수 있습니다. ✨

빠른 순서부터 느린 순서로 흔히 쓰는 순서는 O(1), O(log n), O(n), O(n log n), O(n^2)입니다. 앞쪽일수록 확장성이 좋습니다.

빅오는 상수 배수를 무시하므로 O(2n)은 O(n)일 뿐입니다. 두 번 순회해도 선형으로 증가하므로 배수가 복잡도 등급을 바꾸지 않습니다.

항을 더할 때는 가장 빠르게 증가하는 항만 고려합니다. O(n^2 + n)은 n이 커질수록 n^2이 n보다 훨씬 커지므로 O(n^2)로 단순화됩니다.

두 반복문을 차례로 실행하면 O(n + n) = O(n)이 됩니다. 두 반복문을 중첩하면 O(n^2)이 됩니다. 반복문의 형태가 어느 쪽인지 알려 줍니다.

대회에서는 가장 어려운 테스트를 기준으로 판정하므로 최악의 경우를 생각해야 합니다. 반복문이 일찍 반환된다고 가정하지 말고 끝까지 실행된다고 가정하십시오.

빅오 감각을 테스트해 보십시오.

이제 코드를 증가율로 읽을 수 있습니다: O(1), O(n), O(n^2), O(log n). 상수는 버리고 가장 큰 항만 남기며 최악의 경우를 생각하십시오. 🎯