다양한 데이터 구조의 시간 복잡성은 무엇입니까?

다양한 데이터 구조의 시간 복잡성은 무엇입니까?

---

Arrays, Binary Search Tree, Heap, Linked List 등과 같은 일반적인 데이터 구조 작업의 시간 복잡성을 나열하려고 노력하고 있으며 특히 Java를 언급하고 있습니다. 그들은 매우 일반적이지만 우리 중 일부는 정확한 답에 대해 100 % 확신하지 못하는 것 같습니다. 모든 도움, 특히 참조는 대단히 감사합니다.

예 : 단일 연결 목록의 경우 : 내부 요소 변경은 O (1)입니다. 어떻게 할 수 있습니까? 당신은 가질 를 변경하기 전에 요소를 검색 할 수 있습니다. 또한 Vector의 경우 내부 요소 추가는 O (n)로 제공됩니다. 그런데 왜 우리는 지수를 사용하여 상각 된 일정한 시간에 그것을 할 수 없습니까? 내가 뭔가를 놓친 경우 나를 수정하십시오.

첫 번째 답변으로 내 결과 / 추측을 게시하고 있습니다.

---

배열

• 특정 인덱스에서 요소 설정, 확인 : O (1)
• 검색 : 배열이 정렬되지 않은 경우 O (n) , 배열이 정렬되고 이진 검색과 같은 것을 사용하는 경우 O (log n) ,
• Aivean 에서 지적했듯이 Delete어레이에서 사용할 수있는 작업 이 없습니다 . 요구 사항에 따라 특정 값 (예 : -1, 0 등)으로 설정하여 요소를 상징적으로 삭제할 수 있습니다.
• 마찬가지로, Insert배열의 경우 기본적 Set으로 처음에 언급 한대로

ArrayList :

• 추가 : 상각 O (1)
• 제거 : O (n)
• 포함 : O (n)
• 사이즈 : O (1)

연결된 목록 :

• Inserting : O (1) , 만약 헤드에서 끝나면 O (n) , 링크드리스트를 선형 적으로 탐색하여 그 위치에 도달해야하기 때문에 다른 곳이라면 O (n) .
• Deleting : O (1) , 헤드에서 완료되면 O (n) , 링크드리스트를 선형으로 탐색하여 해당 위치에 도달해야하기 때문에 다른 위치에 있으면 O (n) .
• 검색 중 : O (n)

이중 연결 목록 :

• Inserting : 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)

힙 / PriorityQueue (최소 / 최대) :

• 최소 구하기 / 최대 구하기 : O (1)
• 삽입 : O (log n)
• 최소 삭제 / 최대 삭제 : O (log n)
• 최소 추출 / 최대 추출 : O (log n)
• 조회, 삭제 (제공된 경우) : O (n) , BST와 같이 정렬되지 않은 모든 요소를 ​​스캔해야합니다.

HashMap / Hashtable / HashSet :

• 삽입 / 삭제 : O (1) 상각
• 크기 조정 / 해시 : O (n)
• 포함 : O (1)

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