시간·공간 복잡도와 Big-O

작은 예제에서 빠른 알고리즘이 큰 입력에서도 빠른 것은 아니다

상품 10개의 번호를 찾을 때는 앞에서부터 하나씩 확인해도 부담이 작다. 상품이 100만 개가 되면 같은 방식의 한 번 조회에도 많은 확인이 필요할 수 있다. 반대로 번호순으로 정렬된 배열에서는 가운데와 비교해 볼 범위를 줄일 수 있지만, 먼저 정렬하는 일이 추가된다.

‘1밀리초가 걸렸다’는 말은 그 장치와 자료에서 얻은 측정값이다. 그것만으로 입력이 10배가 되었을 때도 같은 시간이 걸릴지 알 수 없다. 먼저 입력이 커질 때 반복할 일이 어떻게 늘어나는지 세어야 한다.

복잡도는 실행시간을 초 단위로 바로 예언하는 공식이 아니다. 이 절에서는 입력 크기와 세는 연산을 정하고, 작은 수로 계산한 뒤 증가 모양을 기호로 표현한다. 그다음 실제 시간·저장공간·갱신 요구를 대조해 선택한다.

먼저 되짚기: 정확한 알고리즘끼리 비용을 비교한다

알고리즘은 유한한 단계로 입력을 원하는 출력으로 바꾸는 명확한 절차였다. 복잡도 비교는 같은 문제 명세를 올바르게 푸는 알고리즘을 대상으로 한다. 입력 크기를 나타낼 n과 세어야 할 주요 연산을 먼저 정한다.

정확한 알고리즘들 사이에서 증가율을 비교한다

같은 문제 명세를 올바르게 푸는 알고리즘 A·B의 비용을 비교한다. 입력 크기 n과 세는 연산을 정한 뒤 연산 수·추가 공간의 증가 모양을 복잡도로 표현한다. CX-1의 연산 수 비교에서 실제 작은 입력의 차이와 증가율의 상한을 구분한다.

앞 절의 배열 예에서는 위치 조회와 값 검색을 구별했다. 이 절에서도 같은 결과를 요구하는 알고리즘끼리 비교한다. 번호를 찾는 방법과 가장 싼 가격을 찾는 방법을 단순히 횟수만 보고 비교하면 서로 다른 문제를 섞게 된다.

시간·공간 복잡도와 Big-O

시간·공간 복잡도는 입력 크기에 따라 연산횟수와 메모리 사용량이 증가하는 정도다. 시간 복잡도는 정한 기본 연산이 몇 번 필요한지 본다. 공간은 입력을 포함한 전체 공간과 입력 외의 추가 공간을 구별할 수 있으며, 이 절의 비교에서는 추가 공간을 센다.

n은 상품 개수처럼 입력의 크기를 대신 적는 이름이다. 3n+10은 ‘상품 하나마다 3번 하는 일에 고정된 일 10번을 더한다’는 연산수 모형이다. n=1이면 13번, n=10이면 40번, n=100이면 310번이다. n이 커져도 고정된 10번은 그대로이고 상품마다 하는 부분이 커진다.

Big-O 표기(Big-O notation, O)는 입력이 충분히 클 때 비용 증가율의 상한을 상수배 이내로 표현한다. O는 숫자 0이 아니라 영문 대문자이며, O(n)은 ‘오 엔’ 또는 ‘빅오 엔’으로 읽는다. ‘반드시 n번’이라는 뜻은 아니다.

3n+10을 예로 들면 n이 1 이상일 때 10은 10n보다 크지 않으므로 3n+10 <= 13n이다. n에 무관한 13이라는 상수배로 위를 덮을 수 있어 O(n)이라고 쓴다. 여기서 상수는 입력이 커질 때 함께 커지는 값이 아니라 미리 정해진 수다. 같은 함수를 더 느슨한 O(n²)로 덮는 것도 가능하므로 보통 비교에 유용한 더 작은 상한을 쓴다.

n²는 n을 두 번 곱한 n×n이다. 모든 항목마다 다시 n개 항목을 확인하는 두 겹 반복이면 n×n번이 된다. 반면 상한 표기만으로 최선·평균·최악 중 무엇을 분석했는지는 정해지지 않는다. 어떤 경우의 비용함수인지 따로 밝힌다.

한 번씩 훑기와 절반씩 줄이기를 직접 센다

