1. Complexity Analysis of Algorithms
- Spatial complexity analysis
- Time complexity analysis
2. Asymptotic Notations in Complexity Analysis
- Big O notation
- Big Ω notation
- Big ⊝ notation
3. Recursive Algortihm
Examples
- Summation: Recursion vs. Iteration
- Fibonacci: Recursion vs. Iteration
- Tower of Hanoi
- Fractal
Complexity Analysis of Algorithms
1. Spatial complexity analysis
- Mempory space required for execution
2. Time complexity analysis
a) Practical Speed
- Measuring the actual execution time of algorithms
b) Theoretical Speed
- Measure the number of operations performed by the algorithm as a function of data input size n
➡️ Theoretical speed이 합리적 (Free of implementation, Independent of hardware, Independent of software)
1. Time Complexity Analysis: Practical
- Measuring the actual execution time of algorithms
import time # importing time module
start_time = time.time() # record start time
sum = 0
for i in range(2000):
sum = sum + i
end_time = time.time() # record end time
elapsed_time = end_time-start_time # the difference is execution time
print('Execution time:', round(elapsed_time,5), 'seconds')## Execution time: 0.01051 seconds
- difference of end time & start time = execution time
- time: module that measures current time in the processor
2. Time Complexity Analysis: Theoretical
- Measure the number of operations performed by the algorithm as a function of data input size . We call the number of operations as a function of n as f(n)
- e.g. Compare 3 algorithms to compute n^2
1) Algorithm 1
- n * n
- number of multiplicaton = 1
- number of assignment = 1
- In total: 2
def nn_1(n):
out = n*n # 1 multiple
return out # 1 assignment: 결과 output에 저장
2) Algortithm 2
- number of summation = n
- number of assignment = n + 1
- In total: 2n + 1
def nn_2(n):
out = 0 # initialize out=0: 1회
for i in range(n): # iterate n times
out += n # summation happens 1 time인데 for loop로 n번 반복되니까 assignment n*1회
return out
3) Algorithm 3
- number of summation = n^2
- number of assignment = n^2 + 1
- In total = 2n^2 + 1
def nn_3(n):
out = 0
for i in range(n):
for j in range(n):
out += 1
return out
Big O, Ω, ⊝ Notation
- Big O: the upper bound of the function (worst-case complexity of an algorithm)
알고리즘의 시간 복잡도 나타내는 표기
- Big Ω: the lower bound of the function (best-case complexity of an algorithm)
- Big ⊝: the lower and upper bound of the function (average-case complexity of an algorithm)
Properities of Big O
- 데이터 입력값 n이 충분히 크다고 가정하고 있기 때문에 상수항 무시
- O(N^2 + 2N + 1) → O(N^2)와 같이 영향력이 지배적인 N^2 이외의 항 무시
Recursion
def sum_recursive(n):
return n + sum_recursive(n-1)
sum_recursive(3)stopping criteria 없음
⬇️ Base condition is needed to stop the recursion otherwise will run infinitely.
def sum_recursive(n):
if n < 1:
return 0
else:
return n + sum_recursive(n-1)
sum_recursive(3)
Fibonacci Series
1. Recursion
def fib_recursive(n):
if n < 0:
print("Incorrect input")
elif n == 0:
return 0
elif n == 1 or n == 2:
return 1
else:
return fib_recursive(n-1)+fib_recursive(n-2)
fib_recursive(8)T(n) = T(n-1) + T(n-2) + 1
O(2^n)
2. Iteration
def fib_for(n):
fib = [0,1] + [0]*(n-1)
for i in range(2, n+1): # run (n-1) times: O(n)
fib[i] = fib[i-1] + fib[i-2]
return fib[n]
fib_for(8)O(n)
recursion is inefficient for Fibonacci Series
→ it becomes worse when n becomes larger