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

알고리즘을 처음 배울 때 시간 복잡도는 입력 크기에 따라 코드의 실행 횟수가 어떻게 증가하는지 나타내는 개념으로 배운다.

쿠폰 목록에서 사용할 수 있는 쿠폰을 찾는 코드를 생각해보자.

function findAvailableCoupons(coupons, now) {
  const availableCoupons = [];

  for (const coupon of coupons) {
    if (
      coupon.status === "ACTIVE" &&
      now < coupon.expiresAt
    ) {
      availableCoupons.push(coupon);
    }
  }

  return availableCoupons;
}

쿠폰이 n개라면 반복문은 최대 n번 실행된다.

따라서 이 알고리즘의 시간 복잡도를 O(n)이라고 표현할 수 있다.

입력 데이터가 증가할 때 반복 횟수가 어떻게 달라지는지 이해하고 여러 알고리즘을 비교하기에는 유용한 설명이다.

하지만 O(n)이라는 표기만으로 실제 쿠폰 화면이 몇 밀리초 안에 열리는지는 알 수 없다.

• 쿠폰은 브라우저, 서버 메모리와 데이터베이스 중 어디에 있는가?
• n은 한 사용자의 쿠폰 수인가, 서비스 전체 쿠폰 수인가?
• 쿠폰 하나를 확인할 때 메모리의 값만 읽는가?
• 각 쿠폰의 캠페인 정보를 데이터베이스에서 다시 조회하는가?
• 할인 가능 여부를 판단하기 위해 모든 주문 상품도 확인하는가?
• 화면에는 전체 결과가 필요한가, 20개만 필요한가?
• 같은 계산은 초당 몇 번 실행되는가?
• 결과를 만드는 동안 네트워크로 얼마나 많은 데이터를 전송하는가?
• 쿠폰이 동시에 사용되면 최신 상태를 다시 검증해야 하는가?

코드의 반복문만 세면 중요한 비용을 놓칠 수 있다.

실제 서비스에서 시간 복잡도는 실행 시간을 맞히는 공식이 아니라, 데이터와 요청이 증가할 때 어떤 작업의 비용이 얼마나 빠르게 커지는지 예측하여 현재 설계가 감당할 수 있는 범위를 판단하는 도구다.

O(n)은 몇 초가 걸린다는 뜻이 아니다

두 함수가 모두 쿠폰을 한 번씩 확인한다고 생각해보자.

function countActiveCoupons(coupons) {
  let count = 0;

  for (const coupon of coupons) {
    if (coupon.status === "ACTIVE") {
      count += 1;
    }
  }

  return count;
}

이 함수는 각 쿠폰의 메모리 값을 읽고 활성 상태의 개수를 센다.

다음 함수도 반복문은 n번 실행한다.

async function loadCouponCampaigns(coupons) {
  const campaigns = [];

  for (const coupon of coupons) {
    const campaign =
      await campaignRepository.findById(
        coupon.campaignId
      );

    campaigns.push(campaign);
  }

  return campaigns;
}

하지만 두 번째 함수는 쿠폰마다 데이터베이스 조회를 실행한다.

두 코드 모두 반복 횟수만 보면 O(n)이다. 실제 비용은 크게 다르다.

작업	쿠폰 하나당 발생하는 일
활성 쿠폰 개수 계산	메모리 값 비교와 숫자 증가
캠페인 개별 조회	데이터베이스 연결, 검색과 결과 전송
외부 제휴사 상태 확인	네트워크 요청과 외부 응답 대기
쿠폰 이미지 처리	파일 읽기와 이미지 변환
상품별 적용 가능 여부 확인	주문 상품 목록 추가 탐색

시간 복잡도는 입력 증가에 따른 비용의 모양을 보여준다. 각 작업 한 번의 실제 비용까지 알려주지는 않는다.

실행 시간은 대략 다음 요소의 영향을 함께 받는다.

전체 비용
≈ 실행 횟수
× 작업 한 번의 비용
+ 데이터 이동과 대기 비용

O(n)은 실행 시간이 정확히 선형으로 몇 밀리초 증가한다고 보장하지 않는다.