선형 탐색은 앞에서부터 원하는 상품번호와 비교한다. 정렬되어 있지 않은 목록에 없는 번호를 찾으면 마지막 항목까지 모두 보아야 하므로 n개를 비교한다. 첫 항목에서 찾는 경우에는 1개만 비교한다.

이진 탐색은 번호순 정렬과 가운데 위치로 바로 접근할 수 있음을 전제로 한다. 가운데 번호보다 목표가 크면 작은 쪽을 버리고, 작으면 큰 쪽을 버린다. 비교에 사용한 가운데도 다음 후보 범위에서 뺀다. 정렬되어 있으므로 버린 쪽에 목표가 없다고 판단할 수 있다.

예를 들어 [2,4,6,8,10,12,14,16]에서 16을 찾자. 아래 표의 위치는 읽기 쉽게 1번째부터 8번째로 표시했다.

8개를 반복해서 절반으로 줄여 1개를 남기는 단계는 8→4→2→1의 3회다. 이를 log₂8=3이라고 적는다. ‘로그 밑 2의 8’은 ‘2를 몇 번 곱하면 8이 되는가’라는 질문이고, 여기서는 2×2×2가 8이다. 실제 탐색에서는 마지막 남은 항목도 확인해야 하므로 위 비교는 4회이며, 로그값 자체를 정확한 명령 실행횟수라고 쓰지 않는다.

입력이 커질 때의 대표 함수값을 보면 다음과 같다. 소수는 증가 모양을 보이는 함수값이지 컴퓨터가 소수 횟수만큼 비교했다는 뜻이 아니다.

입력이 10배가 될 때 선형의 대표값은 10배, 제곱은 100배가 된다. 두 겹 반복이 순서 있는 모든 쌍과 자기 자신까지 본다면 n²개이고, 서로 다른 두 항목의 조합만 한 번씩 보면 n(n-1)/2개다. 둘은 정확한 횟수가 다르지만 큰 입력의 증가 모양은 모두 제곱이다.

이진 탐색도 준비가 공짜인 것은 아니다. 정렬 비용과 정렬 상태를 유지하는 변경 비용이 필요하다. 가운데로 가려면 앞에서부터 연결을 따라야 하는 자료에서는 위와 같은 위치 접근 비용을 가정할 수 없다. 다음 예에서는 가운데로 바로 갈 수 있는 정렬 배열만 사용한다.

CX-1: Big-O와 실제 연산 수를 함께 본다

같은 문제를 푸는 두 알고리즘의 단순화한 연산 수가 다음과 같다고 하자. 두 식은 자체 교육 모형이며 실제 제품의 측정값이 아니다.

• A: 50n → O(n)
• B: n² → O(n²)

이 예의 50n은 n²보다 증가율이 낮지만 n이 작을 때는 B의 연산 수가 더 적다. n이 양수일 때 50n=n²의 양쪽을 n으로 나누면 50=n이므로 교차점은 50이다. 따라서 1~49에서는 B, 50에서는 동일, 51부터는 A가 더 적다. ‘O(n)이니 모든 입력에서 더 빠르다’는 결론을 낼 수 없다.

공간도 별도다. A가 입력 외 100n바이트를 추가로 쓰면 n=100,000에서 10,000,000바이트가 필요하다. 추가 공간이 일정한 B가 메모리 제약에서는 유리할 수 있지만, 그때도 시간 제약을 동시에 확인한다. 한 자원의 장점으로 다른 한도의 초과를 덮지 않는다.

CX-2: 상품 100만 개의 조회 구조를 실제로 선택한다

이번 문제는 고유 상품번호로 원본의 해당 행을 찾기다. 없으면 없음을 반환한다. 원본의 입력순서는 다른 업무가 사용하므로 원본 자체를 정렬해서 바꿀 수 없다. 하루 한 번 고정한 자료를 하루 동안 10,000회 조회하고, 그동안 추가·삭제·번호 변경은 없다고 가정한다. 이 변경 조건을 만족하지 않는 서비스에 결론을 그대로 옮기지 않는다.

비교할 두 대안은 원본을 그대로 훑는 선형 탐색과, 상품번호·원본 행 위치만 담은 번호순 정렬 배열 색인이다. 여기의 ‘인덱스 기반’은 이 구체적 보조 색인을 뜻한다. 앞 절의 배열 칸 번호도 인덱스라고 부르지만, 그 칸 번호 자체가 검색용 색인 전체는 아니다.

