[알고리즘] 점근적 표기법 - 상한 하한 차수

* 교재 "쉽게 배우는 알고리즘"을 기준으로 알고리즘 수업에서 배운 내용을 정리하는 글입니다.

 

점근적 표기법이란 시간 복잡도 또는 공간 복잡도 함수의 증가 양상을 구분하기 위해 사용하는 표기법이다.

대표적으로 상한(O), 하한(Ω), 차수(Θ)가 있다. 교재에는 o(리틀오) ω(리틀 오메가) 표기법도 나와있다.

 

O(f(n)) : 상한, 아무리 느려봤자 f(n) 정도이다. f(n)보다 빠르거나 같다.

Ω(f(n)) : 하한, 아무리 빨라봤자 f(n) 정도이다. f(n)보다 느리거나 같다.

Θ(f(n)) : 차수, 상한과 하한을 함께 제시. 두 집합의 교집합

 

O-표기법

빅오 표기법은 점근적 상한으로 볼 수 있으며, g(n) ∈ O(f(n))일 때, f(n)이 g(n)의 상한이 된다. 

주어진 복잡도함수 f(n)에 대해 g(n) ≤ c x f(n)을 만족하는 음이 아닌 정수 n과 상수 c가 존재한다. 즉, g(n)이 f(n)보다 빠르거나 같다는 뜻으로 해석할 수 있다. 교재에 나오는 정의는 아래와 같다. 

 

O(g(n)) = {f(n)│∃c>0,n1>0,s.t.∀n≥n1,f(n)≤cg(n)}

이를 직관적으로 표현하면,

O(g(n)) = {f(n)│ 충분히 큰 모든 n 에 대하여 f(n)≤cg(n) 인 양의 상수 c가 존재한다.}

 

예를 들어, O(nlogn)일때 소요 시간이 nlogn과 같은 비율로 증가하는지, 더 완만하게 증가하는지에 대해서는 알 수 없고, nlogn보다 점근적으로 나쁘지 않다는 것만 알 수 있다. (즉, 엄밀한 상한일수도 있고 여유있는 상한일수도 있다.)

 

또 다른 예로, O(n2)에 속하는 집합의 함수들(=g(n))은 n2(=f(n))보다 빠르거나 같다.

최고차항이 n^r이거나 그보다 작은 다항식은 무조건 O(n^r)이라는 말이다. 더 쉽게 생각해보면 빅오는 내가 얘(=f(n))보다는 빨라!(같을수도) 라는 의미다.

 

Ω-표기법

빅오메가 표기법은 점근적 하한으로 볼 수 있으며, g(n) ∈ Ω(f(n))일 때, f(n)이 g(n)의 하한이 된다.

주어진 복잡도함수 f(n)에 대해 g(n) ≥ c x f(n)을  만족하는 음이 아닌 정수 n과 상수 c가 존재한다. 즉, g(n)이 f(n)보다 느리거나 같다는 뜻으로 해석할 수 있다. 교재에 나오는 정의는 아래와 같다.

 

Ω(g(n)) = {f(n)│∃c>0,n₁>0,s.t.∀n≥n₁,cg(n)≤f(n)}

이를 직관적으로 표현하면,

Ω(g(n)) = {f(n) │충분히 큰 모든 n 에 대하여 cg(n)≤f(n) 인 양의 상수 c가 존재한다.}

 

예를 들어, Ω(nlogn)일때 소요 시간이 nlogn과 같은 비율로 증가하는지, 더 가파르게 증가하는지에 대해서는 알 수 없고, nlogn보다 점근적으로 나쁘다는 것만 알 수 있다. (즉, 엄밀한 하한일수도 있고 여유있는 하한일수도 있다.)

 

또 다른 예로, Ω(n2)에 속하는 집합의 함수들(=g(n))은 n2(=f(n))보다 느리거나 같다.

최고차항이 n^r이거나 그보다 큰 다항식은 무조건 Ω(n^r)라는 말이다.최고차항이 n^r이거나 그보다 작은 다항식은 무조건 Ω(n^r)이라는 말이다. 더 쉽게 생각해보면 빅오는 내가 얘(=f(n))보다는..좀 느려!(같을수도) 라는 의미다.

 

참고로, 이때 Ω-표기로 나타낸 하한과 O-표기로 나타낸 상한이 일치하면 상한과 하한이 일치해서 Θ-표기를 사용할 수 있다.

Θ-표기법

Θ(n) = O(f(n)) ∩ Ω(f(n))일 때, Θ(n)은 가능한 모든 g(n)의 집합이다. 

주어진 복잡도함수 f(n)에 대해 c x f(n) ≤ g(n) ≤d x f(n)을 만족하는 음이아닌 정수 n과 상수 c가 존재한다. g(n) ∈ Θ(f(n))일 때, "g(n)은 f(n)의 차수"라고 한다.

 

