시간복잡도(Time Complexity) 정리

학부생이 공부하는 입장에서 작성한 글이므로 다소 오류가 있을 수 있습니다
댓글로 오류를 지적해주시면 바로 수정하겠습니다

1. 시간복잡도란

시간복잡도는 알고리즘의 성능을 분석되는데 사용되는 방법 중 하나입니다.

컴퓨터 프로그램의 입력값과 연산 수행 시간의 상관관계를 나타내는 척도이며,
일반적으로 점근표기법을 이용해 나타내곤 합니다.

연산 수행 시간은 컴퓨터마다 다르지 않나요??

절대적인 수행 시간은 컴퓨터마다 다르고, 그리고 시간이 갈 수록 좋은 성능의 하드웨어가 출시됨에 따라 점점 더 빨라지고 있으므로 절대적인 수행 시간의 측정은 무의미합니다.

입력(Input)값의 예시

배열(array) -> 배열의 크기(size of array)
그래프(graph) -> 정점과 간선의 개수

시간복잡도의 종류

1. Every-Case Time Complexity ( 𝑇(𝑛) )

입력 크기 n 이 입력됐을 때, 알고리즘이 연산을 수행하는 횟수

• 입력 크기에만 종속되며, 어떤 입력값이 들어오더라도 일정하다.

2. The Worst Case Time Complexity( 𝑊(𝑛) )

입력크기 n 이 주어졌을 때, 알고리즘이 연산을 수행하는 최대 횟수

• 입력크기와 입력값 모두에 종속되며, 단위연산이 수행되는 횟수가 최대인 경우 선택

3. The Best Case Time Complexity ( 𝐵(𝑛) )

입력크기 n 이 주어졌을 때, 알고리즘이 연산을 수행하는 최소 횟수

• 입력크기와 입력값 모두에 종속되며, 단위연산이 수행되는 횟수가 최소인 경우 선택

4. The Average Case Time Complexity ( 𝐴(𝑛) )

입력크기 n 이 주어졌을 때, 알고리즘이 연산을 수행하는 평균 횟수

• 입력크기와 입력값 모두에 종속되며, 모든 입력에 대해서 단위연산이 수행되는 기대치

예시1

float sum(float L[], int n) {
	float tsum = 0;
	for(int i =0; i < n; i++)
	tsum += L[i];
	return tsum;
}

위와 같은 함수의 기본 연산이 두 실수의 덧셈 이라면, 배열의 크기에만 수행 시간이 영향을 받으므로 𝑇(𝑛) = 𝑛 배열의 크기 𝑛, 즉 입력 크기에만 종속되는 Every-Case Time Complexity로 분석할 수 있습니다.
𝑇(𝑛)은 만약 𝑇(𝑛)으로 분석할 수 있다면 다른 복잡도도 모두 동일해지는
즉, 𝑊(𝑛) = 𝐴(𝑛) = 𝐵(𝑛) = 𝑇(𝑛)이 되는 특징을 갖고 있습니다.

예시2

index seqsearch(int n, const keytype S[], keytype x)
{
	// S[1,2,...,n] contains the valid keys
	index location = 1;
	while(location <= n && S[location] != x)
		location++;
	if (location > n)
		return 0;
	return location;
}

위는 순차 검색의 함수의 pseudo-code이고 기본 연산은 두 key의 비교 입니다. 이 경우에는 배열 S의 입력 크기 뿐만 아니라 입력 값인 검색하고자 하는 key 𝑥의 값에 따라서 반복문의 종료가 달라지기 때문에 𝑇(𝑛)은 정의되지 않습니다.

이 경우 𝑊(𝑛)과 𝐵(𝑛)으로 분석할 수 있는데, Worst case는 입력값 𝑥가 배열의 마지막에 있을 경우이므로 𝑊(𝑛) = 𝑛이 될 것이고, Best case는 입력값 𝑥가 첫번째 index에 있을 경우이므로 𝐵(𝑛) = 1입니다.

5. Big-Oh (Big-O) 표기법

Big-Oh 표기법은 아래 나올 다른 복잡도들의 표기법과 더불어 𝑛이 매우 큰 수 일 때 알고리즘의 성능을 표기하는 데에 사용됩니다. Big-Oh의 정의는 다음과 같습니다.

