2.1.1 빅오(Big-O) 표기법

실제로 코드를 실행해보면 소프트웨어나 하드웨어적 변수가 많아 똑같은 코드라도 환경에 따라 실행 시간이 조금씩 다릅니다. 이런 차이 때문에 시간을 정확한 수치로 표현하기는 어렵지만, 문법이나 구성에서 발생하는 비용을 수치화해 문제를 푸는 데 필요한 총 연산의 수를 수학적으로 표기할 수 있습니다. 이를 점근 표기법이라고 하며, 세 가지 표기법 중 가장 흔하게 사용하며, 최악의 경우를 계산하는 빅오(Big-O) 표기법에 대해 알아보겠습니다.

빅오 표기법은 알고리즘이 해당 차수이거나, 그보다 낮은 차수의 시간 복잡도를 가지는 점근적 상한 표기 방법을 의미합니다. 쉽게 ‘최악의 경우 이 정도의 시간이 걸린다’로 이해하면 됩니다.

좀 더 자세하게 수학적으로 정의하면 다음과 같습니다.

모든 0 < n₀ ≤ n에 대하여 0 ≤ f(n) ≤ cg(n)인 양의 상수 c와 n₀이 존재하면 f(n) ∈ Og(n))이다.

예를 들어 a 변수에 +1을 하는 코드를 작성했다고 한다면(코드로 a += 1) 이를 실행하기 위해 필요한 연산은 총 1번입니다. 만약 데이터 개수가 n개라면 프로그램을 실행할 때 발생하는 비용을 f(x)라고 가정하면 데이터 개수만큼 연산을 1번 수행하므로 f(n) = n이라고 표기할 수 있고, 이를 빅오 표기법으로 나타내면 O(n)이 됩니다.