예를 들어 원본 행이 (30,행0), (10,행1), (20,행2)라면 보조 색인은 (10,행1), (20,행2), (30,행0)이다. 번호 20을 찾은 뒤 원본 행2를 읽는다. 원본은 그대로 두고 찾는 순서만 별도 배열에 만들었음을 확인할 수 있다. 번호가 없는 경우에는 탐색 범위가 비어 없음이 된다.

구축은 무엇을 하는가? 보조 항목을 하나씩 만들고 번호순으로 정렬한다. 작은 정렬 묶음 둘의 맨 앞을 비교해 작은 쪽부터 새 배열에 내보내면 더 큰 정렬 묶음을 만들 수 있다. 예를 들어 [10,30]과 [20,40]에서는 10·20·30·40 순서로 내보낸다. 길이 1의 묶음부터 이 결합을 반복하면 묶음 길이가 1·2·4·8처럼 커진다.

100만 개는 2를 20번 곱한 1,048,576보다 작으므로 길이를 두 배씩 합치는 라운드는 20회 이내다. 한 라운드의 번호 비교는 전체 항목 수 n회 이하이므로 정렬의 비교 상한은 20,000,000회다. 정렬 뒤 인접 번호를 확인해 순서와 중복을 검사하는 비용을 1,000,000회 이하로 더해, 구축의 번호 비교 예산은 21,000,000회로 둔다. 복사·메모리 할당·원본 입출력은 번호 비교 횟수와 별도 비용이다.

조회는 무엇을 하는가? 색인의 가운데 번호를 비교해 범위를 줄이고 같으면 원본 행 위치를 돌려준다. 이 예의 100만 항목에서 가운데 하나를 확인하고 제외하는 이진 탐색은 한 조회에 최대 20개의 항목을 확인한다. 선형 탐색은 없는 번호 등 최악의 경우 1,000,000개를 확인한다. 두 방식 모두 입력 번호가 허용 형식인지 확인해야 한다.

조회 횟수를 Q라고 적자. Q는 n과 달리 요청의 개수다. 다음은 전체 조회가 최악 경로를 따른다고 놓은 번호 비교 예산이며 실제 초 단위 지연의 예측이 아니다.

색인은 구축에 많은 비교를 쓰지만 이를 여러 조회에서 회수한다. 이 상한 모형에서 1,000,000Q > 21,000,000 + 20Q일 때 색인의 예산이 더 작다. Q=21이면 21,000,000 대 21,000,420이고, Q=22이면 22,000,000 대 21,000,440이다. 따라서 이 가정에서는 22회부터 색인 쪽 예산이 작다. 실제 정렬 상태·조회 위치·한 비교의 비용이 달라지면 실측 전환점도 달라진다.

공간과 갱신은 가능한가? 교육 모형에서 색인 항목은 고정폭 16바이트(번호 8·행 위치 8)라고 정한다. 따라서 100만 항목의 색인은 16,000,000바이트다. 정렬에 같은 크기의 작업 배열 하나를 쓰면 최초 구축은 32,000,000바이트이며, 이전 색인을 유지한 채 새 색인을 구축할 때는 세 배열 48,000,000바이트가 겹칠 수 있다.

추가 작업공간 한도는 64MiB라고 가정한다. 1MiB는 1,048,576바이트이므로 64MiB는 67,108,864바이트다. 위 배열 합계 48,000,000바이트는 이 한도보다 작지만 실제 자료형·관리정보·작업 상태까지 포함한 최대 사용량도 확인해야 한다. 원본 보관과 조회 결과는 별도이고, 모든 언어의 객체가 16바이트라는 뜻도 아니다.

하루 중 변경은 없으므로 새 판본의 색인을 별도로 완성하고 검사한 뒤 다음 판본의 조회에 사용한다. 원본과 색인의 판본이 다르면 잘못된 행을 찾을 수 있어 공개하지 않는다. 구축 실패·중복 번호·행 위치 오류·메모리 초과는 새 판본의 전환을 막는 조건이다. 이미 정렬한 배열의 중간에 매번 삽입해야 한다면 뒤 항목 이동 비용이 생겨, 현재의 갱신 가정부터 다시 검토해야 한다.