데이터가 두 배가 되었을 때 주요 작업도 대체로 두 배까지 늘어날 수 있다는 증가 경향을 보여준다.

입력 크기 n이 무엇인지 설명하지 않으면 복잡도도 모호하다

“이 함수는 O(n)이다”라는 말만으로는 부족하다.

n이 무엇을 의미하는지 먼저 정의해야 한다.

쿠폰 서비스에는 여러 크기의 데이터가 있다.

• 전체 사용자 수
• 서비스에 발행된 전체 쿠폰 수
• 한 사용자가 보유한 쿠폰 수
• 한 주문에 포함된 상품 수
• 쿠폰 하나가 적용되는 상품 수
• 동시에 들어오는 요청 수
• 한 번에 반환하는 결과 수

한 사용자가 보유한 쿠폰만 확인한다면 n은 사용자 쿠폰 수다.

const coupons =
  await couponRepository.findByUserId(
    currentUser.id
  );

return findAvailableCoupons(
  coupons,
  serverNow
);

반대로 전체 쿠폰을 조회한 뒤 사용자의 쿠폰을 찾는다면 n은 서비스 전체 쿠폰 수가 된다.

const coupons =
  await couponRepository.findAll();

return coupons.filter(
  (coupon) =>
    coupon.recipientId === currentUser.id
);

두 구현 모두 배열을 한 번 탐색하므로 O(n)이라고 표현할 수 있다.

하지만 첫 번째 구현의 n은 크리스가 보유한 쿠폰 수이고, 두 번째 구현의 n은 모든 사용자의 쿠폰 수다.

같은 복잡도 표기라도 입력의 범위가 다르면 처리 비용은 전혀 달라진다.

따라서 다음처럼 말해야 설계 판단에 도움이 된다.

사용자 한 명이 보유한 쿠폰 수를 n이라고 할 때, 사용 가능한 쿠폰을 찾는 계산은 O(n)이다.

복잡도를 말할 때는 기호보다 먼저 그 기호가 현실의 어떤 데이터를 뜻하는지 밝혀야 한다.

현실의 문제에는 입력 크기가 하나만 있지 않다

쿠폰이 현재 주문의 상품에 적용되는지 확인한다고 생각해보자.

다음 코드는 각 쿠폰마다 모든 주문 상품을 확인한다.

function findApplicableCoupons(
  coupons,
  orderItems
) {
  return coupons.filter((coupon) =>
    orderItems.some((item) =>
      coupon.productIds.includes(item.productId)
    )
  );
}

쿠폰 수를 n, 주문 상품 수를 m, 쿠폰 하나의 대상 상품 수를 p라고 하면 비용은 단순한 O(n)이 아니다.

각 쿠폰마다 주문 상품을 확인하고, 다시 쿠폰의 대상 상품 목록을 확인할 수 있다.

O(n × m × p)

쿠폰 10개, 주문 상품 5개와 대상 상품 20개라면 큰 문제가 아닐 수 있다.

하지만 쿠폰 1만 개, 주문 상품 100개와 대상 상품 1,000개라면 같은 코드의 비용은 빠르게 커진다.

쿠폰의 대상 상품 ID를 Set으로 바꾸면 반복적인 탐색을 줄일 수 있다.

function buildApplicableProductSet(coupon) {
  return new Set(coupon.productIds);
}

function appliesToOrder(
  applicableProductIds,
  orderItems
) {
  return orderItems.some((item) =>
    applicableProductIds.has(item.productId)
  );
}

Set을 만드는 데는 쿠폰당 O(p)의 사전 작업이 필요하다.

이후 상품 ID 하나가 포함되어 있는지 확인하는 평균 비용은 훨씬 작아진다. 같은 쿠폰을 여러 주문에서 반복해서 검사한다면 사전 처리 비용을 나누어 부담할 수 있다.

여기에서 중요한 질문은 “배열과 Set 중 무엇이 더 빠른가?”가 아니다.

