다양한 데이터 구조의 시간 복잡도는 어느 정도입니까?

다양한 데이터 구조의 시간 복잡도는 어느 정도입니까?

Arrays, Binary Search Tree, Heap, Linked List 등 일반적인 데이터 구조의 작업 시간 복잡성을 나열하려고 하는데, 특히 Java를 언급하고 있습니다.아주 흔하지만, 우리 중 몇몇은 정확한 답을 100% 확신하지 못하는 것 같아요.어떤 도움, 특히 참고 자료도 대단히 감사합니다.

예: 단일 링크 목록의 경우:내부 요소의 변경은 O(1)입니다.어떻게 할 수 있죠?요소를 변경하기 전에 검색해야 합니다.또, 벡터는, 내부 원소를 추가하는 것을 O(n)로서 한다.그런데 왜 지수를 사용해서 상각된 일정 시간 내에 할 수 없는 거죠?부족한 점이 있으면 정정해 주세요.

첫 번째 답변으로 저의 조사결과/추측을 올립니다.

어레이

• 설정, 특정 인덱스에서 요소 확인: O(1)
• 검색: 배열이 정렬되지 않은 경우 O(n), 배열이 정렬되어 바이너리 검색과 같은 것이 사용되는 경우 O(log n)
• 아이비안이 지적한 바와 같이, 거기에는Delete어레이로 조작할 수 있습니다.요건에 따라 특정 값(예: -1, 0 등)으로 설정함으로써 요소를 심볼적으로 삭제할 수 있습니다.
• 유사하게,Insert어레이의 경우 기본적으로Set처음에 말한 바와 같이

어레이 리스트:

• 추가: 상각된 O(1)
• 삭제: O(n)
• 내용물: O(n)
• 사이즈: O(1)

링크 리스트:

• 삽입: O(1), 헤드에서 완료되면 O(n), 링크 리스트를 선형으로 통과하여 해당 위치에 도달해야 하므로 다른 위치에 도달하면 O(n)가 됩니다.
• 삭제: O(1)가 선두에서 이루어지면 O(n)가 됩니다.링크 리스트를 직선적으로 횡단하여 그 위치에 도달해야 하기 때문입니다.
• 검색: O(n)

이중 링크 목록:

• 삽입: O(1), 선두 또는 테일에서 수행되면 O(n), 링크 리스트를 선형으로 통과하여 해당 위치에 도달해야 하기 때문에 다른 곳에서 수행되면 O(n)입니다.
• 삭제: O(1)가 선두 또는 테일에서 수행되면 O(n)가 해당 위치에 도달하려면 링크 목록을 선형으로 통과해야 합니다.
• 검색: O(n)

스택:

• 푸시: O(1)
• 팝: O(1)
• 상단: O(1)
• 검색(특수 조작으로서의 검색 등): O(n) (그런 것 같습니다)

큐/디큐/원형 큐:

• 삽입: O(1)
• 분리: O(1)
• 사이즈: O(1)

이진 검색 트리:

• 삽입, 삭제 및 검색: 평균 케이스: O(log n), 최악의 케이스: O(n)

레드-블랙 트리:

• 삽입, 삭제 및 검색: 평균 케이스: O(log n), 최악의 케이스: O(log n)

힙/우선순위큐(최소/최대):

• 최소 검색/최대 검색: O(1)
• 삽입: O(log n)
• 최소 삭제/최대 삭제: O(log n)
• 최소/최대 추출: O(log n)
• 검색, 삭제(제공된 경우): O(n), BST와 같은 순서가 아니기 때문에 모든 요소를 스캔해야 합니다.

HashMap/Hashtable/HashSet:

• 삽입/삭제: O(1)상각
• 크기 변경/해시: O(n)
• 내용물: O(1)

Baldung은 ArrayList, LinkedList 및 CopyOnWriteArrayList의 몇 가지 시간적 복잡성을 지적했습니다.https://www.baeldung.com/java-collections-complexity 및 Map 구현에 대해서는 https://www.baeldung.com/java-hashmap를 참조하십시오.

또한 구현 간의 차이를 강조하기 위해 벤치마크를 추가했습니다.

언급URL : https://stackoverflow.com/questions/7294634/what-are-the-time-complexities-of-various-data-structures