Big O는 알고리즘을 어려워 보이게 만드는 수학 기호가 아니다

vx_developer·2026년 9월 15일

코테보다가

목록 보기

14/26

알고리즘을 처음 배울 때 Big O는 입력 크기가 증가할수록 실행 횟수가 어떻게 증가하는지 나타내는 표기법으로 배운다.

공연장의 좌석 목록에서 특정 좌석을 찾는 코드를 생각해보자.

function findSeat(seats, seatId) {
  for (const seat of seats) {
    if (seat.id === seatId) {
      return seat;
    }
  }

  return null;
}

좌석이 n개일 때 최악의 경우 모든 좌석을 확인해야 하므로 이 탐색을 O(n)이라고 표현한다.

반복문의 실행 횟수를 세고 O(1), O(n), O(n²)처럼 분류하는 연습은 알고리즘의 증가 방식을 이해하는 데 유용하다.

하지만 실제 예매 서비스에서는 Big O 기호만 보고 구현을 선택할 수 없다.

n은 한 공연장의 좌석 수인가, 전체 공연의 좌석 수인가?
좌석 데이터는 서버 메모리에 있는가, 데이터베이스에서 가져오는가?
좌석 하나를 확인할 때 단순 비교만 하는가, 가격 정책도 계산하는가?
한 사용자가 한 번 조회하는가, 수만 명이 동시에 조회하는가?
좌석 전체가 필요한가, 선택한 좌석 하나만 필요한가?
좌석 상태는 조회하는 동안에도 다른 사용자에 의해 바뀔 수 있는가?
더 낮은 Big O를 얻기 위해 추가할 인덱스와 캐시는 어떤 비용을 만드는가?
정확한 좌석 상태를 확인하기 위해 반드시 필요한 작업은 무엇인가?

Big O는 코드를 평가하는 점수가 아니다.

실제 서비스에서 Big O는 알고리즘을 수학적으로 꾸미는 기호가 아니라, 데이터와 요청이 커질 때 처리 비용이 어떤 방식으로 증가하는지 개발자와 제품 담당자가 함께 논의하기 위한 공통 언어다.

Big O는 실행 시간을 알려주지 않고 증가하는 모양을 알려준다

다음 두 함수는 모두 좌석 목록을 한 번 탐색한다.

function countAvailableSeats(seats) {
  let count = 0;

  for (const seat of seats) {
    if (seat.status === "AVAILABLE") {
      count += 1;
    }
  }

  return count;
}

이 함수는 메모리에 있는 좌석 상태를 읽고 숫자를 증가시킨다.

다음 코드도 좌석 수만큼 반복한다.

async function loadSeatPrices(seats) {
  const prices = [];

  for (const seat of seats) {
    const price =
      await pricingRepository.findBySeatId(
        seat.id
      );

    prices.push(price);
  }

  return prices;
}

두 함수는 좌석 수를 n이라고 할 때 모두 O(n)으로 표현할 수 있다.

하지만 실제 실행 시간은 크게 다르다.

첫 번째 함수는 메모리 비교만 수행한다. 두 번째 함수는 좌석마다 데이터베이스 조회를 기다린다.

Big O가 같은 이유는 작업 한 번의 비용이 같아서가 아니다. 입력 크기가 증가할 때 주요 작업 횟수가 같은 형태로 증가하기 때문이다.

좌석 수가 2배
→ 첫 번째 함수의 비교 횟수도 약 2배
→ 두 번째 함수의 데이터베이스 조회 횟수도 약 2배

Big O는 이 증가 관계를 설명한다.

몇 밀리초가 걸리는지 알려면 데이터베이스 위치, 네트워크 지연, 서버 성능과 실제 데이터 크기를 별도로 측정해야 한다.

상수와 작은 항을 생략하는 이유는 미래의 증가를 보기 위해서다

좌석을 처리하는 데 다음과 같은 작업이 필요하다고 생각해보자.

3n + 20

좌석마다 상태 확인, 가격 확인과 구역 확인을 한 번씩 실행하고, 요청 준비를 위해 고정된 작업 20번을 수행한다는 의미로 볼 수 있다.

Big O에서는 이를 O(n)이라고 표현한다.

O(3n + 20) → O(n)

상수 3과 고정된 값 20을 생략한다고 실제 비용이 사라지는 것은 아니다.

좌석이 10개라면 3n + 20에서 고정 비용도 큰 비중을 차지한다.

좌석이 100만 개라면 n에 따라 증가하는 부분이 훨씬 중요해진다.

