0
입니다. hast 테이블에 액세스하는 것은 단지 hast_table[index]과 같은 배열 인덱스이므로 O(1)이어야합니다. 이유는 hast 테이블의 시간이 최악 인 이유입니다. 복잡성은 O (n)입니다. 최악의 경우는 무엇입니까?hast 테이블의 시간 복잡도가 최악 인 이유는 O (n)
A
답변
1
사이드 체인을 사용하는 용량 1의 해시 테이블은 연결된 목록으로 변질되어 조회를 통해 테이블의 단일 버킷에서 선형 검색이 필요합니다.
https://en.wikipedia.org/wiki/Hash_table#Separate_chaining_with_linked_lists
관련 문제
- 1. 시간 복잡도가 O (sqrt (n) * log (n)) 인 알고리즘이 있습니까?
- 2. 이 이중 루프의 시간 복잡도가 O (n)
- 3. 배열 삽입의 시간 복잡도가 O (n)이고 O (n + 1)이 아닌 이유는 무엇입니까?
- 4. 이 코드 스 니펫 O (n)의 시간 복잡도가 있습니까?
- 5. 왜 코드의 시간 복잡도가 O (log n)입니까?
- 6. 시간 복잡도가 Ө (n²) 인 결정 알고리즘이 있습니까?
- 7. 시간 복잡도 : O (logN) 또는 O (N)?
- 8. 이 코드 세그먼트에 대한 시간 복잡도가 O (n^2) 또는 O (n^3)입니까?
- 9. 다음 코드의 시간 복잡성이 O (n^2) 인 이유는 무엇입니까?
- 10. 시간 복잡성 - 알고리즘의 최악 사례 계산
- 11. 정사각형 행렬 곱셈의 시간 복잡도가 O (n^3)로 정의되는 이유는 무엇입니까?
- 12. 시간 복잡도가 O (lgm) + O (lgn) 인 정렬 된 행렬 (mXn)에서 특정 값을 찾음
- 13. BFS/DFS의 시간 복잡도가 O (E + V) 대신 O (E)가 아닌 이유는 무엇입니까?
- 14. BST의 최악 시간 복잡도 (후순위 탐색)
- 15. 큰 O 시간 복잡성
- 16. 시간 복잡도 O (N) 또는 O (Log N)입니까?
- 17. 기수 정렬 - O (n) 시간
- 18. Maping 키 값 시간 복잡도가
- 19. 복잡도가 O (1) 인 주어진 범위에서 숫자의 배수를 계산합니까?
- 20. 시간 복잡성이 O (N) 인 정렬 알고리즘이 있습니까?
- 21. 평균/최고 O (n) 런타임 복잡도가 10 인 배열의 모든 쌍
- 22. 복잡도가 <O (n^2) 인 모든 하위 문자열을 생성 할 수 있습니까
- 23. 왜 다음과 같은 최대 2 부분 일치 구현 O (m * n^2)의 시간 복잡도가 있습니까?
- 24. O (fib n) 복잡도 알고리즘?
- 25. O (log_2 (n)) = O (log_10 (n))?
- 26. + b = O (n^2)의 시간 복잡도?
- 27. 이진 트리의 InOrder 트리 순회의 시간 복잡도 O (n)?
- 28. 힙 정렬의 공간 복잡성이 O (1) 인 이유는 무엇입니까?
- 29. Insertor Sort의 최악의 경우의 시간 복잡도가 올바르지 않습니다.
- 30. 두 개의 O (N) 메소드가 O (N)으로 간주되는 이유는 무엇입니까?
최악 모든 요소들이 동일한 버킷으로 해싱한다. 일반적으로 최악의 경우는 제한된 메모리의 결과입니다 (또는 메모리의 무한한 양 : 비 완벽한 해싱). 그러나 분석은 훨씬 더 복잡 할 수 있으므로 예를 들어 소금물로 내 의견을 말하십시오. [cuckoo hashing] (https://en.wikipedia.org/wiki/Cuckoo_hashing) + [dearmortization] (https://en.wikipedia.org/wiki/Amortized_analysis) 전략. – sascha
https://www.youtube.com/watch?v=h2d9b_nEzoA – Alexander