Big-O 표기법은 주로 점근적 복잡도, 즉 입력이 무한대에 가까워질 때 함수의 동작에 초점을 맞춥니다. 예를 들어, O(N^2)와 같은 복잡도에서 N이 매우 커지면 다른 항들은 무시할 수 있게 됩니다. 이는 코드의 확장성을 평가할 때 가장 중요한 부분입니다. 다양한 Big-O 복잡도는 다음과 같습니다:
-
O(1) - 상수 시간 복잡도: 데이터셋의 크기에 관계없이 실행 속도가 일정합니다. 예를 들어, 해시(Hash)에서 특정 항목을 찾는 작업은 해시의 크기에 영향을 받지 않아 매우 효율적입니다. 이는 Big-O 복잡도 중 최상의 시나리오로, 입력 크기를 무한정 확장해도 실행 시간이 동일하게 유지됩니다.
-
O(n) - 선형 시간 복잡도: 실행 속도가 데이터셋의 크기에 비례하여 증가합니다.
Array#find와 같은 배열 순회 작업이나 선형 탐색(linear search)이 대표적인 예입니다. 배열에 100개의 항목이 있다면, 1개의 항목이 있을 때보다 100배 더 오래 걸릴 수 있습니다. 선형 탐색의 최악의 경우(Upper Asymptotic Bound)는 배열의 모든 요소를 확인해야 할 때 발생하며, 이는 배열의 크기(n)에 비례합니다. -
O(n^2) - 지수 시간 복잡도: 실행 속도가 데이터셋 크기의 제곱에 비례하여 증가합니다. 이는 주로 중첩된 루프(nested loops)에서 발생합니다. 하나의 루프가 O(n)이라면, 두 개의 중첩 루프는 O(n^2)가 되며, 이는 데이터셋이 커질수록 매우 비효율적인 성능을 초래합니다.
-
O(log n) - 로그 시간 복잡도: 데이터셋의 크기가 커질수록 실행 시간이 매우 완만하게 증가합니다. 이진 탐색(binary search)이 대표적인 예로, 정렬된 배열에서 목표 요소를 찾기 위해 검색 범위를 절반씩 줄여나갑니다. Ruby의
Array#bsearch메서드가 이 알고리즘을 구현합니다. 데이터셋이 10배 증가해도 실행 시간은 약 2배만 증가합니다. -
O(n log n) - 로그 선형 시간 복잡도: O(n^2) 알고리즘의 작업을 줄이기 위한 영리한 방법으로 종종 나타납니다.
Array#sort에서 사용되는 퀵 정렬(quicksort)과 같은 일반적인 정렬 알고리즘이 평균적으로 O(n log n) 복잡도를 가집니다.
Big-O 개념은 데이터베이스 성능에도 직접적인 영향을 미칩니다. 많은 웹 애플리케이션이 개발 환경에서는 빠르지만, 프로덕션 환경에서 데이터베이스 레코드 수가 증가함에 따라 느려지는 경우가 많습니다. 예를 들어, PostgreSQL에서 COUNT 쿼리는 항상 O(n) 복잡도를 가지며, 이는 테이블의 모든 행을 순회(sequential scan)해야 함을 의미합니다. Products.order("price desc").limit(1)나 User.where(hobby: "fishing")와 같은 일반적인 Rails 관용구도 인덱싱이 되어 있지 않으면 전체 테이블에 대한 순차 스캔이나 정렬 작업을 유발하여 성능 저하로 이어질 수 있습니다. 이러한 문제의 해결책은 바로 데이터베이스 인덱싱입니다. 인덱스를 사용하면 Ruby에서 해시 룩업(O(1))을 사용하는 것처럼 데이터베이스 쿼리 성능을 크게 향상시킬 수 있습니다.