• 쿠폰 하나를 몇 번 조회하는가?
• 대상 상품 목록은 얼마나 자주 변경되는가?
• 사전 계산한 구조를 어디에 저장할 것인가?
• 추가 메모리와 갱신 비용을 감당할 수 있는가?

시간 복잡도를 분석하면 반복 비용이 커지는 지점을 찾을 수 있다. 실제 설계는 데이터의 변경 주기와 저장 위치까지 고려해서 결정해야 한다.

배열을 한 번 순회해도 데이터를 가져오는 과정은 훨씬 클 수 있다

서버가 쿠폰 20개를 필터링하는 데 걸리는 시간은 매우 짧을 수 있다.

그런데 데이터베이스에서 서비스 전체 쿠폰 1,000만 개를 가져온 뒤 필터링한다면 문제는 반복문의 속도가 아니다.

const allCoupons =
  await couponRepository.findAll();

const userCoupons = allCoupons.filter(
  (coupon) =>
    coupon.recipientId === currentUser.id &&
    coupon.status === "ACTIVE"
);

배열 필터링은 O(n)이다.

하지만 그 전에 데이터베이스가 모든 행을 읽고 서버로 전송하며 서버가 거대한 배열을 메모리에 만들어야 한다.

사용자와 상태를 기준으로 저장소에서 필요한 데이터만 조회해야 한다.

SELECT
  id,
  title,
  expires_at,
  discount_type,
  discount_value
FROM coupons
WHERE recipient_id = $1
  AND status = 'ACTIVE'
  AND expires_at > $2
ORDER BY expires_at ASC
LIMIT 20;

이 쿼리는 현재 사용자의 활성 쿠폰 중 필요한 20개만 반환한다.

적절한 인덱스가 있다면 데이터베이스는 전체 쿠폰을 확인하지 않고 검색 범위를 줄일 수 있다.

CREATE INDEX coupons_user_status_expiry_idx
ON coupons (
  recipient_id,
  status,
  expires_at
);

인덱스는 사용자, 상태와 만료 시각을 기준으로 관련 데이터에 더 빠르게 접근하도록 돕는다.

그 대신 다음 비용이 추가된다.

• 인덱스를 저장할 공간이 필요하다.
• 쿠폰을 발행하거나 수정할 때 인덱스도 갱신해야 한다.
• 사용하지 않는 인덱스가 많으면 쓰기 비용이 커진다.

시간 복잡도를 줄이는 선택은 종종 저장 공간과 변경 비용을 늘린다.

따라서 읽기 알고리즘만 보지 말고 쿠폰이 생성되고 변경되고 조회되는 전체 생명주기를 함께 봐야 한다.

여러 번 이어진 O(n)은 여전히 O(n)이지만 비용은 사라지지 않는다

쿠폰을 필터링하고 할인 금액을 계산한 뒤 정렬할 수 있다.

const recommendations = coupons
  .filter((coupon) =>
    isAvailable(coupon, serverNow)
  )
  .map((coupon) => ({
    coupon,
    discountAmount:
      calculateDiscount(coupon, order),
  }))
  .filter(
    (candidate) =>
      candidate.discountAmount > 0
  )
  .sort(
    (first, second) =>
      second.discountAmount -
      first.discountAmount
  );

첫 번째 필터링은 O(n), 변환도 O(n), 두 번째 필터링도 O(n)이다.

이 세 단계를 합치면 다음과 같다.

O(n) + O(n) + O(n) = O(3n)

복잡도에서는 상수를 생략하므로 선형 단계들은 O(n)으로 표현한다.

하지만 실제 실행에서 세 번의 순회와 중간 배열 생성 비용이 사라지는 것은 아니다.

마지막 정렬은 후보가 k개라면 일반적으로 O(k log k)의 비용이 든다.

따라서 전체 증가 경향은 다음처럼 볼 수 있다.

O(n + k log k)

한 화면에 쿠폰 10개를 처리한다면 현재 코드는 읽기 쉽고 충분히 빠를 수 있다.

데이터가 수십만 개이고 요청이 자주 실행된다면 중간 배열과 전체 정렬 비용을 살펴봐야 한다.