비슷하게 다음 비용은 O(n²)으로 표현한다.

n² + 100n + 1000

입력이 작을 때는 100n이나 1000의 영향이 클 수 있다. 그러나 n이 계속 커지면 n² 항이 전체 증가를 주도한다.

Big O가 상수와 작은 항을 생략하는 이유는 현재 실행 시간을 정확히 표현하기 위해서가 아니다.

데이터가 충분히 커졌을 때 어떤 증가 방식이 시스템의 한계를 결정하는지 보기 위해서다.

따라서 다음 두 문장은 구분해야 한다.

O(n) 알고리즘이 지금 더 빠르다.
데이터가 커질수록 O(n) 알고리즘의 비용이 O(n²)보다 천천히 증가한다.

Big O가 직접 말해주는 것은 두 번째 문장이다.

기호보다 먼저 `n`이 현실에서 무엇인지 정해야 한다

예매 서비스에는 하나의 데이터 크기만 존재하지 않는다.

공연 수
공연장 수
공연별 좌석 수
사용자가 선택한 좌석 수
적용할 할인 규칙 수
대기열에 있는 사용자 수
동시에 들어오는 예매 요청 수
반환할 공연 목록 수

전체 좌석을 한 번 탐색하는 코드가 O(n)이라고 해도 n이 무엇인지에 따라 의미가 달라진다.

const seats =
  await seatRepository.findByEventId(
    eventId
  );

const availableSeats = seats.filter(
  (seat) =>
    seat.status === "AVAILABLE"
);

여기에서 n은 특정 공연의 좌석 수다.

다음 코드는 형태가 비슷하지만 처리 범위가 다르다.

const allSeats =
  await seatRepository.findAll();

const availableSeats = allSeats.filter(
  (seat) =>
    seat.eventId === eventId &&
    seat.status === "AVAILABLE"
);

여기에서 n은 서비스 전체 공연의 모든 좌석 수다.

두 코드 모두 배열을 한 번 순회하므로 O(n)이다. 그러나 한 공연의 500석을 확인하는 것과 전체 서비스의 5천만 석을 확인하는 것은 같은 설계가 아니다.

따라서 복잡도를 다음처럼 구체적으로 표현해야 한다.

한 공연에 포함된 좌석 수를 n이라고 할 때, 메모리에서 사용 가능한 좌석을 찾는 비용은 O(n)이다.

Big O는 기호만으로 의미를 갖지 않는다.

기호가 현실의 어떤 입력을 나타내며 그 입력이 어디까지 증가할 수 있는지 설명할 때 설계 언어가 된다.

증가 방식은 서비스가 감당할 수 있는 범위를 바꾼다

대표적인 증가 방식을 예매 서비스에 연결해보자.

Big O	예매 서비스의 예	데이터가 증가할 때
`O(1)`	좌석 ID로 메모리 맵 조회	입력 크기와 관계없이 비슷한 단계
`O(log n)`	정렬된 좌석 ID 범위를 좁혀 검색	데이터가 크게 늘어도 단계가 천천히 증가
`O(n)`	한 공연의 모든 좌석 상태 확인	좌석 수에 비례해 증가
`O(n log n)`	좌석 전체를 가격순으로 정렬	선형보다 빠르게 증가하지만 제곱보다는 느림
`O(n²)`	모든 좌석 쌍의 관계 비교	좌석 수가 늘면 비교가 매우 빠르게 증가
`O(2ⁿ)`	좌석 묶음의 모든 조합 확인	작은 입력 증가에도 경우의 수가 급격히 증가

좌석 수가 10배 증가할 때 대략적인 작업량은 다음과 같이 달라질 수 있다.

증가 방식	입력 100	입력 1,000
`n`	100	1,000
`n log₂ n`	약 664	약 9,966
`n²`	10,000	1,000,000
`2ⁿ`	현실적으로 매우 큼	계산 불가능한 수준

정확한 실행 시간을 보여주는 숫자는 아니다.

같은 작업 한 단위를 가정했을 때 입력 증가가 작업량에 미치는 차이를 보여준다.

좌석이 최대 20개라면 O(n²) 비교도 충분히 단순하고 빠를 수 있다. 좌석이 10만 개라면 같은 방법을 다시 검토해야 한다.

Big O는 특정 기호를 금지하기 위한 규칙이 아니다.

입력의 최대 크기와 증가 방식을 연결하여 어느 지점에서 현재 방법이 한계에 도달하는지 예상하는 도구다.

