Definition [Big "oh"]
- O(1) < O(logn) < O(n) < O(nlogn) < O(n^2) < O(n^3) < O(2^n)
ex) O(n) 과 O(2^n) 비교
1. 100000 x n
2. 1000, 2000, 4000, 8000 .... (2^n x 1000)=> n값 커지면 기하급수적 증가
Practical Complexities
Definition [Omega]
- g(n)은 lower bound
- g(n)은 가능한 가장 큰 값이 되어야 함.
예제 1) 3n + 2는 Ω(n)이라고 할 수 있는가?
f(n) = 3n + 2
n = g(n)
3n + 2 >= c * n
c = 3이라고 하면,
-> 3n + 2 >= 3n
-> 2 >= 0
n0 값이 뭐가 되든 만족함
3n + 2 = O(n) => upper bound
3n + 2 = Ω(n) => lower bound
예제 2) 10n^2 + 4n + 2 = Ω(n^2)이라고 할 수 있는가?
f(n) = 10n^2 + 4n + 2
n^2 = g(n)
10n^2 + 4n + 2 >= c * n^2
c = 10이라고 하면,
-> 10n^2 + 4n + 2 >= 10n^2
-> 4n + 2 >= 0
-> 2(2n + 1) >= 0
-> n이 -1/2 이상이면 항상 만족함. n0 = -1/2
예제 3) 6 x 2^n + n^2 = Ω(2^n)이라고 할 수 있는가?
f(n) = 6 x 2^n + n^2
2^n = g(n)
6 x 2^n + n^2 >= c x 2^n
c = 6이라고 하면,
-> 6 x 2^n + n^2 >= 6 x 2^n
-> n^2 >= 0
-> n0 값이 뭐가 되든 만족함
Definition [Theta]
- g(n)은 upper bound와 lower bound 둘 다
ex)
3n + 2 = O(n)
3n + 2 = Ω(n)
=> 3n + 2 = Θ(n)
- g(n)의 계수(coefficient)는 항상 1이 되어야 함.
ex) Θ(n)이라고 써야지, Θ(32n)과 같이 표기하면 안 됨. - 예제) 2nm + 2n + 1 = Θ(n*m)
Performance Measurement
- 프로그램을 다 짠 후에 성능을 측정하는 것
- 고려 사항: input 값
1) worst-case data
2) best-case data
3) average-case data
ex) Sequential Search
1, 3, 4, 5, 6, 7, 9, 11, 15
1) worst-case => 15 or 15보다 더 큰 수(없는 수)
2) best-case => 1
Iterative binary search
int binsearch(int list[], int searchnum, int left, int right) { int middle; while (left <= right) { middle = (left + right) / 2; switch (COMPARE(list[middle], searchnum) { case -1: left = middle + 1; break; case 0: return middle; case 1: right = middle - 1; } } return -1; }worst-case => O(log(base2)n) --- (n/2->n/4->n/8......->1)
best-case => O(1)
rsum function
float rsum(float list[], int n) { if (n) return rsum(list, n-1) + list[n-1]; return 0; }길이 n인 배열의 실행 시간 = 길이 n-1인 배열의 실행 시간 + 상수 시간
[Recurrence equation]
T(n) = T(n-1) + 1
T(0) = 1 => n=0이 되면 if문에서 나와 return 0 후 끝나므로 상수 시간 소요
- Solve T(n)
T(n) = T(n-1)+1
= (T(n-2)+1)+1
= ((T(n-3)+1)+1)+1
= ...
= (..((T(0)+1)+1)...)+1 = 1 + 1*n = n+1
=> O(n)
Binary search function
[Recurrence equation] (assume that n = 2^k)
T(n) = T(n/2) + 1
T(0) = 1
- Solve T(n)
T(n) = T(n/2)+1
= (T(n/4)+1)+1
= ((T(n/8)+1)+1)+1
= ...
= (..((T(n/2^k)+1)...)+1 = 1 + 1*k = 1+k = 1+log(base2)
=> O(log(base2)n)
Fibonacci (iterative function)
F(0) = 0, F(1) = 1
F(i) = F(i-1) + F(i-2)for (i = 2; i <= n; i++) f[i] = f[i-1] + f[i-2]=> O(n)
Fibonacci (recursive function)
[Recurrence equation]
T(n) = T(n-1) + T(n-2) + 1
T(0) = T(1) = 1
- Solve T(n)
T(n) = T(n-1)+T(n-2)+1 <= 2T(n-1)+1
2T(n-1)+1
= 2(2T(n-2)+1)+1
= 2(2(2T(n-3)+1)+1)+1
= ...
= 2^n-1T(1)+2^n-2+2^n-3+...+2+1 (등비수열)
=> O(2^n)- 등비수열의 합 공식 : a(r^k-1)/r-1 (공비 r, 항 개수 k, 첫번째 항 a)