가장 큰 할인 쿠폰 하나만 필요하다면 전체 순서를 만들 필요가 없다.

function findBestCoupon(
  coupons,
  order,
  now
) {
  let best = null;

  for (const coupon of coupons) {
    if (!isAvailable(coupon, now)) {
      continue;
    }

    const discountAmount =
      calculateDiscount(coupon, order);

    if (
      best === null ||
      discountAmount >
        best.discountAmount
    ) {
      best = {
        coupon,
        discountAmount,
      };
    }
  }

  return best;
}

이 코드는 모든 쿠폰을 한 번 확인하면서 현재까지의 최선만 유지한다.

전체 정렬 없이 O(n)의 탐색과 일정한 크기의 추가 상태로 결과 하나를 만든다.

다만 전체 순위가 필요하다면 정렬을 제거할 수 없다.

성능 개선은 문법을 짧게 바꾸는 일이 아니라 필요한 출력이 무엇인지 다시 확인하는 일에서 시작한다.

입력이 두 배가 될 때 무엇이 증가하는지 생각해야 한다

시간 복잡도는 현재 실행 시간을 설명하기보다 미래의 증가를 예상하는 데 더 유용하다.

쿠폰 수에 따른 작업 횟수를 단순화해보자.

쿠폰 수 n	선형 탐색 n	전체 쌍 비교 n²
10	10	100
100	100	10,000
1,000	1,000	1,000,000
10,000	10,000	100,000,000

선형 탐색은 쿠폰 수가 10배가 되면 작업도 약 10배 증가한다.

모든 쿠폰 쌍을 비교하는 방법은 쿠폰 수가 10배가 되면 작업이 약 100배 증가한다.

예를 들어 함께 사용할 수 없는 쿠폰 조합을 모두 비교할 수 있다.

function findConflicts(coupons) {
  const conflicts = [];

  for (
    let first = 0;
    first < coupons.length;
    first += 1
  ) {
    for (
      let second = first + 1;
      second < coupons.length;
      second += 1
    ) {
      if (
        cannotStack(
          coupons[first],
          coupons[second]
        )
      ) {
        conflicts.push([
          coupons[first].id,
          coupons[second].id,
        ]);
      }
    }
  }

  return conflicts;
}

이 코드는 각 쿠폰을 다른 모든 쿠폰과 비교하므로 쿠폰 수가 증가할수록 비교 횟수가 빠르게 커진다.

현재 사용자가 쿠폰을 최대 5개만 보유한다면 단순하고 안전한 선택일 수 있다.

하지만 제휴사 계정이 쿠폰을 10만 개까지 관리한다면 같은 방법은 사용할 수 없다.

시간 복잡도는 O(n²)이라는 기호를 보고 무조건 코드를 거부하게 하는 개념이 아니다.

지원해야 하는 최대 입력에서 작업량이 어느 정도까지 증가하는지 예상하게 하는 기준이다.

평균 데이터만 보면 서비스의 한계를 놓칠 수 있다

쿠폰 서비스에서 사용자는 평균 12개의 쿠폰을 보유할 수 있다.

이 평균만 보면 모든 쿠폰을 메모리에서 탐색해도 충분해 보인다.

하지만 실제 분포는 다음과 같을 수 있다.

사용자 유형	보유 쿠폰 수
신규 사용자	0
일반 사용자	5~20
이벤트 참여 사용자	500
장기 이용 사용자	10,000
제휴사 테스트 계정	100,000

평균값은 대부분의 요청을 이해하는 데 도움이 된다.

그러나 어떤 범위까지 정상적인 사용으로 지원할 것인지는 최댓값과 상위 사용자 분포를 기준으로 따로 결정해야 한다.

시간 복잡도를 분석할 때는 다음 값을 구분해야 한다.

• 평균 입력 크기
• 대부분의 사용자가 속하는 입력 크기
• 상위 1% 사용자의 입력 크기
• 현재 관찰된 최댓값
• 서비스가 공식적으로 지원할 최댓값
• 잘못된 요청으로 들어올 수 있는 크기