전체 데이터를 가져온 뒤 빠른 알고리즘을 써도 설계는 느릴 수 있다

선택한 좌석 하나를 ID로 찾기 위해 서버에서 Map을 사용할 수 있다.

const seats =
  await seatRepository.findAll();

const seatById = new Map(
  seats.map((seat) => [
    seat.id,
    seat,
  ])
);

const selectedSeat =
  seatById.get(request.body.seatId);

Map을 만든 뒤 좌석 조회는 평균적으로 O(1)에 가깝다.

그러나 조회 한 번을 위해 전체 좌석을 데이터베이스에서 가져오고 Map을 만드는 비용이 먼저 발생한다.

전체 좌석 조회: 데이터 크기에 따라 증가
Map 생성: O(n)
좌석 조회: 평균 O(1)

마지막 단계만 보면 빠르지만 요청 전체는 빠르지 않다.

필요한 좌석 하나를 저장소에서 직접 조회하는 편이 자연스럽다.

const selectedSeat =
  await seatRepository.findByIdForEvent({
    seatId: parseSeatId(
      request.body.seatId
    ),
    eventId: parseEventId(
      request.params.eventId
    ),
  });

이 코드는 외부 입력의 형식을 검증한 뒤 특정 공연에 속한 좌석 하나만 조회한다.

데이터베이스에는 조회 조건에 맞는 인덱스를 둘 수 있다.

CREATE UNIQUE INDEX
  seats_event_id_seat_id_idx
ON seats (event_id, id);

인덱스를 사용하면 데이터베이스가 전체 좌석을 순서대로 확인하지 않고 검색 범위를 줄일 수 있다.

다만 인덱스도 무료는 아니다.

별도의 저장 공간이 필요하다.
좌석을 생성하거나 변경할 때 인덱스도 갱신한다.
사용하지 않는 인덱스가 많으면 쓰기 비용이 증가한다.
조회 조건과 인덱스 순서가 맞지 않으면 기대한 효과를 얻지 못한다.

Big O는 서버 함수 하나만 평가하는 데 사용해서는 안 된다.

데이터베이스에서 데이터를 찾고, 서버로 옮기고, 계산하고, 응답으로 반환하는 전체 흐름에서 입력에 따라 증가하는 비용을 찾아야 한다.

하나의 요청과 서비스 전체의 비용은 다르다

크리스가 공연의 좌석 목록을 한 번 조회한다고 생각해보자.

한 요청이 좌석 500개를 처리하는 비용은 작을 수 있다.

하지만 인기 공연의 예매가 열리면 10만 명이 거의 동시에 같은 좌석을 조회할 수 있다.

요청 한 건당 좌석 500개
× 동시에 들어오는 요청 100,000건

한 요청의 알고리즘이 O(n)이라고 해도 전체 서비스는 요청 수에 비례한 비용까지 부담한다.

좌석 수를 n, 동시에 처리하는 요청 수를 r이라고 하면 단순화된 전체 작업량은 다음과 같이 볼 수 있다.

O(r × n)

실제로 모든 요청이 완전히 같은 순간에 실행되는 것은 아니지만, 이 표현은 두 종류의 증가가 시스템에 함께 영향을 준다는 사실을 보여준다.

여기에서 설계 질문이 달라진다.

좌석 전체를 매번 다시 조회해야 하는가?
변하지 않는 좌석 배치와 자주 바뀌는 판매 상태를 분리할 수 있는가?
응답에 실제로 필요한 필드만 반환하는가?
동시에 처리할 요청 수를 제한해야 하는가?
좌석 상태 갱신이 데이터베이스에 집중되지는 않는가?
읽기 캐시가 허용하는 최신성은 어느 정도인가?

Big O는 함수의 반복문을 설명하는 데서 끝나지 않는다.

서로 다른 입력 크기가 곱해지는 지점을 찾고 서비스 전체의 처리량을 논의하게 한다.

서로 다른 데이터 크기를 모두 `n`이라고 부르면 비용을 잘못 이해한다

두 명이 붙어 있는 좌석을 추천한다고 생각해보자.

사용 가능한 좌석 수를 n, 사용자가 요청한 좌석 수를 k라고 할 수 있다.

function findSeatGroup(
  availableSeats,
  requestedCount
) {
  for (
    let start = 0;
    start <=
      availableSeats.length -
        requestedCount;
    start += 1
  ) {
    const group = availableSeats.slice(
      start,
      start + requestedCount
    );

    if (isConsecutive(group)) {
      return group;
    }
  }

  return null;
}