채택·검증. 이 조건에서는 읽기 전용 원본을 유지하는 정렬 배열 색인을 선택한다. 작은 자료와 최대 자료에서 첫 번호·가운데·마지막·없는 번호의 결과를 선형 탐색과 대조하고, 각 색인 행 위치가 같은 판본의 번호로 돌아가는지 검사한다. 조회 지연 목표는 모든 시험 조회 5ms 이하라는 교육용 목표로 두되, 이를 20회 비교에서 환산하지 않는다. 실제 환경의 조회 지연·구축 소요시간·최대 추가 메모리를 측정하기 전에는 운영 적합성을 확정하지 않는다.

최선·평균·최악·상환 비용을 구분한다

선형 탐색의 네 항목 중 첫째를 찾으면 1회, 마지막을 찾거나 못 찾으면 4회 비교한다. 네 항목 각각을 똑같은 횟수로 찾고 실패 조회는 없다는 조건이면 평균은 (1+2+3+4)/4=2.5회다. 없는 번호를 자주 찾는 서비스에 이 평균을 그대로 적용할 수 없다.

상환 분석은 이런 입력 확률의 평균과 다르다. 빈 동적 배열에 항목을 추가하되 용량 1에서 시작해 가득 차면 2·4·8처럼 두 배로 늘리는 모형을 보자. 8개를 넣는 동안 새 값 쓰기는 8회, 기존 값 복사는 확장 때 1+2+4=7회여서 합계 15회다. 8번에 나누면 한 번당 15/8회이지만, 개별 삽입의 비용이 모두 같다는 뜻은 아니다.

9번째를 넣을 때는 기존 8개 복사와 새 값 쓰기 1회가 한 번에 필요하다. 일반적으로 두 배씩 확장한 복사 총량은 항목 수의 상수배 안에 머무므로 여러 삽입의 한 번당 상환 비용을 O(1)로 설명할 수 있다. 용량을 두 배가 아니라 매번 한 칸씩 늘리면 이전 전체를 자주 복사하므로 이 결론을 그대로 적용할 수 없다.

계산 결과를 저장해 재사용하면 시간을 줄이는 대신 공간을 쓴다. 압축은 공간·전송을 줄이지만 압축·해제 계산이 필요하다. 이처럼 시간·공간의 교환은 실제 제약에서 판단하며 상환 비용이 작다고 모든 요청의 순간 지연까지 작다고 보장하지 않는다.

실패조건과 방어

입력 크기 정의 누락. n이 상품 수이고 Q가 조회 수라면 선형 탐색의 반복 조회 비용은 n만이 아니라 n×Q로 계산한다. 같은 n이어도 Q=1과 Q=10,000의 선택이 달라질 수 있다.

중첩 반복이면 무조건 O(n²)라고 단정. 두 반복이 각각 n번이면 n²지만, 안쪽 반복을 합친 총 처리량이 n인 구조도 있다. 실제 범위와 전체 횟수를 먼저 세고 기호를 붙인다.

Big-O를 실행시간으로 오해. O(n)이라는 글자로 5ms를 보장하지 않는다. 입력 크기·자료형·메모리 접근·입출력·실행환경을 고정해 측정한다.

색인 조회만 비교. 구축·정렬·갱신·새 판본 전환의 비용을 누락하면 요청이 적거나 변경이 많은 상황에서 잘못 선택한다. 원본의 입력순서를 바꾸어도 되는지부터 명세에 넣는다.

평균의 근거 누락. 앞에 있는 상품을 자주 찾는 유리한 분포를 당연시하지 않는다. 상한 요구가 있으면 실패 조회·마지막 항목·최대 입력을 포함한다.

시간만 최적화. 새 배열 하나가 16,000,000바이트라고 이전 배열·정렬 작업 배열을 잊으면 갱신 순간의 48,000,000바이트를 놓친다. 실제 최대 추가공간과 전환 중 겹침까지 계산한다.

자체 10점 문제

시간·공간 복잡도와 Big-O를 설명하고 분석 시 유의사항을 제시하시오.

요구어는 설명, 제시다. n과 기본 연산을 정하고, 3n+10을 O(n)으로 쓰는 이유를 한 줄로 설명한다. 이어서 경우 구분·추가 공간·실제 측정의 경계를 붙인다. 기호 목록만 적거나 Big-O를 정확한 실행시간으로 쓰면 요구를 충족하지 못한다.

10점 풀이 방향과 모범답안 보기

10점 답안 목차

1. 시간·공간 복잡도
2. Big-O 의미
3. 입력크기 정의
4. 최선·평균·최악·상환
5. 실제 상수·메모리·측정

