시간복잡도

시간복잡도(Time Complexity)는 컴퓨터과학 이론으로, 알고리즘이 어떤 문제를 해결하는 데 걸리는 시간을 의미한다. 계산 복잡도 이론의 한 종류로, 알고리즘을 분석하여 효율성을 평가하는 데 사용된다. 계산 복잡도 이론에는 시간복잡도 외에 공간복잡도가 있다.

개요

컴퓨터가 프로그램을 가동할 때, 제대로 된 결과만 낸다고 해서 좋은 프로그램이라고 볼 수는 없다. 결과가 나오기까지의 시간이 오래 걸릴수록 프로그램이 중앙처리장치를 차지하는 시간이 길어지고, 그렇게 되면 중앙처리장치가 다른 일을 처리하지 못해서 컴퓨터의 효율성은 떨어질 수밖에 없다. 따라서 좋은 프로그램인지 알고리즘의 성능을 분석할 방법이 필요하다.

알고리즘의 성능분석의 주된 요소로는 공간복잡도와 시간복잡도가 있다. 공간 복잡도는 메모리 사용량을 분석한 결과로 알고리즘에 사용되는 메모리 공간의 총량을 의미하며, 시간복잡도는 알고리즘에 사용되는 연산 횟수의 총량을 의미한다. 더 정확히는, 알고리즘을 구성하는 명령어들이 몇 번 실행되는지 실행 횟수를 센 결과에 각 명령어의 실행 시간을 곱한 합계를 의미한다. 주로 수행 시간을 구해 시간복잡도를 구하고 해당 알고리즘이 효율적인 알고리즘인지를 판단하는 데 사용된다. 다만, 각 명령어의 실행 시간은 하드웨어나 프로그래밍 언어에 따라 값의 변동이 있을 수 있어서 일반적으로는 실행 시간을 제외하고 명령어의 실행 횟수만을 고려한다. 또한, 알고리즘의 소요 시간을 명확하고 정확하게 평가할 수는 없기 때문에 자료의 수 $n$ 이 증가한다고 할 때 시간이 증가하는 패턴을 시간 복잡도로 표현한다. 시간복잡도의 간단한 예를 들자면, 1을 1000000번 더하는 for 반복문이 있다고 할 때, 여기서 시간 복잡도는 $10^{6}$이라고 할 수 있다. 시간복잡도를 표기하는 방법으로는 대표적으로 빅오표기법이 있다. 빅오에서 가장 차수가 높은 최고차항만 두고 나머지는 버려진다.

• $O(1)$ : 입력 데이터의 크기와 상관없이 언제나 일정한 시간이 걸리는 알고리즘이다. 입력데이터의 양에 상관없이 언제나 실행 시간이 일정하다. 알고리즘이 문제를 해결하는 과정이 한 단계이다.
• $O(n)$: 입력 데이터의 크기에 비례하여 처리 시간에 걸리는 알고리즘을 표현할 때 사용한다. 데이터의 양에 따라 시간이 정비례한다. Lenear Search, for 문을 통한 탐색을 예로 들 수 있다.
• $O(n^{2})$:데이터의 양에 따라 걸리는 시간은 제곱에 비례한다. 이중 루프내에서 입력자료를 처리하는 경우에 발생하며, $n$ 값이 커지면 실행 시간도 매우 길어져 효율성이 떨어진다.
• $O(logn)$: 데이터의 양이 증가해도 시간이 조금씩 증가한다. 시간에 비례하여 탐색 가능한 데이터의 양이 $2^{n}$이 된다. 문제를 해결할 때 필요한 단계들이 연산마다 특정 요인에 의해 줄어든다. 문제를 일정한 크기의 작은 문제로 분리할 때 사용된다. 이진 검색을 예로 들 수 있다.

시간복잡도 연산 크기는 $O(1)<O(logn)<O(n)<O(nlogn)<O(n^{2})<O(n^{3})<O(2^{n})<O(n!)$ 순이다. 시간 복잡도는 어떤 함수를 돌렸을 때 결과를 반환할 때까지 걸리는 실행 시간을 의미하는 것이 아니다. 시간복잡도는 연산의 횟수를 의미하는 것이므로, 시간 단위가 아니라 시행 횟수 단위이다. 따라서 다음과 같은 장점을 얻는다.

• 실행이 따로 필요하지 않다.
• 소프트웨어나 하드웨어가 필요없다.
• 모든 플랫폼에서 동일한 결과를 산출한다.

계산복잡도

