자료구조

알고리즘 복잡도

속도 -  시간 복잡도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)

 

재귀 알고리즘 예제

1. 입력값 n을 넣으면 n~0까지 출력
2. Fibonacci - 입력값 n을 넣으면 n번째 값 출력 0 1 1 2 3 5 8 …
3. Factorial - 입력값 n을 넣으면 n! 값 출력 5! = 5*4*3*2*1
4. BinarySearch
5. 하노이 타워

 

종류

선형구조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