Dijkstra 最短路径算法为何要求边权非负才能正确工作?
Why does Dijkstra's shortest-path algorithm require non-negative edge weights to be correct?
Dijkstra 采用贪心策略，一旦某个顶点被标记为已确定最短距离就永久固定，依据是此后不可能有更短路径到达它。若存在负权边，已确定的距离可能被后续经过负权边的路径推翻，而算法已不会再松弛该顶点，从而得出错误结果。
Dijkstra uses a greedy rule that permanently finalizes a vertex's shortest distance the moment it is settled, relying on the assumption that no shorter path can later reach it. With a negative-weight edge a later path through that edge could improve an already-settled distance, but the algorithm will not relax it again, yielding a wrong answer.
难度 专业 · 适合 高中(15-18)
CC BY 4.0 · 已核验 · Verified 2026-10-03 · 2 条独立证据
来源 · Source
Cormen《算法导论》第24章 (机械工业出版社)
T. Cormen et al., Introduction to Algorithms (CLRS), 4th ed., Chapter 24 (Single-Source Shortest Paths)
独立核验依据 · Independent verification: 核验依据 1 ISBN 978-0-262-04630-5 · 核验依据 2 ISBN 9780691079516 (1957)
#Dijkstra #最短路径 #贪心
哈希表的负载因子如何影响平均查找性能，工程上如何取舍?
How does a hash table's load factor affect average lookup performance, and how is the trade-off managed in practice?
负载因子是已存元素数与桶数之比；它越大，冲突越频繁，平均查找时间从接近 O(1) 逐渐退化。当负载因子超过阈值（如 0.75）时，实现会扩容并重新散列所有元素，以用更多空间换取更低的冲突率。
The load factor is the ratio of stored entries to buckets; as it grows, collisions become more frequent and average lookup time drifts away from O(1). Once it exceeds a threshold such as 0.75, implementations resize and rehash all entries, trading extra space for fewer collisions.
难度 专业 · 适合 高中(15-18)
CC BY 4.0 · 已核验 · Verified 2026-10-03 · 2 条独立证据
来源 · Source
Cormen《算法导论》第11章 (机械工业出版社)
T. Cormen et al., Introduction to Algorithms (CLRS), 4th ed., Chapter 11 (Hash Tables)
独立核验依据 · Independent verification: 核验依据 1 ISBN 978-0-262-04630-5 · 核验依据 2 ISBN 9780691079516 (1957)
#哈希表 #负载因子 #扩容
快速排序在最坏情况下为何会退化为 O(n²)，实际实现如何规避?
Why does quicksort degrade to O(n²) in the worst case, and how do practical implementations avoid it?
若每次划分都极不平衡（如输入已有序且总选首元素为基准），递归深度达到 n，比较次数累计为 O(n²)。工程实现通常采用随机化选取基准或三数取中来降低最坏情况概率，并对小数组切换到插入排序。
If every partition is highly unbalanced, as when the input is already sorted and the first element is always chosen as pivot, the recursion depth reaches n and the total comparisons become O(n²). Practical implementations pick the pivot randomly or by median-of-three to reduce this probability, and switch to insertion sort for small subarrays.
难度 专业 · 适合 高中(15-18)
CC BY 4.0 · 来源待核验 · Source pending review
来源 · Source
出处备注：著录含书名，但缺版次 / 出版社 / 年份中的一部分，需编辑补全后才能做独立比对。
Knuth《计算机程序设计艺术》第3卷 排序与查找 (国防工业出版社)
D. Knuth, The Art of Computer Programming, Volume 3 (Sorting and Searching), Section 5.2.2
独立核验依据 · Independent verification: 核验依据 1 ISBN 9787115360670（豆瓣书目条目） · 核验依据 3 ARCHIVE 标识 B-001-002-138-NLA：The Art of Computer Program
#快速排序 #时间复杂度 #随机化
广度优先搜索(BFS)通常用于解决哪类图问题?
What class of graph problems is breadth-first search (BFS) typically used for?
BFS 从起点逐层向外扩展，先访问距离近的节点，因此能求出无权图上从一个顶点到其余顶点的最短路径。它也常用于连通分量检测、社交网络中的一度二度关系发现等按层遍历的场景。
BFS expands outward layer by layer from the start, visiting nearer nodes first, so it finds shortest paths on unweighted graphs from one vertex to all others. It is also used for connected-component detection and level-by-level traversal such as finding first- and second-degree connections in a social network.
难度 进阶 · 适合 大众
CC BY 4.0 · 已核验 · Verified 2026-10-03 · 2 条独立证据
来源 · Source
Cormen《算法导论》第22章 (机械工业出版社)
T. Cormen et al., Introduction to Algorithms (CLRS), 4th ed., Chapter 22 (Elementary Graph Algorithms)
独立核验依据 · Independent verification: 核验依据 1 ISBN 978-0-262-04630-5 · 核验依据 2 ISBN 9780691079516 (1957)
#BFS #图遍历 #最短路径
在二叉搜索树中查找一个键的基本步骤是什么?
What are the basic steps to search for a key in a binary search tree?
从根节点出发，将目标键与当前节点键比较：若相等即找到，若更小则进入左子树，若更大则进入右子树，重复直到命中或到达空节点。该过程在平衡树中平均只需 O(log n) 次比较。
Starting at the root, compare the target key with the current node: if equal you have found it, if smaller go left, if larger go right, repeating until a match or an empty subtree. In a balanced tree this takes on average only O(log n) comparisons.
难度 进阶 · 适合 初中(12-15)
CC BY 4.0 · 已核验 · Verified 2026-10-03 · 2 条独立证据
来源 · Source
Cormen《算法导论》第12章 (机械工业出版社)
T. Cormen et al., Introduction to Algorithms (CLRS), 4th ed., Chapter 12 (Binary Search Trees)
独立核验依据 · Independent verification: 核验依据 1 ISBN 978-0-262-04630-5 · 核验依据 2 ISBN 9780691079516 (1957)
#二叉搜索树 #查找 #分治
算法分析中的大 O 符号表达的是什么含义?
What does big-O notation express in algorithm analysis?
大 O 描述算法运行时间或空间随输入规模增长的上界，忽略常数因子和低阶项，只反映渐进趋势。例如 O(n log n) 表示当 n 很大时，运行时间的增长不超过 n log n 的某个常数倍。
Big-O describes an upper bound on an algorithm's running time or space as the input size grows, ignoring constant factors and lower-order terms to capture only the asymptotic trend. O(n log n) means that for large n the time grows no faster than a constant multiple of n log n.
难度 进阶 · 适合 大众
CC BY 4.0 · 已核验 · Verified 2026-10-03 · 2 条独立证据
来源 · Source
Cormen《算法导论》第3章 (机械工业出版社)
T. Cormen et al., Introduction to Algorithms (CLRS), 4th ed., Chapter 3 (Growth of Functions)
独立核验依据 · Independent verification: 核验依据 1 ISBN 978-0-262-04630-5 · 核验依据 2 ISBN 9780691079516 (1957)
#大O #复杂度 #渐进分析
归并排序为什么是稳定的排序算法?
Why is merge sort a stable sorting algorithm?
归并排序采用分治，把序列递归拆到单个元素再两两合并，合并时遇到相等元素总是优先取前半部分（左边）的元素。因为相等键的相对顺序在合并中保持不变，所以整体排序是稳定的。
Merge sort uses divide and conquer, recursively splitting down to single elements and then merging pairs, and during a merge it always takes the element from the left half first when keys are equal. Because equal keys keep their relative order, the whole sort is stable.
难度 进阶 · 适合 初中(12-15)
CC BY 4.0 · 来源待核验 · Source pending review
来源 · Source
出处备注：著录含书名，但缺版次 / 出版社 / 年份中的一部分，需编辑补全后才能做独立比对。
Knuth《计算机程序设计艺术》第3卷 排序与查找 (国防工业出版社)
D. Knuth, The Art of Computer Programming, Volume 3 (Sorting and Searching), Section 5.2.4 (Merge Sorting)
独立核验依据 · Independent verification: 核验依据 1 ISBN 9787115360670（豆瓣书目条目） · 核验依据 3 ARCHIVE 标识 B-001-002-138-NLA：The Art of Computer Program
#归并排序 #稳定性 #分治
哈希表中发生哈希冲突时，链地址法是如何处理的?
When a hash collision occurs in a hash table, how does separate chaining handle it?
链地址法让每个桶存放一个链表（或动态结构），所有映射到同一桶的元素都挂在对应的链表上。查找时先通过哈希定位桶，再在链表内顺序比较键，因此冲突只会增加链表长度而不影响其他桶。
Separate chaining gives each bucket a linked list into which all keys hashing to that bucket are inserted. To look up a key you first locate the bucket by hash and then scan the list linearly, so collisions only lengthen one list rather than affecting other buckets.
难度 进阶 · 适合 大众
CC BY 4.0 · 已核验 · Verified 2026-10-03 · 2 条独立证据
来源 · Source
Cormen《算法导论》第11章 (机械工业出版社)
T. Cormen et al., Introduction to Algorithms (CLRS), 4th ed., Chapter 11 (Hash Tables)
独立核验依据 · Independent verification: 核验依据 1 ISBN 978-0-262-04630-5 · 核验依据 2 ISBN 9780691079516 (1957)
#哈希表 #冲突 #链地址法