계산 복잡도 이론은 계산 문제를 푸는 알고리즘을 복잡도에 따라 문제를 구성하는 방법을 연구한다. 따라서 알고리즘의 계산복잡도를 고려하면 더 효율적인 프로그램이 개발될 수 있다. 복잡도의 기준은 시간 복잡도, 공간 복잡도로 나뉘어 각각 알고리즘이 소요하는 시간과 메모리 사용량을 기준으로 한다. 공간 복잡도는 문제를 해결하는 데 있어 주기억장치의 공간을 얼마나 차지하는지를 살펴보는 것이다. 공간복잡도는 공간을 얼마나 차지하는가를 기준으로 판단하고, 시간복잡도는 시간을 얼마나 차지하는가를 기준으로 판단한다. 과거보다 기술의 발달로 주기억장치인 RAM의 용량이 커져서 공간복잡도의 중요성이 많이 낮아졌다. 따라서 최근에는 공간복잡도보다 시간복잡도가 프로그램의 성능을 비교·분석하고 판단하는 중요한 잣대로 사용되고 있다.

표기법

알고리즘 성능평가는 시간복잡도와 공간복잡도를 계산하고 점근 표기법으로 나타낸다. 점근 표기법은 알고리즘의 복잡도를 단순화할 때나 무한급수의 뒷부분을 간소화할 때 쓰이는 방법으로, 어떤 함수가 증가하는 양상을 다른 함수와 비교하여 표현하는 해석 기법이다. 점근 표기법에는 빅오 표기법, 오메가 표기법, 세타 표기법이 있으며, 이 중 빅오 표기법이 복잡도를 표현하는 데 가장 많이 사용된다.

• 빅오 표기법(Big-O)

알고리즘을 실행했을 때 가장 최악의 경우를 의미하며, 알고리즘의 최대 수행 시간을 표기한다. 최고차항의 차수만 표기하는 방법으로, 시간복잡도를 표현할 때 자주 사용된다. 예를 들어 $n^{2}+n+1$를 빅오표기법으로 표현한다면 $O(n^{2})$으로 표기할 수 있다. 입력자료가 $n$인 알고리즘에서 시간복잡도가 $O(n)$이라고 할 때, $n$ 의 값이 커질수록 시간복잡도가 복잡한 알고리즘은 수행 시간이 급격하게 증가한다. 수행 시간은 문제의 크기에 독립적인 필요가 없으나, 수행 시간의 상한은 문제의 크기에 독립적으로 제한된다. 만약 a와 b를 바꿔서 b가 a보다 크거나 작게 만들어야 하는 문제가 발생한 경우, 시간이 조건 만족 여부에 종속적이라고 해도 상수 시간을 갖는다고는 할 수 없다. 빅오 표기법의 정의는 다음과 같다.

$O(g(n))=${$f(n):n\geq n_{0}$인 모든$n$에 대해$0\leq f(n)\leq cg(n)$을 만족하는 양의 상수$c$와$n_{0}$이 존재한다}

• 오메가 표기법(Big-Omega)

$f(n)=\Omega (g(n))$으로 표현되며, 가장 최선의 경우를 의미한다. 시간에 대한 등가 또는 하한의 개념을 나타내며, 모든 과정은 $\Omega (1)$로 표현될 수 있다. 오메가 표기법의 정의는 다음과 같다.

$\Omega (g(n))=${$f(n):n\geq n_{(}0)$인 모든$n$에 대해$0\leq cg(n)\leq f(n)$을 만족하는 양의 상수$c$와$n_{0}$이 존재한다}

• 세타 표기법(Big theta)

평균적인 상황의 경우를 의미한다. 빅오 표기법과 오메가 표기법의 공통 부분을 맡고 있다. 특정 알고리즘의 시간복잡도가 $O(n)$이면서 $\Omega (n)$이라면 $\Theta (n)$ 세타표기법으로 표기할 수 없는 경우도 존재한다. 세타 표기법의 정의는 다음과 같다.

$\Theta (g(n))=${$f(n):n\geq n_{(}0)$인 모든$n$에 대해$0\leq clg(n)\leq f(n)\leq c2g(n)$을 만족하는 양의 상수$c_{1},c_{2}$와$n_{0}$이 존재한다}

종류

다항 로그 시간

$T(n)=O(\log n)^{k}$라면, 이 알고리즘은 상수 k에 대해 다항 로그 시간 동안 수행되고 있는 것이다.

상수 시간