시작 위치는 좌석 수에 따라 증가하고, 각 위치에서 최대 k개의 좌석을 확인한다.

따라서 비용은 다음과 같이 표현할 수 있다.

O(n × k)

사용자가 요청할 수 있는 좌석이 최대 4개로 제한되어 있다면 k는 매우 작은 값이다. 이 경우 실무적으로는 좌석 수에 비례하는 비용에 가깝게 동작할 수 있다.

그러나 단체 예매에서 k가 수천까지 증가할 수 있다면 별도로 고려해야 한다.

할인 계산에도 여러 입력이 생긴다.

function calculateBestPrice(
  seats,
  discountPolicies
) {
  for (const seat of seats) {
    for (const policy of discountPolicies) {
      evaluateDiscount(seat, policy);
    }
  }
}

좌석 수가 n, 할인 정책 수가 m이라면 비용은 O(n × m)이다.

n과 m을 모두 하나의 기호로 뭉뚱그려 O(n²)이라고 표현하면 현실의 증가 원인을 놓칠 수 있다.

좌석은 빠르게 증가하지만 할인 정책은 10개로 고정될 수 있다. 반대로 좌석 수는 작지만 제휴 할인 정책이 계속 늘어날 수도 있다.

여러 입력 크기를 구분하면 어떤 데이터를 제한하거나 사전 처리해야 하는지도 분명해진다.

가장 낮은 Big O가 언제나 가장 좋은 설계는 아니다

좌석 ID를 배열에서 한 번 찾는 방법은 O(n)이다.

function findSeatById(seats, seatId) {
  return seats.find(
    (seat) => seat.id === seatId
  );
}

좌석 ID를 키로 사용하는 Map을 만들면 이후 조회는 평균적으로 O(1)에 가깝다.

const seatById = new Map(
  seats.map((seat) => [
    seat.id,
    seat,
  ])
);

const seat = seatById.get(seatId);

그러나 Map 생성에는 O(n)의 시간과 추가 메모리가 필요하다.

좌석 20개에서 한 번만 조회한다면 배열 탐색이 단순하고 충분히 빠를 수 있다.

같은 좌석 목록에서 수천 번 조회한다면 Map을 한 번 만들고 재사용하는 편이 적절할 수 있다.

상황	고려할 수 있는 선택
작은 목록에서 한 번 조회	배열 선형 탐색
같은 목록에서 반복 조회	`Map` 사전 구성
좌석 상태가 계속 변경됨	`Map` 갱신 책임 확인
서버 메모리가 제한됨	추가 저장 비용 확인
원본이 데이터베이스에 있음	필요한 좌석만 인덱스로 조회
여러 서버가 같은 상태를 공유함	서버별 메모리 복사본의 최신성 검토

Big O가 더 낮더라도 초기 구성 비용, 메모리, 변경 동기화와 코드 복잡성이 커질 수 있다.

적절한 설계는 기호가 가장 작은 구현이 아니다.

서비스가 지원해야 하는 데이터 크기와 호출 빈도에서 충분한 성능을 내면서 정확성과 유지보수 비용을 감당할 수 있는 구현이다.

빠른 미리보기와 정확한 예매 확정은 같은 비용 기준을 사용하지 않는다

좌석 목록 화면에서는 사용 가능한 좌석을 빠르게 보여줘야 한다.

짧은 시간 동안 캐시된 좌석 상태를 사용할 수 있다.

const seatMap =
  await seatMapCache.get(eventId);

return {
  eventId,
  seats: seatMap,
  cachedAt: seatMap.cachedAt,
};

이 결과는 사용자가 선택할 후보를 보여주는 미리보기다.

그러나 크리스가 좌석을 선택한 뒤 결제를 진행할 때는 캐시된 상태만으로 확정할 수 없다.

다른 사용자가 같은 좌석을 먼저 예약했을 수 있기 때문이다.

const reservation =
  await seatRepository.reserveIfAvailable({
    eventId,
    seatId,
    userId: session.user.id,
    reservedAt: serverNow,
  });

저장소는 최신 상태가 AVAILABLE일 때만 좌석을 예약 상태로 변경해야 한다.

UPDATE seats
SET
  status = 'RESERVED',
  reserved_by = $3,
  reserved_at = $4
WHERE event_id = $1
  AND id = $2
  AND status = 'AVAILABLE'
RETURNING id, status, reserved_by;

이 쿼리는 변경 순간에도 좌석이 사용 가능한 경우에만 성공한다.