외부 사용자가 조회 개수를 직접 지정할 수 있다면 입력 크기를 제한해야 한다.

const requestedLimit = Number(
  request.query.limit
);

if (!Number.isInteger(requestedLimit)) {
  throw new Error(
    "조회 개수는 정수여야 한다."
  );
}

const limit = Math.min(
  Math.max(requestedLimit, 1),
  100
);

이 코드는 한 요청이 가져올 수 있는 쿠폰 수를 1개 이상 100개 이하로 제한한다.

입력의 최대 크기를 제한하면 서버 메모리, 데이터베이스 작업과 네트워크 응답 크기의 상한도 예측하기 쉬워진다.

외부 입력에 제한이 없다면 알고리즘의 최대 비용도 제한하기 어렵다.

한 번의 비용이 작아도 반복 횟수가 많으면 서비스 비용은 커진다

쿠폰 하나를 추천하는 계산이 5밀리초에 끝난다고 생각해보자.

한 사용자의 요청만 보면 충분히 빠르다.

하지만 홈 화면, 장바구니와 결제 화면이 각각 같은 계산을 요청하고, 이벤트 시간에 초당 수천 명이 접속한다면 전체 비용은 달라진다.

요청 한 건의 비용
× 사용자당 호출 횟수
× 동시에 요청하는 사용자 수

다음 코드는 한 번의 API 요청 안에서도 같은 계산을 반복할 수 있다.

const homeCoupon =
  await recommendCoupon(userId, order);

const bannerCoupon =
  await recommendCoupon(userId, order);

const checkoutCoupon =
  await recommendCoupon(userId, order);

호출 위치가 다르더라도 같은 사용자, 주문과 쿠폰 상태를 기준으로 계산한다면 중복 작업일 수 있다.

한 요청 안에서는 계산 결과를 재사용할 수 있다.

const recommendation =
  await recommendCoupon(userId, order);

return {
  homeCoupon: recommendation,
  bannerCoupon: recommendation,
  checkoutCoupon: recommendation,
};

요청 사이에서도 결과를 캐시할 수 있지만 최신성 조건을 먼저 확인해야 한다.

쿠폰 추천 미리보기는 짧은 시간 동안 오래된 값을 허용할 수 있다. 그러나 결제를 확정할 때는 캐시된 쿠폰 상태만 믿을 수 없다.

const preview =
  await couponCache.getRecommendation({
    userId,
    orderId,
  });

캐시는 화면에 추천을 빠르게 보여주는 데 사용할 수 있다.

최종 사용 단계에서는 데이터베이스의 최신 상태를 다시 검증해야 한다.

const result =
  await couponRepository.redeemIfAvailable({
    couponId: preview.couponId,
    userId,
    redeemedAt: serverNow,
  });

추천 결과는 계산된 데이터이고, 쿠폰의 최종 상태에 대한 Source of Truth는 데이터베이스다.

시간을 줄이기 위해 계산 결과를 저장할 수는 있지만, 그 결과를 어느 단계까지 신뢰할 수 있는지는 별도의 정확성 판단이다.

더 낮은 시간 복잡도가 항상 더 빠른 것은 아니다

두 가지 구현을 비교해보자.

첫 번째 방법은 작은 쿠폰 배열을 직접 탐색한다.

function findCouponById(coupons, couponId) {
  return coupons.find(
    (coupon) => coupon.id === couponId
  );
}

시간 복잡도는 O(n)이다.

두 번째 방법은 ID를 키로 갖는 Map을 먼저 만든다.

const couponById = new Map(
  coupons.map((coupon) => [
    coupon.id,
    coupon,
  ])
);

const coupon = couponById.get(couponId);

Map을 만든 뒤의 평균 조회 비용은 O(1)에 가깝다.

그러나 Map을 만드는 데는 O(n)의 시간과 추가 메모리가 필요하다.

쿠폰 10개에서 ID 조회를 한 번만 한다면 배열 탐색이 더 단순하고 실제로도 충분히 빠를 수 있다.

