문인철 교수님의 ‘데이터 구조 및 분석: Linear Structure and Dynamic Programming’ 수업
Algorithm Analysis
Algorithm
clearly specified set of simple instructions to be followed to solve a problem
- lanagaue
- computer program
- pseudo code
Data Structures
Program = algorithms + data structures
Bubble Sort Algorithm & Importance of Efficiency
Bubble Sort
- Data Structure: List
- Algorithm: Bubble sort
Code
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
Importance of Efficiency
- 항상 효율적으로 프로그램이 동작한다는 보장이 없음 → 따라서 최악의 시나리오 케이스를 알고 있어야한다.
- worst-case running time of a single transaction
- worst-case transaction request numbers of a single day