알고리즘의 수학적 연산 시간이 입력 데이터의 크기와 관계없이 언제나 일정하고, 알고리즘이 문제를 해결하는데 한 단계만 걸리는 것을 상수 시간 또는 $O(1)$이다. 객체에서 키를 알거나 배열에서 인덱스를 알고 있으면 언제나 한 단계만 걸린다. 입력 데이터의 양에 상관없이 언제나 실행 시간이 일정하다. 예를 들자면, 배열 또는 메모리에 있는 요소들에 접근하는데 연산 하나만으로 가능한데, 요소에 접근하는 복잡도를 상수 시간이라고 칭한다. 하지만, 정렬되지 않은 배열 내의 최솟값을 찾아낼 때는 요소 하나하나를 전부 훑어봐야 하므로, 이에 걸리는 시간은 상수 시간이라고 칭할 수 없고, $O(n)$시간이 사용되는 선형 시간이 된다. 그러나 만약 요소들의 개수를 미리 알고 있다면, 알고리즘은 상수 시간에 제대로 이뤄질 수 있다.

로그 시간

입력값 n이 주어졌을 때 문제를 해결하는 데 필요한 단계들이 연산마다 특정 요인 때문에 줄어든다면 로그 시간 또는 $O(\log n)$이다. 데이터의 양이 증가해도 시간이 조금씩 증가하고, 시간에 비례하여 탐색 가능한 데이터의 양이 $2^{n}$이 된다. 문제를 해결할 때 필요한 단계들이 연산마다 특정 요인에 의해 줄어든다. 문제를 일정한 크기의 작은 문제로 분리할 때 사용되며, 배열에서 값을 찾을 때 어느 쪽에서 시작할지를 알고 있으면 검색 시간이 두 배로 감소한다. 컴퓨터는 이진수 시스템을 사용하기 때문에, 로그는 밑을 대부분 2로 사용한다. 그러나 로그의 밑이 변할 때 $\log _{a}n$와 $\log _{b}n$는 오로지 상수 승수에 따라서만 달라지기 때문에 빅오 표기법에서는 버려지므로, $O(\log n)$은 로그 시간 알고리즘에 대한 표준 표기법이다. 로그 시간이 걸리는 알고리즘은 이진 트리에서의 연산에서나 또는 이진 탐색에서 찾아볼 수 있다. 높은 효율을 갖고 있는 $O(\log n)$알고리즘은 문자열을 절반으로 쪼개고 그 오른쪽의 문자열을 다시 또 절반으로 쪼개어 이를 반복하는 알고리즘을 예로 들 수 있다. 각각의 출력 이전에 문자열을 절반으로 나누기 때문에, $O(\log _{10}n)$시간 (n은 문자열의 길이) 이 소요되는데, 이를 통해 출력 횟수를 증가시키기 위해서는 문자열의 길이를 두 배로 늘려야 함을 알 수 있다.

$for(i=1;i<=n;i*=2)$ //application code

$for(i=1;i<=n;i/=2)$ //application code

위와 같은 경우, 데이터 n개에 대한 i는 1, 2, 4, 8, 16...과 같이 제곱으로 증가한다. 비선형적으로 i가 증가하기때문에 첫번째와 비교하여 두번째는 i가 n까지 도달하는 횟수, 즉 연산 횟수가 더 적다. 시간복잡도는 $T(n)=\log _{0}n$이다.

선형 시간

시간복잡도가 $O(n)$이라고 할 때, 알고리즘은 $O(n)$시간 혹은 선형 시간이라고 할 수 있다. 입력 데이터의 양에 정비례하여 실행 시간이 증가하는 알고리즘을 표현할 때 사용된다. Linear Search, for 문을 통한 탐색을 예로 들 수 있다. 선형 시간의 예를 들자면, 다음 식의 n은 입력 값의 개수이고 $T(n)$은 연산 횟수를 구하는 함수이다. 첫 번째는 n개의 데이터가 들어왔을 때 for 문에서 n번 반복하므로 $T(n)=n$이라고 할 수 있다. 두 번째는 $i+=2$이므로 $T(n)=n/2$라고 할 수 있다. 이처럼 데이터 n개에 대한 $T(n)$들이 n 또는 n/2일 경우 n에 대한 1차 방정식이 된다. n이 증가하면 시간복잡도도 비례하여 선형적으로 증가한다.

$for(i=1;i<=n;i++)$ //application code

$for(i=1;i<=n;i+=2)$ //application code

유사 선형 시간

