빅-O 표기법이란?언급된 바와 같이, 빅-O 표기법은 코드의 성능이 처리할 데이터 양에 따라 어떻게 달라지는지 설명하는 방법입니다. 주로 실행 시간(시간 복잡도)에 초점을 맞추지만, 메모리 사용량(공간 복잡도)에도 적용됩니다.

일반적인 빅-O 복잡도 유형다음은 데이터 스케일에 따른 코드 성능 변화를 나타내는 일반적인 빅-O 복잡도 유형입니다.:* O(1) - 상수 시간 복잡도 (Constant time complexity): 데이터셋 크기에 무관하게 속도가 일정합니다. (예: Ruby의 Hash 룩업). 가장 이상적인 성능을 나타냅니다.

• O(log n) - 로그 시간 복잡도 (Logarithmic complexity): 데이터가 10배 증가해도 시간은 약 2배만 증가합니다. (예: 이진 탐색, Ruby의 `Array

bsearch`). 매우 효율적입니다.

• O(n) - 선형 시간 복잡도 (Linear time complexity): 데이터가 10배 증가하면 시간도 10배 증가합니다. (예: 선형 탐색, Ruby의 `Array

find`, 배열 순회).

• O(n log n) - 로그선형 시간 복잡도 (Loglinear complexity): 데이터가 10배 증가하면 시간이 약 20배 증가합니다. (예: 퀵 정렬, Ruby의 `Array

sort` 평균 복잡도).

• O(n^2) - 다항 시간 복잡도 (Polynomial time complexity): 데이터가 10배 증가하면 시간이 100배 증가합니다. (예: 중첩 루프). 대규모 데이터셋에서 매우 비효율적입니다.
• O(2^n) - 지수 시간 복잡도 (Exponential time complexity): 데이터가 조금만 증가해도 시간이 기하급수적으로 증가합니다. 최악의 성능을 나타냅니다.

점근적 복잡도빅-O 표기법은 입력 크기가 무한대로 커질 때 함수의 동작(점근적 성장)에만 관심을 가집니다. 즉, f(x) = x^2 + 4x와 같은 함수에서 x가 매우 커지면 4x 항은 x^2에 비해 무시할 수 있으므로, f(x)는 x^2에 거의 동등하다고 간주합니다. 이는 상수 계수나 작은 항을 무시하고 가장 큰 영향을 미치는 항만 고려한다는 의미입니다.

Ruby 코드와 빅-O의 연관성

• O(1) 예시: Hash 룩업은 해시 크기에 관계없이 일정한 시간을 소요합니다. hash_with_100_items[:a], hash_with_10000_items[:a] 모두 유사한 시간을 가집니다.
• O(n) 예시: `Array

find`는 배열 항목 수에 비례하여 시간이 증가합니다. 100개 항목의 배열은 1개 항목 배열보다 100배 더 오래 걸립니다. 배열을 반복하는 많은 코드가 O(n) 패턴을 따릅니다.

• O(n^2) 예시: 중첩 루프는 전형적인 O(n^2) 복잡도를 가집니다. 루프 수준이 증가할수록 복잡도는 O(n^3), O(n^4) 등으로 기하급수적으로 증가합니다.

데이터베이스에 미치는 영향새로운 웹 애플리케이션이 개발 환경에서는 빠르지만 프로덕션 환경에서 느려지는 주된 원인은 데이터베이스 레코드 수가 증가함에 따라 코드가 비효율적인 O(n) 또는 그 이상의 작업을 요청하기 때문입니다. 예를 들어, PostgreSQL에서 Users.count 쿼리는 기본적으로 모든 행을 순차 스캔(O(n))합니다. 또한 Products.order("price desc").limit(1)나 인덱스가 없는 User.where(hobby: "fishing")와 같은 쿼리도 전체 테이블 스캔이나 정렬(O(n log n) 또는 O(n^2))을 유발할 수 있습니다. 이러한 문제의 해결책은 데이터베이스 인덱싱을 활용하여 O(1)에 가까운 룩업 성능을 확보하는 것입니다.