문인철 교수님의 ‘데이터 구조 및 분석: Linear Structure and Dynamic Programming’ 수업
Definition of Algorithm Analysis and Examples
Analyzing an algorithm
- Memory
- Communication bandwidth
- Computational time
Factors affecting the running time
- Computer used for executions
- Algorithms
- Data Structures
- Input data size → Estimate the worst-case of costs by the factors
Simple algorithm analysis
def calculate_int_range_sum(int_from, int_to):
result = 0
for i in range(int_form, int_to):
result = result + i
return result
- Line 1: 1
- Line2, 3: iterations x 2 = 2N iteration
- Line4: 1 iteration
- total = 2N + 2 = O(N)
Bubble sort algorithm analysis
def perform_select_sort(lst):
for i in range(0, len(lst)):
for j in range(i+1, len(lst)):
if lst[i] < lst[j]:
lst[i], lst[j] = lst[j], lst[i]
return lst
- Line1: N iterations
- Line2,3,4: N-i iterations
- 최악의 경우를 구해야해서, if 문이 항상 실행된다는 가정
- Line5: 1
- total: O[N^2]