도구스개발

시간복잡도 비교 계산기

입력 크기를 넣으면 O(1)부터 O(n!)까지 아홉 가지 시간복잡도의 연산 횟수와 예상 실행 시간을 한눈에 비교합니다. 정해진 시간 안에 감당 가능한 최대 n도 역산합니다.

n = 1,000,000 일 때 정렬(O(n log n))

199 ms

같은 n 으로 이중 반복문(O(n²))을 돌리면 2.78 시간

O(1)상수1회10.0 ns
O(log n)로그20회199 ns
O(√n)제곱근1,000회10.0 µs
O(n)선형1,000,000회10.0 ms
O(n log n)선형로그19,931,569회199 ms
O(n²)이차1,000,000,000,000회2.78 시간
O(n³)삼차1.00 × 10¹⁸회317 년
O(2ⁿ)지수9.90 × 10^301,029회사실상 영원
O(n!)계승8.26 × 10^5,565,708회사실상 영원

1초 안에 끝낼 수 있는 최대 n

O(1)사실상 제한 없음
O(log n)사실상 제한 없음
O(√n)10,000,000,000,000,000개
O(n)100,000,000개
O(n log n)4,523,071개
O(n²)10,000개
O(n³)464개
O(2ⁿ)26개
O(n!)11개

어디서 나오는 복잡도인가

O(1)배열 인덱스 접근, 해시 테이블 조회
O(log n)이진 탐색, 균형 이진 트리 탐색
O(√n)소수 판정(√n 까지 나눠 보기)
O(n)배열 한 번 훑기, 최댓값 찾기
O(n log n)병합 정렬, 퀵 정렬 평균, 힙 정렬
O(n²)이중 반복문, 버블 정렬, 모든 쌍 비교
O(n³)행렬 곱셈(단순 구현), 삼중 반복문
O(2ⁿ)부분집합 전체 탐색, 메모이제이션 없는 피보나치
O(n!)순열 전체 탐색, 외판원 문제 완전탐색
빅오는 실행 횟수가 아니라 자라는 속도입니다. 상수 배와 낮은 차수 항을 버린 값이라, n 이 작으면 O(n²)가 O(n log n)보다 빠를 수도 있습니다. 실제로 정렬 라이브러리도 구간이 작아지면 삽입 정렬로 갈아탑니다. 위 숫자는 정확한 실행 시간이 아니라 자릿수의 감각으로 보세요.
지수와 계승은 다른 세상입니다. n = 100 이면 O(n²)는 1만 번으로 눈 깜짝할 사이지만, O(2ⁿ)는 1.26 × 10³⁰ 번이라 우주 나이로도 못 끝냅니다. 완전탐색을 줄이려고 가지치기·메모이제이션·동적계획법을 쓰는 이유가 이 자릿수 차이입니다.

사용 방법

  1. 1입력 크기 n을 넣습니다. 아래 버튼으로 흔한 크기를 바로 넣을 수 있습니다.
  2. 2쓰는 언어에 맞는 초당 연산 횟수를 고릅니다.
  3. 3복잡도별 연산 횟수와 예상 시간, 그리고 정해진 시간 안에 감당 가능한 최대 n을 확인합니다.

자주 묻는 질문

입력이 커질 때 연산 횟수가 얼마나 빨리 늘어나는지를 나타냅니다. 상수 배와 낮은 차수 항은 버리므로 2n² + 5n + 3은 그냥 O(n²)입니다. 실제 실행 시간이 아니라 자라는 속도를 비교하는 도구라서, n이 작으면 O(n²)가 O(n log n)보다 빠를 수도 있습니다.

O(n log n)이므로 약 2천만 번의 연산입니다. 초당 1억 번을 처리하는 환경이라면 0.2초쯤 걸립니다. 같은 100만 개를 이중 반복문(O(n²))으로 돌리면 1조 번이 되어 세 시간 가까이 걸립니다.

초당 1억 번을 기준으로 1초 안에 끝내려면 O(2ⁿ)는 n이 26까지, O(n!)은 11까지입니다. 코딩 테스트에서 n ≤ 20이면 비트마스크 완전탐색을, n ≤ 10이면 순열 전체 탐색을 떠올리라는 말이 이 계산에서 나옵니다.

보통의 실수형으로 담을 수 없을 만큼 크기 때문입니다. 2¹⁰⁰⁰은 10의 301제곱, 1000!은 10의 2567제곱이라 계산 도중에 넘쳐버립니다. 그래서 이 계산기는 전부 상용로그로 계산하고 결과만 지수 표기로 되돌립니다.

빅오에서는 밑이 달라도 상수 배 차이라 표기상 구별하지 않습니다. 다만 이 계산기는 이진 탐색을 기준으로 밑을 2로 잡았습니다. 100만 개를 이진 탐색하면 20번 남짓이면 끝난다는 감각을 주기 위해서입니다.

알아두면 좋은 점

  • 초당 연산 횟수는 언어와 하드웨어, 연산의 종류에 따라 크게 달라지는 어림값입니다.
  • 메모리 접근 패턴(캐시 적중률)이 실제 속도를 몇 배씩 바꾸므로 복잡도만으로 성능을 단정할 수 없습니다.

함께 보면 좋은 도구

ID 충돌 확률UUID·nanoid 같은 랜덤 ID를 몇 개까지 만들어도 안전한지 생일 문제로 계산합니다.다운로드 시간 계산파일 크기와 인터넷 속도를 입력하면 다운로드에 걸리는 예상 시간을 계산합니다.RAID 용량RAID 0·1·5·6·10으로 묶었을 때 실제로 쓸 수 있는 용량과 디스크 몇 개까지 고장 나도 버티는지 계산합니다.마크다운 표엑셀에서 복사한 표를 마크다운 표 문법으로 바꿉니다.메타태그 생성제목·설명·이미지 URL을 입력하면 SEO·오픈그래프·트위터 카드 메타태그를 한 번에 생성합니다.

마지막 검증: 2026년 8월 29일 · 결과는 참고용 추정치입니다.