Θ(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에 비례한다고 볼 수 있다.