화면의 좌석 목록은 계산되거나 복제된 조회 데이터다. 좌석을 실제로 배정할 수 있는지에 대한 Source of Truth는 데이터베이스의 최신 상태다.

미리보기에서는 읽기 성능을 위해 캐시를 사용할 수 있다. 예매 확정에서는 동시성을 제어하기 위한 저장소 작업이 필요하다.

Big O만 보고 데이터베이스 확인을 제거하면 응답은 빨라질 수 있지만 같은 좌석이 여러 사용자에게 배정될 수 있다.

성능 판단은 기능의 책임에 따라 달라져야 한다.

외부 입력이 처리 비용을 결정한다면 반드시 제한해야 한다

예매 API가 사용자가 원하는 좌석 수를 받는다고 생각해보자.

const requestedCount = Number(
  request.query.count
);

const seats =
  await seatService.findGroup({
    eventId,
    requestedCount,
  });

정상적인 화면은 count=2나 count=4를 보낼 수 있다.

그러나 외부 사용자가 count=1000000을 보내면 큰 배열 생성, 긴 탐색이나 거대한 데이터베이스 요청을 유발할 수 있다.

숫자로 변환할 수 있다는 사실만으로는 충분하지 않다.

const requestedCount = Number(
  request.query.count
);

if (
  !Number.isInteger(requestedCount) ||
  requestedCount < 1 ||
  requestedCount > 10
) {
  throw new Error(
    "좌석 수는 1개 이상 10개 이하여야 한다."
  );
}

이 코드는 서비스가 지원하기로 한 좌석 수만 허용한다.

입력 상한은 단순한 형식 검증이 아니다.

한 요청이 사용할 수 있는 계산량, 데이터베이스 시간과 메모리를 제한하는 성능 규칙이자 시스템 보호 규칙이다.

Big O로 증가 방식을 알더라도 입력이 무제한이면 최대 비용을 예측하기 어렵다.

서비스가 책임질 입력 크기를 명시해야 복잡도 분석도 실제 의미를 갖는다.

Big O는 정확성을 포기하기 위한 근거가 아니다

좌석 예약에서 가장 빠른 응답만 중요하다면 서버 메모리에 있는 상태를 바로 변경할 수 있다.

if (seat.status === "AVAILABLE") {
  seat.status = "RESERVED";
  return {
    success: true,
  };
}

서버 한 대에서 요청 하나만 처리할 때는 동작할 수 있다.

하지만 서버가 여러 대이거나 같은 요청이 동시에 들어오면 각 서버가 서로 다른 좌석 상태를 보고 성공할 수 있다.

예매 서비스가 지켜야 하는 핵심 조건은 다음과 같다.

하나의 좌석은 같은 공연에서 한 사용자에게만 예약된다.
사용 가능한 좌석만 예약 상태로 변경할 수 있다.
예약에 성공했다는 응답은 저장된 예약 기록과 일치해야 한다.
결제 시간이 지나면 임시 예약은 해제되어야 한다.
같은 요청이 재시도되어도 예약이 중복 생성되어서는 안 된다.
다른 사용자의 예약을 변경할 수 없어야 한다.

이 조건을 지키기 위해 고유 제약, 조건부 갱신과 트랜잭션이 필요할 수 있다.

CREATE UNIQUE INDEX
  one_active_reservation_per_seat
ON reservations (event_id, seat_id)
WHERE status IN ('HELD', 'CONFIRMED');

이 제약은 같은 공연의 같은 좌석에 활성 예약이 여러 개 생성되는 것을 막는다.

추가 확인과 저장소 제어는 비용을 만든다. 그래도 비즈니스 규칙을 지키기 위해 제거할 수 없는 비용이다.

Big O는 정확하지 않은 알고리즘을 더 빠르게 만드는 도구가 아니다.

올바른 결과를 보장하는 범위 안에서 증가 비용을 관리하는 도구다.

복잡도 분석과 실제 측정은 함께 사용해야 한다

좌석 추천 API가 느려졌다고 생각해보자.

코드에 중첩 반복문이 있다는 이유만으로 그 부분이 실제 병목이라고 단정할 수는 없다.

다음 구간을 나누어 측정할 수 있다.

const startedAt = performance.now();

const seats =
  await seatRepository.findAvailable(
    eventId
  );

const loadedAt = performance.now();

const recommendation =
  recommendSeatGroup(
    seats,
    requestedCount
  );

const completedAt = performance.now();