같은 목록에서 수천 번 조회한다면 Map을 만드는 비용을 먼저 부담하고 반복 조회 비용을 줄이는 편이 유리할 수 있다.

상황	적절할 수 있는 선택
작은 목록에서 한 번 조회	배열의 선형 탐색
같은 목록에서 반복 조회	Map으로 사전 구성
데이터가 자주 변경됨	재구성 비용까지 비교
메모리가 제한됨	추가 저장 구조의 크기 확인
데이터베이스에 원본이 있음	애플리케이션 구조보다 인덱스 조회 검토

복잡도는 선택을 돕는 기준이지 선택을 자동으로 결정하는 규칙이 아니다.

입력 크기, 반복 빈도, 작업 한 번의 비용과 추가 자원 사용을 함께 비교해야 한다.

정확성을 지키는 비용은 제거할 수 없는 경우가 있다

크리스가 1회용 쿠폰을 두 기기에서 동시에 사용한다고 생각해보자.

애플리케이션이 쿠폰 상태를 한 번 읽고 메모리에서 판단하면 빠를 수 있다.

const coupon =
  await couponRepository.findById(couponId);

if (coupon.remainingUses > 0) {
  await couponRepository.updateRemainingUses(
    couponId,
    coupon.remainingUses - 1
  );
}

하지만 두 요청이 같은 remainingUses 값을 읽으면 둘 다 성공할 수 있다.

조금 더 많은 데이터베이스 제어 비용을 부담하더라도 확인과 변경을 하나의 조건부 작업으로 처리해야 한다.

UPDATE coupons
SET remaining_uses = remaining_uses - 1
WHERE id = $1
  AND recipient_id = $2
  AND remaining_uses > 0
  AND status = 'ACTIVE'
  AND expires_at > $3
RETURNING id, remaining_uses;

이 쿼리는 처리 순간의 상태가 모든 조건을 만족할 때만 쿠폰을 차감한다.

읽기와 쓰기를 분리한 코드보다 무거울 수 있지만 1회용 쿠폰이 두 번 사용되지 않는다는 비즈니스 규칙을 보장한다.

시간 복잡도를 줄이기 위해 다음 조건을 제거해서는 안 된다.

• 권한 확인
• 최신 상태 검증
• 중복 요청 방지
• 동시 변경 제어
• 금액과 재고의 일관성
• 필요한 트랜잭션

성능은 서비스가 올바른 결과를 만드는 범위 안에서 개선해야 한다.

잘못된 답을 빠르게 반환하는 구현은 사용자에게 빠른 서비스가 아니다.

복잡도 분석과 실제 측정은 서로 다른 질문에 답한다

시간 복잡도는 데이터가 증가할 때 비용이 어떻게 변할지 예상하게 한다.

측정은 현재 환경과 데이터에서 실제로 어디에 시간이 쓰이는지 알려준다.

쿠폰 API가 느리다고 생각해보자.

코드에 정렬이 있다는 이유만으로 정렬을 병목이라고 판단할 수는 없다.

다음 구간을 각각 측정해야 한다.

const queryStartedAt = performance.now();
const coupons =
  await couponRepository.findAvailable(input);
const queryEndedAt = performance.now();

const calculationStartedAt = performance.now();
const result =
  selectBestCoupon(coupons, order);
const calculationEndedAt = performance.now();

logger.info("Coupon recommendation timing", {
  queryMs:
    queryEndedAt - queryStartedAt,
  calculationMs:
    calculationEndedAt -
    calculationStartedAt,
  couponCount: coupons.length,
});

이 코드는 데이터베이스 조회 시간, 계산 시간과 처리한 쿠폰 수를 함께 기록한다.

측정 결과는 다음과 다를 수 있다.

구간	걸린 시간
인증과 권한 확인	20ms
데이터베이스 조회	420ms
쿠폰 필터링과 계산	8ms
응답 직렬화	15ms
네트워크 전송	180ms

이 상황에서 O(n)인 필터링을 미세하게 개선해도 사용자가 느끼는 시간은 거의 달라지지 않는다.

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