상수 k에 대해 $T(n)=O(n\log ^{k}n))$인 알고리즘은 유사 선형 시간 동안 실행된다. 선형 로그 기간은 k=1인 경우이다. 유사 선형기간에서 실행되는 알고리즘들은 선형 로그 알고리즘에 덧붙여 다음과 같다.

• $O(n\log ^{2}n)$
• 퀵 정렬, $O(n\log n)$, 랜덤화된 버전에서는 최악의 경우 입력 평균에서의 선형 로그 시간이 수행 시간이 된다.
• 힙 정렬, $O(n\log n)$, 합병 정렬, 인트로 정렬, 스무스 정렬 등에서의 최악의 경우
• 고속 퓨리에 변환, $O(n\log n)$

다항 시간

입력 크기에 어떤 다항 표현의 상한을 가지고 수행이 되는 알고리즘은 다항 시간, $T(n)=O(n^{k})$이다. $n$ 값이 커지면 실행 시간도 매우 길어져 효율성이 떨어진다. 결정론적 다항시간 알고리즘이 존재하는지에 관한 문제는 복잡도 클래스 P에 속하고, 이 복잡도 클래스 P는 계산 복잡도 이론 분야에서 핵심을 차지한다. 코밤(Cobham) 논제는 다항 시간이 "추적 가능한", "실현 가능한", "효율적인" 또는 "빠른" 과 같은 동의어를 갖는다고 언급했다. 다음은 다항 시간 알고리즘의 예시이다.

• 정수 $n$에 대한 선택 정렬 알고리즘이 상수 A에 대한 연산을 $An^{2}$개 수행할 때, 이는 $O(n^{2})$의 시간동안 진행되는 다항시간 알고리즘이다.
• 사칙연산과 비교 연산은 다항 시간 동안 이루어진다.
• 그래프에서의 최대 매칭은 다항 시간 동안 찾을 수 있다.

복잡도 클래스

다항 시간은 계산 복잡도 이론의 여러 가지 복잡도 클래스와 연결된다. 다음은 몇 가지 중요한 다항 시간으로 정의된 클래스이다.

• P: 다항 시간 동안 결정적 튜링 머신에서 해결할 수 있는 결정 문제의 복잡도 클래스
• NP: 다항 시간 동안 비결정적 튜링 머신에서 해결할 수 있는 결정 문제의 복잡도 클래스
• ZPP: 다항 시간 동안 확률적 튜링 머신에서 0의 에러 확률로 해결할 수 있는 결정 문제의 복잡도 클래스
• RP: 다항 시간 동안 확률적 튜링 머신에서 단방향 에러를 가지고 해결할 수 있는 결정 문제의 복잡도 클래스
• BPP: 다항 시간 동안 확률적 튜링 머신에서 양방향 에러를 가지고 해결할 수 있는 결정 문제의 복잡도 클래스
• BQP: 다항 시간 동안 양자 튜링 머신에서 양방향 에러를 가지고 해결할 수 있는 결정 문제의 복잡도 클래스

P는 머신 모델 변화의 측면에서 결정적 기계에 대한 가장 작은 시간 복잡도 클래스이다. 모든 주어진 추상 기계는 해당 기계에 대해 다항 시간동안 해결할 수 있는 문제에 해당하는 복잡도 클래스를 갖고 있다.

강력한 다항 시간과 약한 다항 시간

강력한 다항 시간과 약한 다항 시간 알고리즘은 알고리즘의 입력이 정수로 구성되어 있을 때만 관련이 있고 일부 차별점이 존재한다. 강력한 다항 시간은 계산의 산술 모델에서 정의되며, 기본 산술 연산은 피연산자의 크기에 상관없이 수행된다. 다음은 강력한 다항 시간의 특징이다.

• 계산의 산술 모델에서 연산의 횟수는 입력 인스턴스의 정수 개수를 가지고 다항식으로 경곗값을 갖는다.
• 알고리즘의 공간은 입력 크기가 다항식으로 경곗값을 가진다.

위와 같은 특징을 가진 모든 알고리즘은 튜링 머신에서 산술 연산을 수행하는 적합한 알고리즘을 사용해 산술 연산을 교체하는 것으로 다항 시간 알고리즘화 할 수 있다. 만약 두 번째의 요구사항이 충족되지 않는다면, 다항 시간 알고리즘화를 할 수 없다. 다항 시간에 작동하지만 강력한 다항 시간은 아닌 알고리즘은 약한 다항 시간 동안에 작동한다. 약한 다항 시간 알고리즘으로 알려진 문제 중에는 가장 유명하지만 강력한 다항 시간 알고리즘은 아닌 것은 선형 계획법을 예로 들 수 있다. 약한 다항 시간은 유사 다항 시간과 헷갈려서는 안 된다.