logger.info("Seat recommendation timing", {
  seatCount: seats.length,
  queryMs: loadedAt - startedAt,
  algorithmMs:
    completedAt - loadedAt,
});

이 코드는 조회한 좌석 수, 데이터베이스 조회 시간과 추천 계산 시간을 함께 기록한다.

측정 결과가 다음과 같을 수 있다.

구간	측정 결과
인증과 권한 확인	15ms
좌석 데이터 조회	700ms
좌석 추천 계산	12ms
응답 변환	8ms
네트워크 전송	150ms

이 상황에서 추천 알고리즘의 반복문을 미세하게 줄여도 사용자 경험은 거의 달라지지 않는다.

조회 범위, 인덱스와 응답 데이터 크기를 먼저 개선해야 한다.

반대로 현재 좌석이 100개라 계산 시간이 1밀리초밖에 걸리지 않더라도 알고리즘이 O(n²)이고 향후 10만 석 규모를 지원해야 한다면 성장 위험을 미리 발견할 수 있다.

두 접근은 서로 다른 질문에 답한다.

Big O는 데이터가 증가할 때 어디가 위험해지는지 설명한다.
측정은 현재 환경에서 실제 시간이 어디에 쓰이는지 보여준다.
부하 테스트는 많은 요청이 동시에 들어올 때 한계를 확인한다.
운영 지표는 실제 사용량이 설계 가정과 달라지는 순간을 알려준다.

복잡도로 미래를 예상하고 측정으로 현재의 우선순위를 결정해야 한다.

Big O를 공통 언어로 사용하려면 조건까지 함께 말해야 한다

개발 회의에서 다음처럼 말할 수 있다.

이 API는 O(n)이다.

틀린 말은 아닐 수 있지만 설계 판단에 필요한 정보가 부족하다.

다음처럼 구체적으로 표현하는 편이 낫다.

한 공연의 조회 대상 좌석 수를 n이라고 할 때, 서버의 추천 계산은 O(n)이다. 현재 최대 5만 석을 지원하며, 데이터베이스에서 사용 가능한 좌석만 조회한 뒤 실행한다. 좌석 조회는 별도로 측정해야 한다.

또는 다음과 같이 말할 수 있다.

좌석 수를 n, 요청한 연속 좌석 수를 k라고 할 때 현재 탐색은 O(n × k)다. k는 API에서 최대 10으로 제한하므로 주요 증가 요인은 n이다.

이 설명에는 다음 정보가 포함된다.

입력 크기가 무엇인지
입력의 최대 범위가 얼마인지
분석에 포함한 작업이 무엇인지
제한된 값이 무엇인지
별도로 측정해야 할 비용이 무엇인지

Big O를 공통 언어로 사용한다는 것은 기호만 말하는 일이 아니다.

같은 가정과 데이터 범위를 공유하여 설계의 한계를 함께 판단하는 일이다.

서비스가 감당할 수 있는 범위를 숫자로 정해야 한다

“좌석 조회가 빨라야 한다”는 요구사항만으로는 현재 알고리즘이 충분한지 판단하기 어렵다.

측정 가능한 목표로 바꿔야 한다.

항목	목표 예시
공연당 최대 좌석 수	50,000석
한 번에 반환할 좌석 수	최대 500개
사용자가 선택할 수 있는 좌석 수	최대 10개
일반적인 좌석 조회 응답	300ms 이내
상위 지연 요청	800ms 이내
예매 시작 시 최대 요청량	초당 5,000건
좌석 중복 확정	0건
임시 예약 만료 처리	만료 후 1분 이내

이 숫자는 모든 예매 서비스에 동일하게 적용되는 기준이 아니다.

공연 규모, 사용자 경험, 인프라 비용과 비즈니스 위험에 따라 정해야 한다.

목표가 있으면 Big O를 실제 결정에 연결할 수 있다.

선형 탐색으로 충분한가?
전체 좌석 대신 특정 구역만 조회해야 하는가?
전체 정렬 대신 필요한 좌석 몇 개만 선택할 수 있는가?
읽기 인덱스나 사전 계산 구조가 필요한가?
캐시가 허용할 수 있는 상태 지연은 얼마인가?
최대 요청량에서 데이터베이스가 조건부 갱신을 감당할 수 있는가?
어느 데이터 크기에서 현재 구조를 다시 검토해야 하는가?

가장 낮은 Big O를 얻는 것이 목표가 아니다.

서비스가 약속한 범위 안에서 처리 시간, 정확성과 비용을 예측할 수 있게 만드는 것이 목표다.