𝑔(𝑛) = 𝑂(𝑓(𝑛)) (read as "𝑔 of 𝑛 is big oh of 𝑓 of 𝑛") iff there exist positive constants 𝑐 and 𝑛0 such that 𝑔(𝑛)≤ 𝑐𝑓(𝑛) for all 𝑛, 𝑛 ≥ 𝑛0.
𝑛 ≥ 𝑛0인 모든 𝑛에 대해 𝑔 𝑛 ≤ 𝑐𝑓(𝑛)인 양의 상수 𝑐와 𝑛0가 존재하면 𝑔(𝑛) = 𝑂(𝑓(𝑛)) 이다.

쉽게 말해 점근적 상한을 의미하는데,
g(n)의 성능이 아무리 나빠도 f(n)보다 같거나 좋은 시간 복잡도를 갖는다는 것입니다.
보통 f(n)을 g(n)의 최악의 경우라고 생각하시면 될 것 같습니다.

6. Ω(Omega) 표기법

Omega 표기법의 정의는 다음과 같습니다.

𝑔(𝑛) = Ω(𝑓(𝑛)) (read as "𝑔 of 𝑛 is omega of 𝑓 of 𝑛") iff there exist positive constants 𝑐 and 𝑛0 such that 𝑔(𝑛) ≥ 𝑐𝑓(𝑛) for all 𝑛, 𝑛 ≥ 𝑛0
𝑛 ≥ 𝑛0인 모든 𝑛에 대해 𝑔(𝑛) ≥ 𝑐𝑓(𝑛)인 양의 상수 𝑐와 𝑛0가 존재하면 𝑔(𝑛) = Ω(𝑓(𝑛)) 이다.

Big-oh와 반대로 점근적 하한을 의미하고,
g(n)의 성능이 아무리 빨라도 f(n)보다 같거나 나쁜 시간복잡도를 갖는다는 것입니다.

Big-Oh와 반대의 의미이고 다르게 표현하자면
𝑓(𝑛) = 𝑂(𝑔(𝑛)) 이면, 𝑔(𝑛) = Ω(𝑓(𝑛)) 이라고 표현할 수 있습니다.
n이 일정 수 이상일 때 f(n)은 g(n)보다 작기 때문에 g(n)은 f(n)보다 크기 때문입니다.

7. Θ(theta) 표기법

𝑔(𝑛) = Θ(𝑓(𝑛)) (read as "𝑔 of 𝑛 is theta of 𝑓 of 𝑛") iff there exist positive constants 𝑐1, 𝑐2 and 𝑛0 such that 𝑐1𝑓(𝑛) ≤ 𝑔(𝑛) ≤ 𝑐2𝑓(𝑛) for all 𝑛, 𝑛 ≥ 𝑛0.
𝑛 ≥ 𝑛0인 모든 𝑛에 대해 𝑐1𝑓(𝑛) ≤ 𝑔(𝑛) ≤ 𝑐2𝑓(𝑛) 인 양의 상수 𝑐1, c2와 𝑛0가 존재하면 𝑔(𝑛) = Θ(𝑓(𝑛)) 이다.

theta 표기법의 경우엔 정의에 나와있다시피 n이 일정 수 이상일 때, g(n)이 c1f(n)과 c2f(n)의 사이에 존재합니다. 그래서 theta 표기법으로 표현하기 위해서는 𝑔(𝑛) = Ω(𝑓(𝑛)) 과 𝑔(𝑛) = 𝑂(𝑓(𝑛))을 모두 만족할 수 있어야 합니다.

2. Big-Oh 시간복잡도 순서

𝑂(1) < 𝑂(log n) < 𝑂(n) < 𝑂(nlog n) < 𝑂(n^2) < 𝑂(n^3) < 𝑂(2^n) < 𝑂(n!)

컴퓨터 쪽에서는 일반적으로 알고리즘의 평균적인 시간이 의미가 없는 경우가 많아서 Big-Oh 표기법이 주로 사용됩니다. "이 알고리즘은 평균적으로 이 정도 걸려"보단 "아무리 못해도 절대 이 정도는 된다"가 더욱 신빙성이 높고 평균적인 시간만으로는 최악의 경우를 보장할 수 없기도 합니다.

3. 알아두면 유익한! 시간복잡도 특징들

1. g(n) = O(f(n)) 이면 f(n) = Ω(g(n)) 이다.

2. g(n) = Θ(f(n)) 이면 f(n) = Θ(g(n)) 이다.

3. 1보다 큰 두 수 a,b에 대해, log_a b = Θ(log_b a)

3번은 결국 log 복잡도가 같은 복잡도의 범위에 들어온다는 것을 의미해서 보통 log를 복잡도와 관련해서 의미할 땐 밑은 생략하고 log n 이라고 표현합니다.