초다항 시간

$T(n)$이 모든 다항식 위에서 경계를 갖지 않는 것은 초다항 시간이 걸리는 알고리즘이다. 상수 $c$에 대해서 $n$이 입력 파라미터일 때, ω(nc)시간을 가지며, 여기에서 n값은 보통 입력값에서의 비트 개수를 뜻한다. 예를 들면, 크기 n 의 입력값에 대해 2n단계 실행되는 알고리즘은 초다항 시간을 요구한다. 지수 자원을 사용하는 알고리즘은 초다항이지만, 어떤 알고리즘들은 매우 약한 초다항이다. 또한, 초다항 시간을 필요로하는 알고리즘은 복잡도 클래스 P밖에 놓인다. P-NP문제가 해결되지 않았기 때문에, NP완비 문제가 다항 시간 동안 실행될 수 있다고 알려진 것은 없다.

참고자료

• 시간복잡도 위키백과 - https://ko.wikipedia.org/wiki/%EC%8B%9C%EA%B0%84_%EB%B3%B5%EC%9E%A1%EB%8F%84
• 호로요이이, 〈시간 복잡도와 공간 복잡도〉, 《네이버 블로그》, 2018-03-15
• 박동건, 〈Time Complexity(시간복잡도)〉, 《벨로그》, 2020-01-02

같이 보기

• 알고리즘
• 공간복잡도

이 시간복잡도 문서는 인공지능 기술에 관한 글로서 검토가 필요합니다. 위키 문서는 누구든지 자유롭게 편집할 수 있습니다. [편집]을 눌러 문서 내용을 검토·수정해 주세요.

인공지능 : 인공지능 기술 □■⊕, 인공지능 활용, 인공지능 개발업체, 인공지능 인물 인간적 행위 로봇공학 • 로봇기술 • 인지과학 • 자동추론 • 자연어 처리 • 지식표현 • 컴퓨터 비전 • 튜링 테스트 합리적 사고 결정이론 • 논리학 • 논리주의자 • 삼단논법 • 선호도 • 최대기대효용 • 효용이론 강화학습 ADP • DDPG • DQN • SARSA • 결정이론적 메타추론 • 계통적 강화학습 • 동적 계획법 • 모델 기반 강화학습 • 모델 프리 강화학습 • 반영식 아키텍처 • 수시 알고리즘 • 심층믿음망 • 어니 • 에이전트 • 확률적 경사하강법 인공지능 프로그램 A2I • 어니 • 알파고 • 왓슨 • 카페 • 텐서플로 • 토치 • 한돌 인공지능 알고리즘 AGI • 관계형 네트워크(RN) • 다층퍼셉트론 • 데이터마이닝 • 딥러닝 • 딥큐러닝 • 머신러닝(기계학습) • 방사신경망 • 분산 샌드박스 • 비지도학습 • 생성대립신경망(GAN) • 생성형 AI • 수퍼 얼라인먼트 • 순전파 • 순환신경망(RNN) • 시그노이드 함수 • 신경망 구조 • 심층신경망(DNN) • 심층신뢰신경망(DBN) • 양방향 비고정값 암호 체계(TSID) • 역전파 • 인공신경망(ANN) • 인공지능(AI) • 제한 볼츠만 머신(RBM) • 전방전달신경망 • 지도학습 • 코헨 자기조직 신경망 • 텍스트마이닝 • 파이 • 퍼셉트론 • 합성곱 신경망(CNN) 문자인식 ICR • OCR • OMR • 문자인식 인공지능 특징 계산상의 합리성 • 분산성 • 불확실성 • 예측곤란성 • 완벽한 합리성 • 유계 합리성 • 이유 불충분의 원리 • 자율성 • 할루시네이션 계산 복잡도 NP • NP-완전 • 공간복잡도 • 시간복잡도 • 여 NP • 여 NP-완전 인공지능 기술 BCI • 멀티모달 • 모달 • 모달리티 • 모달창 • 텔레파시 인공지능 법적 지위 권리주체성 • 전자대리인 • 전자적 인간 • 책임법 • 코파일럿 인공지능 업무 데이터라벨러 • 데이터라벨링 • 크라우드워커 위키 : 자동차, 교통, 지역, 산업, 기업, 단체, 업무, 쇼핑, 블록체인, 암호화폐, 인공지능, 개발, 인물, 행사, 일반