Big O를 설계 판단에 사용할 때 물어봐야 할 질문

알고리즘과 서비스 구조를 검토할 때 다음 질문을 사용할 수 있다.

Big O에서 사용하는 n은 현실의 어떤 데이터를 의미하는가?
한 공연의 좌석 수와 전체 서비스 좌석 수를 구분했는가?
입력 크기가 여러 개라면 각각 다른 기호로 표현했는가?
현재 평균 입력 크기는 얼마인가?
서비스가 정상적으로 지원할 최대 입력 크기는 얼마인가?
입력이 두 배, 열 배가 될 때 작업량은 어떻게 증가하는가?
현재 Big O에서 생략한 상수 작업은 실제로 얼마나 무거운가?
반복 한 번 안에서 데이터베이스나 네트워크 요청을 실행하는가?
분석 대상은 서버 계산만인가, 데이터 조회와 이동도 포함하는가?
전체 데이터를 가져온 뒤 작은 부분만 사용하고 있지는 않은가?
저장소에서 먼저 탐색 범위를 줄일 수 있는가?
필요한 결과는 전체 목록인가, 일부 목록이나 하나의 값인가?
전체 정렬이나 전체 조합 계산이 정말 필요한가?
같은 데이터를 반복해서 조회하거나 계산하는가?
사전 계산 구조는 몇 번 재사용되는가?
더 낮은 조회 비용을 위해 필요한 메모리와 갱신 비용은 얼마인가?
인덱스가 실제 조회 조건과 맞는가?
인덱스가 쓰기 성능과 저장 공간에 미치는 영향을 확인했는가?
요청 한 건의 비용뿐 아니라 동시 요청 수도 고려했는가?
외부 사용자가 입력 크기를 임의로 늘릴 수 있는가?
페이지 크기와 선택 개수에 안전한 상한을 두었는가?
캐시된 조회 데이터와 최신 원본 상태를 구분했는가?
최종 상태 변경의 Source of Truth는 어디에 있는가?
성능 때문에 권한, 검증이나 동시성 제어를 제거하지 않았는가?
Big O가 더 낮은 방법의 초기 비용과 코드 복잡성도 비교했는가?
현재 데이터에서 실제 병목을 측정했는가?
향후 데이터 규모에서도 같은 설계가 충분한지 예측했는가?
응답 시간, 처리량과 정확성 목표가 숫자로 정의되어 있는가?
현재 가정이 깨지는 시점을 알려줄 운영 지표가 있는가?
팀이 같은 입력 범위와 가정을 기준으로 복잡도를 이야기하고 있는가?

이 질문은 모든 코드를 가장 복잡한 방식으로 최적화하기 위한 목록이 아니다.

데이터가 작고 호출 횟수가 적다면 단순한 구현이 가장 좋은 선택일 수 있다. 중요한 것은 왜 현재 방법이 충분하며 어느 조건에서 다시 검토해야 하는지 설명할 수 있는가이다.

Big O는 서비스의 성장 한계를 함께 말하게 한다

Big O는 실행 시간을 직접 알려주지 않는다.

O(n)이 항상 빠르다는 뜻도 아니고, O(n²)을 언제나 사용하면 안 된다는 뜻도 아니다.

Big O가 알려주는 것은 입력이 커질 때 비용이 증가하는 방향이다.

이를 실제 서비스에 사용하려면 다음 범위를 함께 살펴봐야 한다.

입력 크기가 현실의 어떤 데이터를 뜻하는지 정의한다.
평균값과 지원할 최댓값을 구분한다.
여러 입력 크기가 함께 증가하는지 확인한다.
서버 계산뿐 아니라 저장소 조회와 데이터 이동을 살펴본다.
한 요청의 비용과 전체 요청량을 연결한다.
읽기 속도를 높이는 선택이 쓰기와 저장 공간에 만드는 비용을 확인한다.
캐시된 계산 데이터와 최신 원본 상태를 구분한다.
정확성과 동시성을 위해 필요한 비용은 유지한다.
현재 병목은 측정하고 미래의 위험은 증가 방식으로 예측한다.
서비스 목표 안에서 충분히 단순한 방법을 선택한다.

Big O는 알고리즘의 우열을 한 글자로 결정하는 기호가 아니다. 입력이 커질 때 서비스의 계산, 저장과 통신 비용이 어떻게 변하는지 같은 기준으로 설명하고, 현재 설계가 책임질 수 있는 데이터 규모의 경계를 합의하는 언어다.

