전체 글
-
자료구조 기초 정리 (시간 복잡도, 추상 데이터 타입, 선형 자료구조, 트리)Computer Science/자료구조&알고리즘 2021. 2. 13. 16:13
시간 복잡도 : 인스턴스에 따른 실행 시간 변화 추이를 나타내는 척도 추상 데이터 타입 (ADT) : 자료구조의 명세서, 사용 설명서 같은 것. 데이터가 저장되는 방식과 데이터의 인터페이스 역할을 하는 메소드들의 정의로 이루어져 있다. 배열(Array) : 탐색 시간이 O(1)이지만, 삽입과 삭제가 worst case의 경우 O(n)이다. 링크드 리스트(Linked List) : 삽입과 삭제 시간이 O(1)이지만, 탐색 시간이 worst case의 경우 O(n)이다. 스택과 큐 : 둘 다 선형 자료구조이다. 스택(Stack) : LIFO(Last In First Out) 방식의 자료구조. 큐(Queue) : FIFO(First In First Out) 방식의 자료구조. 트리(Tree) : 비선형 자료구조..