반대로 현재 데이터가 작아 측정에서 문제가 보이지 않더라도 알고리즘이 O(n²)이고 입력이 빠르게 증가한다면 미래의 위험을 예상할 수 있다.

두 방법은 서로 대체하지 않는다.

• 복잡도 분석은 데이터가 커졌을 때의 위험을 예측한다.
• 측정은 현재 실제 병목이 어디인지 확인한다.
• 운영 지표는 예상과 현실이 언제 달라지는지 알려준다.

설계 단계에서는 복잡도로 위험한 증가 구조를 찾고, 구현 이후에는 측정으로 우선순위를 정해야 한다.

성능 목표가 있어야 충분히 빠른지 판단할 수 있다

“쿠폰 API가 빨라야 한다”는 요구사항만으로는 알고리즘을 평가하기 어렵다.

측정 가능한 목표가 필요하다.

예를 들어 다음과 같이 정할 수 있다.

항목	목표 예시
지원할 사용자당 쿠폰 수	최대 10,000개
한 번에 반환할 쿠폰 수	최대 20개
일반적인 서버 응답 시간	300ms 이내
상위 요청 응답 시간	800ms 이내
이벤트 최대 요청량	초당 2,000건
응답 본문 크기	100KB 이하
최종 쿠폰 사용 정확성	중복 차감 0건

이 숫자는 모든 쿠폰 서비스에 적용되는 표준이 아니다.

사용자 경험, 서버 비용과 비즈니스 위험을 기준으로 서비스가 직접 결정해야 하는 예시다.

목표가 있으면 다음 판단이 가능해진다.

• 단순한 선형 탐색으로 충분한가?
• 전체 목록 대신 필요한 결과만 조회해야 하는가?
• 데이터베이스 인덱스가 필요한가?
• 계산 결과를 미리 저장할 가치가 있는가?
• 캐시의 오래된 데이터를 어디까지 허용할 수 있는가?
• 요청량이 증가하면 어느 자원이 먼저 한계에 도달하는가?
• 현재 구현을 언제 다시 설계해야 하는가?

시간 복잡도는 가장 낮은 기호를 얻기 위한 경쟁이 아니다.

서비스가 약속한 데이터 규모와 응답 시간 안에서 충분히 동작하는 해결책을 선택하기 위한 공통 기준이다.

시간 복잡도를 설계에 사용할 때 물어봐야 할 질문

알고리즘이나 데이터 처리 흐름을 설계할 때 다음 질문을 확인할 수 있다.

1. 입력 크기를 나타내는 n은 현실의 어떤 데이터를 의미하는가?
2. 입력 크기가 하나인가, 쿠폰 수와 상품 수처럼 여러 개인가?
3. 현재 평균 입력 크기는 얼마인가?
4. 정상적으로 지원해야 할 최대 입력 크기는 얼마인가?
5. 데이터는 어느 속도로 증가하고 있는가?
6. 입력이 두 배가 되면 주요 작업 횟수는 얼마나 늘어나는가?
7. 반복문 한 번 안에서 실제로 어떤 작업을 실행하는가?
8. 반복 중 데이터베이스나 네트워크를 호출하고 있지는 않은가?
9. 같은 데이터를 여러 번 탐색하고 있지는 않은가?
10. 여러 선형 단계에서 중간 배열이나 객체가 얼마나 생성되는가?
11. 전체 결과가 필요한가, 일부 목록이나 하나의 값만 필요한가?
12. 전체 정렬 없이 필요한 결과를 만들 수 있는가?
13. 처리 전에 저장소에서 후보 범위를 줄일 수 있는가?
14. 데이터베이스가 사용할 수 있는 적절한 인덱스가 있는가?
15. 인덱스 추가로 발생하는 저장 공간과 쓰기 비용을 감당할 수 있는가?
16. 사전 계산이나 조회 구조를 몇 번 재사용하는가?
17. 속도를 위해 추가 데이터를 저장한다면 언제 갱신하는가?
18. 계산 결과와 원본 데이터의 Source of Truth를 구분했는가?
19. 캐시된 결과는 어느 단계까지 신뢰할 수 있는가?
20. 외부 사용자가 요청할 수 있는 입력 크기를 제한했는가?
21. 한 번의 요청 비용뿐 아니라 전체 요청 빈도를 고려했는가?
22. 동시에 많은 요청이 들어오면 어떤 자원이 먼저 부족해지는가?
23. 권한, 검증과 동시성 제어를 성능 때문에 생략하고 있지는 않은가?
24. 현재 구현의 성능을 실제 데이터 규모에서 측정했는가?
25. 데이터베이스, 서버 계산과 네트워크 시간을 구분해 측정했는가?
26. 평균뿐 아니라 느린 요청과 큰 입력도 관찰하고 있는가?
27. 현재 병목이 정말 알고리즘에 있다는 근거가 있는가?
28. 서비스가 만족해야 하는 응답 시간과 처리량 목표가 있는가?
29. 현재 설계가 한계에 가까워졌음을 알려줄 지표가 있는가?
30. 더 복잡한 방법이 실제 요구사항에 비해 지나친 설계는 아닌가?