좌석이 20개라면 배열을 한 번 탐색하는 방법이 충분하다.

공연당 좌석이 수만 개라면 조회 범위와 정렬 비용을 살펴봐야 한다. 예매 시작과 함께 요청이 수천 배로 증가한다면 한 요청의 비용을 전체 처리량과 연결해야 한다. 좌석 확정에서는 더 빠른 캐시보다 최신 상태와 동시성 제어가 중요하다.

Big O를 안다는 것은 O(n)과 O(log n)을 구분하는 데서 끝나지 않는다.

현재 데이터에서 단순한 방법으로 충분한지, 데이터가 얼마나 증가하면 설계를 바꿔야 하는지, 그 선택이 다른 책임에 어떤 비용을 만드는지 설명할 수 있어야 한다.

다음 글에서는 O(1)이 언제나 빠르다는 뜻이 아니며, 데이터베이스 조회, 네트워크 호출과 캐시 접근처럼 한 단계로 보이는 작업의 실제 비용을 어떻게 판단해야 하는지 살펴본다.

vx_developer

Vision eXperience Developer

이전 포스트

시간 복잡도는 코드가 실행되는 시간을 계산하는 공식이 아니다

다음 포스트

Big O는 알고리즘을 어려워 보이게 만드는 수학 기호가 아니다

코테보다가

Big O는 실행 시간을 알려주지 않고 증가하는 모양을 알려준다

상수와 작은 항을 생략하는 이유는 미래의 증가를 보기 위해서다

기호보다 먼저 `n`이 현실에서 무엇인지 정해야 한다

증가 방식은 서비스가 감당할 수 있는 범위를 바꾼다

전체 데이터를 가져온 뒤 빠른 알고리즘을 써도 설계는 느릴 수 있다

하나의 요청과 서비스 전체의 비용은 다르다

서로 다른 데이터 크기를 모두 `n`이라고 부르면 비용을 잘못 이해한다

가장 낮은 Big O가 언제나 가장 좋은 설계는 아니다

빠른 미리보기와 정확한 예매 확정은 같은 비용 기준을 사용하지 않는다

외부 입력이 처리 비용을 결정한다면 반드시 제한해야 한다

Big O는 정확성을 포기하기 위한 근거가 아니다

복잡도 분석과 실제 측정은 함께 사용해야 한다

Big O를 공통 언어로 사용하려면 조건까지 함께 말해야 한다

서비스가 감당할 수 있는 범위를 숫자로 정해야 한다

Big O를 설계 판단에 사용할 때 물어봐야 할 질문

Big O는 서비스의 성장 한계를 함께 말하게 한다

시간 복잡도는 코드가 실행되는 시간을 계산하는 공식이 아니다

O(1)은 언제나 빠르다는 뜻이 아니다

0개의 댓글

Big O는 알고리즘을 어려워 보이게 만드는 수학 기호가 아니다

코테보다가

Big O는 실행 시간을 알려주지 않고 증가하는 모양을 알려준다

상수와 작은 항을 생략하는 이유는 미래의 증가를 보기 위해서다

기호보다 먼저 n이 현실에서 무엇인지 정해야 한다

증가 방식은 서비스가 감당할 수 있는 범위를 바꾼다

전체 데이터를 가져온 뒤 빠른 알고리즘을 써도 설계는 느릴 수 있다

하나의 요청과 서비스 전체의 비용은 다르다

서로 다른 데이터 크기를 모두 n이라고 부르면 비용을 잘못 이해한다

가장 낮은 Big O가 언제나 가장 좋은 설계는 아니다

빠른 미리보기와 정확한 예매 확정은 같은 비용 기준을 사용하지 않는다

외부 입력이 처리 비용을 결정한다면 반드시 제한해야 한다

Big O는 정확성을 포기하기 위한 근거가 아니다

복잡도 분석과 실제 측정은 함께 사용해야 한다

Big O를 공통 언어로 사용하려면 조건까지 함께 말해야 한다

서비스가 감당할 수 있는 범위를 숫자로 정해야 한다

Big O를 설계 판단에 사용할 때 물어봐야 할 질문

Big O는 서비스의 성장 한계를 함께 말하게 한다

시간 복잡도는 코드가 실행되는 시간을 계산하는 공식이 아니다

O(1)은 언제나 빠르다는 뜻이 아니다

0개의 댓글

기호보다 먼저 `n`이 현실에서 무엇인지 정해야 한다

서로 다른 데이터 크기를 모두 `n`이라고 부르면 비용을 잘못 이해한다