알고리즘 복잡도
속도 – 시간 복잡도Time Complexity
메모리 – 공간 복잡도Space Complexity
복잡도의 기준은 비교연산의 횟수 or 반복문 횟수
worst case 기준으로 복잡도 측정
빅-오 표기법( Big-Oh notation)
좋은 알고리즘
O(1) 상수형 빅-오
y=1
O(log n) 로그형 빅-오
O(n) 선형 빅-오
O(nlong n)
보통
O(n^2)
거의사용불가
O(n^3)
O(2^n)
재귀 알고리즘 예제
- 입력값 n을 넣으면 n~0까지 출력
- Fibonacci – 입력값 n을 넣으면 n번째 값 출력 0 1 1 2 3 5 8 …
- Factorial – 입력값 n을 넣으면 n! 값 출력 5! = 5*4*3*2*1
- BinarySearch
- 하노이 타워
종류
선형구조Linear
List
Stack
Queue
비선형구조
Tree
Graph
파일구조
순차파일
색인파일
직접파일
단순구조
정수
실수
문자
문자열
Stack – LIFO(Last In, First Out)
Queue – FIFO(First In, First Out)
뱀그림 대가리 입력 꼬리 출력
Deque
아무리봐도 디큔데 덱이라고 읽음
양방향 입출력 큐
Tree
계층적 관계, Hierarchical Relationship을 표현하는 자료구조
Decision Tree, 조직도
Full Binary Tree 왕세모
Complete Binary Tree 작은세모집합
Traversal
1
2 3
전위 순회Preorder Traversal (2 1 3)
중위 순회Inorder Traversal (2 3 1)
후위 순회Postorder traversal (1 2 3)
예제) 계산기
전위 표기법prefix notation
중위 표기법infix notation
후위 표기법postfix notation
BubbleSort
Selection Sort
Insertion Sort
Heap Sort
Merge Sort
Quick Sort