O(n)이 몇 초라는 뜻일까? 연산 수로 보는 Big-O

Об этом предложении

“이 코드는 O(n)이라 빠르다”는 설명만으로 실제 시간을 알 수는 없습니다. 이번에는 입력 개수와 반복 횟수를 따로 세면서 증가율을 설명하는 표기와 측정 시간을 구분 해보겠습니다. 무엇을 세는지 먼저 정하기 Big-O는 입력 크기에 따른 비용의 점근적 상한을 설명합니다. 상수와 작은 항을 생략하므로 같은 O(n)인 코드라도 실제 실행 시간은 달라질 수 있습니다. 또 최악의 경우를 분석하는지, 평균 경우를 분석하는지는 별도 선택입니다. Open Data Structures의 수학적 배경 그림의 단위는 연산 횟수 모형 입니다. 초나 밀리초를 측정한 그래프가 아닙니다. 두 반복문을 실제로 세기 for (const n of [4, 8, 16]) { let linear = 0; let quadratic = 0; for (let i = 0; i < n; i += 1) linear += 1; for (let i = 0; i < n; i += 1) { for (let j = 0; j < n; j += 1) quadratic += 1; } console.log(`${n}: ${linear}, ${quadratic}`); } 검증한 출력은 다음과 같습니다. n 첫 반복문 중첩 반복문 4 4 16 8 8 64 16 16 256 여기서는 표시한 증가 연산을 셌습니다. 모든 CPU 명령어 수나 전체 실행 시간을 센 것은 아닙니다. n을 두 배로 늘리면 첫 값은 두 배, 두 번째 값은 네 배가 됩니다. 중첩이면 모두 O(n2)일까? 안쪽 반복문이 항상 n번 실행하는지 봐야 합니다. 안쪽이 고정 3번이면 전체 반복은 3n입니다. 안쪽 변수가 매번 두 배가 되는 경우는 증가 방식이 다릅니다. 중첩된 모양보다 각 반복 횟수의 합을 확인하는 편이 좋습니다. O(n)은 “정확히 n번”이라는 뜻도 아닙니다. 이 예제의 정확한 횟수와 Big-O 표기를 구분합니다. 작은 입력에서의 상수 비용, 캐시와 입출력은 실제 실행 측정으로 보완해야 합니다. 확인 문제 n을 32로 바꾸면 위 두 값은 무엇일까요? 바깥 n번, 안쪽 3번이면 O(n2)일까요? 같은 O(n)이면 실제 실행 시간도 같을까요? 답과 해설 32와 1024입니다. 각 반복문의 횟수를 대입합니다. 아닙니다. 3n이므로 O(n)입니다. 아닙니다. 상수 비용과 구현, 입력 특성, 실행 환경이 다릅니다. 오늘은 연산을 무엇으로 정의했는지 적어보겠습니다. 내일은 고정 3번 반복을 추가하고, 일주일 뒤에는 이진 탐색의 입력 절반 줄이기와 비교해보면 좋겠습니다. 자료 확인 기준: Open Data Structures의 Big-Oh 설명, 2026-10-04. 표는 코드로 확인한 증가 연산 횟수이며 실행 시간 벤치마크가 아닙니다. 예제 검증 환경: Node.js v24.13.1.

Детали предложения

Провайдер

velog

Источник

velog-rss

Балл

54.39

Уверенность

49%