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) 다른 위치에서는 연결 목록을 선형으로 탐색하여 해당 위치에 도달해야하기 때문입니다.
- 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)