이 질문에 모두 정확한 숫자로 답하지 못할 수도 있다.

모르는 값을 드러낸 뒤 로그와 측정을 추가하는 것도 중요한 설계 작업이다.

확인하지 않은 데이터 규모를 작다고 가정하거나, 측정하지 않은 코드를 병목이라고 가정하지 않는 것이 출발점이다.

시간 복잡도는 서비스가 성장할 때의 변화를 보여준다

시간 복잡도는 코드가 정확히 몇 초 동안 실행되는지 알려주지 않는다.

같은 O(n) 알고리즘도 메모리 값을 비교하는지, 데이터베이스를 조회하는지, 외부 API를 호출하는지에 따라 실제 시간은 크게 달라진다.

하지만 시간 복잡도는 다른 중요한 질문에 답하게 해준다.

사용자, 쿠폰, 상품과 요청이 늘어날 때 현재 방식의 비용은 어떤 속도로 커지는가?

이 질문을 서비스에 적용하려면 반복문의 모양만 봐서는 안 된다.

1. 현실의 어떤 데이터가 입력 크기인지 정의한다.
2. 평균과 지원할 최대 크기를 구분한다.
3. 계산뿐 아니라 조회와 데이터 이동을 포함한다.
4. 여러 입력 크기가 서로 곱해지는 지점을 찾는다.
5. 필요한 출력의 크기에 맞게 처리 범위를 제한한다.
6. 반복되는 조회와 계산이 있는지 확인한다.
7. 추가 저장 구조가 줄이는 시간과 늘리는 비용을 비교한다.
8. 정확성과 최신성을 지키는 작업은 유지한다.
9. 실제 운영 환경에서 구간별 시간을 측정한다.
10. 서비스 목표를 기준으로 현재 방법이 충분한지 판단한다.

시간 복잡도는 실행 시간을 숫자로 예언하는 공식이 아니다. 현실의 데이터 규모가 변할 때 계산, 조회와 통신 비용이 어떻게 증가하는지 설명하고 서비스가 감당할 수 있는 한계를 미리 발견하는 방법이다.

작은 쿠폰 목록을 한 번 탐색한다면 O(n) 방식이 가장 단순하고 안전할 수 있다.

서비스 전체 쿠폰을 매 요청마다 가져온다면 같은 O(n)이라도 입력 범위를 줄여야 한다. 쿠폰과 상품을 반복해서 비교한다면 여러 입력 크기의 관계를 살펴봐야 한다. 조회가 반복된다면 인덱스나 사전 계산을 검토할 수 있다.

중요한 것은 가장 낮은 복잡도의 코드를 선택하는 일이 아니다.

서비스가 책임질 데이터 규모, 응답 시간, 정확성과 운영 비용 안에서 충분히 예측 가능한 방법을 선택하는 일이다.

다음 글에서는 Big O가 알고리즘을 어려워 보이게 만드는 수학 기호가 아니라, 서비스가 감당할 수 있는 데이터 규모와 성장 한계를 논의하는 공통 언어인 이유를 살펴본다.