Θ(g(n))=O(g(n))∩Ω(g(n))

O(g(n))과 Ω(g(n))이 동시에 성립하는 함수의 집합을 뜻한다. O(g(n))와 Ω(g(n))의 정의를 합쳐서 아래와 같이 정의하기도 한다.

 

Θ(g(n))={f(n)│∃c1,c2>0,s.t.∀n≥n1,c1g(n)≤f(n)≤c2g(n)}

위를 풀어서 말하면 아래와 같다.

Θ(g(n)) = {f(n)│ 충분히 큰 모든 n 에 대하여 c1g(n)≤f(n)≤c2g(n) 인 양의 상수 c1,c2 가 존재한다.}

 

최고차항이 n^r이면 Θ(n^r)이다.

 

코드를 통한 알고리즘 수행 시간 분석

먼저 코드에서는 명확하게 횟수가 정해지면 쎄타, 조건에 따라 실행횟수가 달라지면 빅오를 쓴다고 한다. 그래서 아래 case들은 모두 Θ를 사용했다.

case1: 중첩 반복문과 일반 반복문

void func4(int n) {
	for (int i = 1; i <= 140000 * n; i++)
		printf("Hello, Complexity! \n");
	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= 2 * n; j++)
			printf("Hello, Complexity! \n");
}

위와 같은 코드가 있을 때,

먼저 첫번째 for문을 확인하면 140000n이고 중첩 for문의 경우 n *2n이다. 이를 T(n)으로 표현해보면

T(n) = 140000n + n * (2n) = 2n^2 + 140000n 이다. 이는 ∈ Θ(n^2) 으로 나타낼 수 있다.

즉 for 문에서 중간 "조건식" 부분이 수행 시간이고(cf. for문 초기식;조건식;증감식 의 구조이다.) 각 반복문은 + 로 연결함을 알 수 있다. 

case2: 증감식이 다양한 경우

void func5 (int n) {
	for (int i = 1; i <= n; i *= 2)
		printf("Hello, Complexity! \n");
	for (int i = n; i ›= 1; i /= 2)
		printf ("Hello, Complexity! In");
}

위와 같은 코드는 증감식이 다양하게 표현되어 있다. 먼저 위 for문은 i가 2씩 곱해진다. 1 2 4 8 16 .. n 으로 증가하므로 이는 log n이다.

마찬가지로, 아래 for문은 2씩 나누어진다. n n/2 n/4 n/8 n/16 .. n/n이므로 log n이다. (이떄 정확히 log n+1 번 순회하지만, 빅오의 점근적인 접근에서는 상수를 무시하기 때문에 log n으로 표기)

T(n) = logn + logn = 2logn이므로 ∈ Θ(logn) 이다. 

case3: 변수가 다양한 경우

void func6 (int n, int m) {
	for (int i = 1; i <= n; i++)
	for (int j = 1; j <= m; j *= 2)
		printf("Hello, Complexity! \n");
}

위 경우는 변수 i, j가 사용되었다. 이 경우는 n과 m을 사용해서 표시한다면,(계산 방법은 위 두 case와 같으니 생략) T(n) = n * logm 이므로 ∈ Θ(nlogm) 이다.

 

증명 문제

아래는 5n^2 = Θ(n^2)에 대한 증명이다. Θ의 경우, O와 Ω를 모두 증명해야하기 때문에 예시로 가져왔다.

Q8. f(n)=2n^2-10n+3이 Θ(n^2)임을 증명하시오.

근데 이 문제는 구글링해보니 Ω를 다들 다른 방식으로 푼거 같아서 맞는지 모르겠다. 틀렸다면 댓글로 알려주시길..

 

Q9. 

Algorithm(A[], n) {
	sum1 <- 0
    for i <- 1 to n
    	sum1 <- sum1 + A[i]
    sum2 <- 0
    for i <- 1 to n
    	for j <- 1 to n
        	sum2 <- sum2 + A[i] * A[j]
    return sum1 + sum2
}

위 식에서 중첩 for문이 사용되었으며, 조건에 따라 실행횟수가 정해지므로 Θ일 것이다. 이에 따라 Θ(n^2) 이며 n^2에 비례한다고 볼 수 있다.

 

Q10.

Algorithm(A[][], B[][], M[][], n) {
	for i <- 1 to n
    	for j <- 1 to n {
        	M[i, j] <- 0
            for k <- 1 to n
            	M[i, j] <- M[i, j] + A[i, k] * B[k, j]
        }
}

위 식에서 삼중 for문이 사용되었으며, 조건에 따라 실행횟수가 정해지므로 Θ일 것이다. 이에 따라 Θ(n^3) 이며 n^3에 비례한다고 볼 수 있다.