10점 답안 도식

입력 크기 n·세는 연산을 먼저 정해 연산 수와 추가 공간을 계산하고, 분석하는 경우를 밝힌 뒤 증가율의 상한 Big-O를 표현한다. 마지막으로 실제 제약·측정과 구축·조회·갱신 비용을 대조한다. 상한 표기가 실제 측정을 대신하지 않는다.

상한 표기와 실제 환경의 측정은 서로 다른 단계다.

10점 답안 예시: 증가율과 실제 조건을 분리한다

시간 복잡도는 입력 크기 n에 따른 기본 연산 수의 증가를 나타내며, 여기서 공간 복잡도는 입력 외 추가 저장량의 증가를 비교한다. Big-O는 충분히 큰 n에서 비용함수를 입력에 무관한 상수배로 덮는 상한 표기다. 3n+10은 n이 1 이상일 때 13n 이하이므로 O(n)으로 쓸 수 있다.

Big-O가 자동으로 최악 경우를 뜻하지는 않는다. 최선·평균·최악 중 분석하는 비용함수를 밝히고, 평균에는 입력 분포의 근거를 둔다. 상환은 연산열 총비용을 횟수로 나눈 관점으로, 개별 연산의 지연 상한과는 다르다.

두 겹 반복은 실제 총횟수를 세고, 여러 입력 크기와 구축·조회·갱신 비용을 구분한다. 추가 공간에는 동시에 살아 있는 작업 배열도 포함한다. 작은 입력의 상수 차이와 실제 메모리·입출력 비용은 기호만으로 결정되지 않으므로 대표·최대 입력에서 결과·지연·공간을 측정한 뒤 선택한다.

자체 25점 문제

대규모 상품조회에서 선형 탐색과 인덱스 기반 탐색의 시간·공간·운영 비용을 비교하여 선택안을 설계하시오.

요구어는 비교, 설계다. CX-2의 100만 상품·하루 10,000회 조회·하루 중 변경 없음·원본 순서 보존·추가공간 64MiB를 교육용 가정으로 사용한다. ‘인덱스’라는 이름만 쓰지 말고 번호·행 위치의 정렬 배열이라는 실제 구조를 선택한다.

번호 비교 예산과 메모리를 계산하고, 구축 중 구·신 판본의 겹침과 조회 지연의 실제 검증까지 연결한다. 문제에서 주지 않은 조건은 가정임을 명시하며, 다른 갱신 조건에서도 언제나 같은 구조가 최선이라고 하지 않는다.

25점 풀이 방향과 모범답안 보기

25점 답안 목차

1. 입력크기·조회패턴
2. 선형 탐색 비용
3. 정렬/인덱스 조회 비용
4. 구축·갱신 비용
5. 추가공간
6. 최악·평균 가정
7. 경계 입력 측정
8. 선택·전환 조건

25점 답안 도식

상자 안의 대상과 화살표의 조건을 함께 읽으세요. 좁은 화면에서는 같은 관계를 세로로 재배치한 도식을 보여 줍니다.

선형 탐색은 매번 원본 번호를 확인한다. 보조 색인은 번호·원본 행 위치를 생성해 정렬·순서·중복을 검증하고 이진 탐색 뒤 원본 행을 읽는다. 새 판본 구축 때 이전 색인·새 색인·작업 배열의 48,000,000바이트 겹침과 결과·판본·지연·최대 공간을 검증한 뒤 전환한다. 구축 실패·판본 불일치·5ms 또는 64MiB 목표 실패에는 채택을 확정하지 않는다.

정렬된 색인만 새것이고 원본은 다른 판본이면 올바른 조회 구조가 아니다.

25점 답안 예시

조건·구조. 상품 100만 개를 하루 10,000회 번호로 조회하며 하루 중 변경은 없고 원본 입력순서를 보존한다고 가정한다. 추가 작업공간은 64MiB, 시험 조회 지연은 5ms 이하를 목표로 한다. 원본을 바꾸지 않고 번호·행 위치의 정렬 배열 색인을 만들어 이진 탐색하는 구조를 선택한다. 번호가 없으면 없음을 반환한다.

