본문 바로가기
1. Information Technology/7. Algorithm

Algorithm

by H232C 2021. 2. 18.

1. 정의
 - LIFO(Last In First Out : 마지막에 입력된 자료가 제일 먼저 내보내짐) 형태의 자료구조

2. 특징
 - 자료입력(push), 출력(pop)
 - 자료크기(size), 현재위치(ptr)

3. 시간복잡도

자료구조 비교

Data Structures    Average Case      Worst Case      SearchInsert      DeleteSearch     InsertDelete

Array O(n) N/A N/A O(n) N/A N/A
Sorted Array O(log n) O(n) O(n) O(log n) O(n) O(n)
Linked List O(n) O(1) O(1) O(n) O(1) O(1)
Doubly Linked List O(n) O(1) O(1) O(n) O(1) O(1)
Stack O(n) O(1) O(1) O(n) O(1) O(1)
Hash table O(1) O(1) O(1) O(n) O(n) O(n)
Binary Search Tree O(log n) O(log n) O(log n) O(n) O(n) O(n)
B-Tree O(log n) O(log n) O(log n) O(log n) O(log n) O(log n)
Red-Black tree O(log n) O(log n) O(log n) O(log n) O(log n) O(log n)
AVL Tree O(log n) O(log n) O(log n) O(log n) O(log n) O(log n)

 

4. Algorithm 깃헙 (계속 업데이트 예정)

github.com/h232ch/DataStructureAndAlgorithm

 

h232ch/DataStructureAndAlgorithm

Contribute to h232ch/DataStructureAndAlgorithm development by creating an account on GitHub.

github.com

 

댓글