자료구조

시간 복잡도 : 알고리즘 실행 속도

성능 표기법

빅오 표기법 BIG-O

• 알고리즘 최악의 실행 시간을 표기
• 가장 많이/일반적으로 사용
• 아무리 최악의 상황이라도, 이정도의 성능은 보장한다는 의미이기 때문

입력 n에 따라 결정되는 시간 복잡도 함수

O(1) < O(logn) < O(n) < O(nlog) < O(n^2) < O(2^n) < O(n!)

 

공간 복잡도 : 알고리즘이 사용하는 메모리 사이즈

해쉬 테이블 :

구조 : 키에 데이터를 저장하는 데이터 구조

해쉬 : 임의 값을 고정 길이로 변환 하는것

슬롯 : 한개의 데이터를 저장할 수 있는 공간

트리 : 

노드와 브랜치를 이용해서, 사이클을 이루지 않도록 구성한 데이터 구조

node : 트리에서 데이터를 저장하는 기본 요소

root node : 트리 맨 위에 있는 노드

level : 최상위 노드를 level 0으로 하였을때 하위 브랜치로 연결된 노드의 길이를 나타냄

parent node : 어떤 노드의 다음 레벨에 연결된 노드

child node : 어떤 노드의 상위 레벨에 연결된 노드

leaf node :  child node가 하나도 없는 노드

siblings : 동일한 parent node를 가진 노드

depth : 트리에서 node가 가질수 있는 최대 level 

 

힙 : 데이터에서 최대값과 최소 값을 빠르게 찾기 위해 고안된 완전 이진 트리

사용하는 이유

배열에 데이터를 넣고, 최대값과 최소값을 찾으려면 O(n)이 걸림

힙에 데이터를 넣고, 최대값과 최소값을 찾으면 O(logn)이 걸림

우선순위 큐와 같이 최대값 또는 최소값을 빠르게 찾아야 하는 자료구조 및 알고리즘 구현 등에 활용됨

최대 힙은 가장 위에가 가장 높은 값을 가지고 있거나 같다.

최소 합은 가장 위에가 가장 작은 값을 가지고 있거나 같다.