시간 복잡도

시간 복잡도(Time Complexity)는 계산 복잡도 이론에서 문제를 해결하는 데 걸리는 시간과 입력값의 크기 사이의 함수 관계를 의미한다. 컴퓨터 과학에서는 알고리즘의 효율성을 평가하기 위해 입력 데이터의 길이에 따라 수행되는 기본 연산의 횟수를 정량화하여 나타낸다. 주로 입력 크기가 무한대로 커질 때의 증가율을 나타내는 점근적 표기법을 사용한다.

배너 광고

개요

시간 복잡도는 알고리즘이 실행되는 동안 소요되는 자원 중 시간에 초점을 맞춘 개념이다. 이는 단순히 특정 컴퓨터에서 측정된 실행 시간을 의미하는 것이 아니라, 입력 크기 $n$ 이 변화함에 따라 연산 횟수가 어떤 비율로 증가하는지를 수학적으로 표현한 것이다. 시간 복잡도가 낮을수록 입력 크기의 증가에 따른 실행 시간의 증가폭이 작으므로 더 효율적인 알고리즘으로 평가된다.

점근 표기법과 빅-오 표기법

알고리즘의 시간 복잡도는 주로 빅-오 표기법(Big-O notation)을 사용하여 나타낸다. 빅-오 표기법은 함수의 증가율을 설명하는 수학적 표기법으로, 계수와 낮은 차수의 항을 제외하고 가장 큰 영향을 미치는 항만을 남겨 점근적으로 묘사한다.

예를 들어, 입력 크기 $n$ 에 대해 필요한 연산 횟수가 $5n^3 + 3n$ 이라면, 이 알고리즘의 점근적 시간 복잡도는 $O(n^3)$ 이 된다. 이는 입력값이 무한히 커질 때 상숫값이나 낮은 차수의 항이 전체 실행 시간에 미치는 영향이 상대적으로 미미하기 때문이다.

주요 시간 복잡도 유형

입력 크기 $n$ 에 따른 대표적인 시간 복잡도는 다음과 같다.

표기법	명칭	특징 및 예시
$O(1)$	상수 시간	입력 크기와 상관없이 항상 일정한 연산 수행
$O(\log n)$	로그 시간	연산마다 탐색 범위가 절반으로 줄어듦 (이진 탐색)
$O(n)$	선형 시간	입력 크기에 비례하여 연산 횟수 증가 (단일 반복문)
$O(n \log n)$	선형 로그 시간	효율적인 정렬 알고리즘 (병합 정렬 등)
$O(n^2)$	이차 시간	입력 크기의 제곱에 비례 (중첩 반복문)
$O(2^n)$	지수 시간	입력이 커질수록 연산량이 급격히 증가 (재귀적 조합 탐색)
$O(n!)$	팩토리얼 시간	모든 가능한 순열을 탐색하는 경우

측정 기준

알고리즘의 수행 시간은 동일한 크기의 입력이라도 데이터의 구성에 따라 달라질 수 있다. 따라서 다음과 같은 기준을 사용한다.

최악의 시간 복잡도: 크기 $n$ 의 모든 입력에 대해 걸리는 최대 시간으로 정의하며, 가장 널리 사용되는 기준이다.
평균 시간 복잡도: 가능한 모든 입력에 대해 걸리는 시간의 평균을 측정하며, 최악의 경우보다 명확하게 서술되어야 할 때 사용된다.

시간 복잡도는 기본적인 연산(변수 대입, 비교, 산술 연산 등)을 수행하는 데 고정된 시간이 걸린다고 가정하고, 알고리즘이 수행하는 기본 연산의 개수를 세어 예측한다.

참고 자료

5건

시간 복잡도시간 복잡도 계산 복잡도 이론에서 시간 복잡도는 문제를 해결하는데 걸리는 시간과 입력의 함수 관계를 가리킨다. 컴퓨터과학에서 알고리즘의 시간복잡도는 입력을 나타내는 문자열 길이의 함수로서 작동하는 알고리즘을 취해 시간을 정량화하는 것이다. 알고리즘의 시간복잡도는 주로 빅-오 표기법을 사용하여 나타내며, Pan Bubil…https://ko.wikipedia.org/wiki/%EC%8B%9C%EA%B0%84_%EB%B3%B5%EC%9E%A1%EB%8F%84 시간 복잡도 - 나무위키시간 복잡도 - 나무위키 최근 변경 최근 토론 특수 기능 # 시간 복잡도 최근 수정 시각: 2026-03-06 03:29:40 편집 편집 이용중인 IP는 문제가 자주 발생하거나 공공 IP 대역이므로 로그인이 필요합니다.(이 메세지는 같은 인터넷 공급업체를 사용하는 다른 누군가로 인해 발생했을 가능성이 높습니다.) (#2…https://namu.wiki/w/%EC%8B%9C%EA%B0%84%20%EB%B3%B5%EC%9E%A1%EB%8F%84 [TIL] 시간 복잡도(Time Complexity) | HyunJi’s Blog[TIL] 시간 복잡도(Time Complexity) | HyunJi’s Blog # 👀Today I Learn ## 시간 복잡도란? “입력 크기(n)가 커질 때, 알고리즘이 얼마나 빠르게 느려지는지”를 수학적으로 표현한 것 - 단순히 코드 실행 시간을 의미하는 것이 아니라, 입력 크기에 따라 실행 횟수가 얼마나 증가…https://hzi09.github.io/til/51_time_complexity/점근 표기법점근 표기법 빅-O 표기법(Big O notation)은 함수의 정의역에 대한 대략적인 크기를 설명하는 수학적 표기법이다. 빅-O는 독일 수학자 파울 바흐만과 에드문트 란다우가 발명하고 다른 사람들이 확장한 일련의 표기법중 하나이며, 이를 통틀어 바흐만-란다우 표기법이라고 한다. 문자 O는 바흐만이 근삿값의 순서를 의미…https://ko.wikipedia.org/wiki/%EC%A0%90%EA%B7%BC_%ED%91%9C%EA%B8%B0%EB%B2%95 계산 복잡도 이론계산 복잡도 이론 계산 복잡도 이론(計算複雜度理論, 영어: Computational complexity theory)은 컴퓨터 과학에서 계산 이론의 분야로, 계산 문제를 푸는 알고리즘을 복잡도에 따라 분류하여 문제의 모임을 구성하는 방법을 연구한다. 이 때 알고리즘의 수행은 실제 컴퓨터가 할 수 있지만, 평가하는 데…https://ko.wikipedia.org/wiki/%EA%B3%84%EC%82%B0_%EB%B3%B5%EC%9E%A1%EB%8F%84_%EC%9D%B4%EB%A1%A0