자료구조 썸네일형 리스트형 [Data Structures] 자료구조 힙(Heap)이란? 소개 Heap은 데이터에서 최댓값과 최솟값을 빠르게 찾기 위해 고안된 완전 이진 트리(Complete Binary Tree) 부모 노드의 인덱스는 1로, 왼쪽 자식 노드부터 2, 3 순서이다. (부모 노드의 인덱스) = (자식 노드 인덱스) // 2 (왼쪽 자식 노드의 인덱스) = (부모 노드의 인덱스) * 2 (오른쪽 자식 노드의 인덱스) = (부모 노드의 인덱스) * 2 + 1 힙을 사용하는 이유? 최솟값이나 최댓값을 찾기 위해 배열을 사용하면 Ο(n) 만큼 시간이 걸린다. 하지만 힙을 사용하면 O(logn) 만큼 소요되므로, 배열을 사용할 때보다 빠르게 최솟값과 최댓값을 구할 수 있다. 우선순위 큐와 같이 최댓값 또는 최솟값을 빠르게 찾아야하는 알고리즘 등에 활용된다. 특징 힙은 최대힙(Max he.. 더보기 [Java] 자료구조의 시간복잡도와 공간복잡도 소개 자바에서 제공되는 주요 자료구조들의 일반적인 시간 복잡도를 살펴보겠습니다. 시간 복잡도란 알고리즘이 입력 크기에 따라 어떻게 성장하는지를 나타내는 개념입니다. 알고리즘의 성능을 분석하고 비교하기 위해 사용됩니다. 일반적으로, 알고리즘의 수행 시간이나 실행 단계 수를 입력 크기에 대한 함수로 표현합니다. 자료구조 Array 공간 복잡도: O(n) 배열은 각 원소를 연속된 메모리 위치에 저장하므로 모든 원소를 저장하기 위해서는 배열의 크기에 비례한 메모리가 필요합니다. 접근 (Access) O(1) 검색 (Search) O(n) 삽입 (Insertion) O(n) - 평균적인 경우 삭제 (Deletion) O(n) - 평균적인 경우 LinkedList 공간 복잡도: O(n) 각 노드는 데이터와 다음 노.. 더보기 이전 1 다음