시간 비교. 선형 탐색은 별도 색인이 없지만 최악 조회 1회에 100만 항목, 하루 100억 항목을 확인한다. 색인은 길이를 두 배씩 합치는 정렬의 번호 비교 최대 2,000만 회와 정렬 후 검증 100만 회 이하로 구축 예산 2,100만 회를 둔다. 이진 탐색은 조회당 최대 20개 항목으로 하루 20만 회이며, 구축·조회 합계 예산은 2,120만 회다. 이는 번호 비교 모형의 상한 비교이고 복사·입출력·초 단위 실행시간은 별도다.

공간·운영. 색인 항목을 16바이트로 정한 모형에서 색인 1,600만 바이트, 최초 색인과 작업 배열 3,200만 바이트가 필요하다. 이전 색인 유지 중 새 색인과 작업 배열을 만들면 최대 4,800만 바이트가 겹친다. 64MiB=67,108,864바이트보다 작지만 실제 관리정보를 포함한 최대 사용량도 측정한다. 원본·색인의 같은 판본과 행 위치 대응을 확인한 뒤 새 판본으로 전환한다.

대안·전환 경계. 원본 직접 정렬은 입력순서 보존 요구 때문에 채택하지 않는다. 조회가 한 번뿐이면 구축비용이 커서 선형 탐색이 유리할 수 있다. 이 상한 모형의 비교 예산은 22회부터 색인 쪽이 작지만 실측 전환점은 분포·상수에 따라 달라진다. 하루 중 변경이 생기면 배열의 이동·재구축 비용과 판본 규칙을 다시 설계한다.

검증·중단. 첫·가운데·마지막·없는 번호와 최대 입력에서 선형 기준 결과와 대조한다. 정렬순서·중복 번호·원본 행 대응·판본을 확인하고 실제 구축시간·조회지연·최대 추가공간을 측정한다. 오류·5ms 목표 초과·64MiB 초과이면 운영 채택을 확정하지 않는다. 복잡도 표기가 낮다는 이유로 검증 실패를 정상 처리하지 않는다.

출처와 적용 경계

연산수 식과 상품 수·조회 횟수·16바이트 항목·64MiB·5ms는 자체 교육 예의 가정이다. 구축·조회 상한 계산은 명시한 정렬 배열과 비교 모형에 한정한다. 모든 인덱스가 O(log n)이라는 뜻도, 실제 실행시간이 비교 횟수에 정확히 비례한다는 뜻도 아니다.

실제 지연은 하드웨어·언어·자료형·메모리 접근·입출력·데이터 분포에 따라 확인해야 한다. 자체 문제·답안·검산은 공식 기출·공식 채점이나 실제 제품 성능 승인과 구분한다.

30초 정리

1. 입력 크기와 기본 연산을 정해 증가 모양을 비교하고, 입력 저장량과 추가 공간을 구분한다.
2. Big-O는 증가율의 상한이며 정확한 횟수·실행시간·최악 경우를 자동으로 뜻하지 않는다.
3. 구축·조회·갱신·동시 작업공간을 함께 계산하고 실제 결과·지연·메모리 검증을 거쳐 선택한다.

자기교정과 조건 변경

A의 상수가 50에서 5로 줄면? 5n=n²의 양쪽을 양수 n으로 나누면 n=5다. 1~4는 B, 5는 동일, 6부터 A의 연산 수가 적다. A의 O(n), B의 O(n²) 증가 모양은 그대로다.

CX-2의 조회가 한 번뿐이면? 선형의 비교 예산은 100만, 색인의 구축·조회 예산은 21,000,020이다. 낮은 조회 비용만 보고 구축을 생략하면 잘못 비교한 것이다. 이 모형에서는 한 번 조회에 새 색인을 만들지 않는다.

추가 공간이 10MiB로 줄면? 10MiB=10,485,760바이트여서 완성 색인 하나의 16,000,000바이트도 담지 못한다. 지연이 빠를 것 같다는 이유로 진행하지 않고 공간 조건이나 선택안을 다시 정한다.

자료가 하루 중 계속 바뀌면? 조회당 20회라는 숫자만 유지해서는 안 된다. 정렬 배열의 삽입 이동·새 판본 구축·동시 작업공간과 원본 대응을 다시 계산한다. 현재 답안의 ‘하루 중 변경 없음’ 가정이 깨졌음을 먼저 적는다.

상품이 원래 정렬되어 있고 입력순서를 바꿀 필요도 없다면? 보조 색인 구축 없이 원본 배열에 이진 탐색을 적용할 수 있는지 검토한다. 새로운 조건의 더 단순한 선택이며, 원본 순서를 보존해야 했던 CX-2와 구분한다.