What & How & Why

您在这里: start » cs » dsa » courses » gtx_1332x » ii_non_linear

差别

这里会显示出您选择的修订版和当前版本之间的差别。

到此差别页面的链接

两侧同时换到之前的修订记录前一修订版
后一修订版		前一修订版
cs:dsa:courses:gtx_1332x:ii_non_linear:start [2024/03/25 12:17] – [Quadratic Probing] codingharecs:dsa:courses:gtx_1332x:ii_non_linear:start [2024/04/14 14:21] (当前版本) – [原理：双子节点的情况] codinghare
行 200: 行 200:
 //Predecessor//（**最大前继**） 是指在 BST 中，比 root **小**的节点中**最大**的一个节点；而 //Successor//（**最大后继**） 是指在 BST 中，比 root **大**的节点中**最小**的一个节点。比如下面 BST 中的 ''21'' 和 ''30'' 就是 root ''24'' 的最大前继和最小后继： //Predecessor//（**最大前继**） 是指在 BST 中，比 root **小**的节点中**最大**的一个节点；而 //Successor//（**最大后继**） 是指在 BST 中，比 root **大**的节点中**最小**的一个节点。比如下面 BST 中的 ''21'' 和 ''30'' 就是 root ''24'' 的最大前继和最小后继：
 \\ \\  \\ \\ 
-{{ :cs:dsa:courses:gtx_1332x:ii_non_linear:prede_n_successor.svg?250 |}}+{{ :cs:dsa:courses:gtx_1332x:ii_non_linear:prede_n_successor_1_.svg?250 |}}
   * **//为什么要使用 Predecessor 和  Successor？该如何使用？//**   * **//为什么要使用 Predecessor 和  Successor？该如何使用？//**
 这种解决方案来源于一种很朴素的想法，化繁为简。首先可以明确的是，直接删除拥有两个子节点的节点，并且还要保证 BST 的结构不出问题，是非常困难的。但相比之下，删除只有一个子节点或者没有子节点的节点则非常简单。因此，相比直接删除节点，我们选择**替换**节点中的内容，而这正是使用 Predecessor 或 Successor 的精妙之处。 这种解决方案来源于一种很朴素的想法，化繁为简。首先可以明确的是，直接删除拥有两个子节点的节点，并且还要保证 BST 的结构不出问题，是非常困难的。但相比之下，删除只有一个子节点或者没有子节点的节点则非常简单。因此，相比直接删除节点，我们选择**替换**节点中的内容，而这正是使用 Predecessor 或 Successor 的精妙之处。
行 480: 行 480:
 </WRAP> </WRAP>
 ===Quadratic Probing=== ===Quadratic Probing===
-//Linear Probing// 带来的问题被称为 //**primary clustering**（//turtling//）//。该问题指当 hash map 中**连续**的区域越来越大时（这是必然的，因为递增找空最终会将整个 hashmap 变为连续的区块。），我们每做一次 Probing 找空位都要跨越之前的连续区块。因此，我们需要一种更快的方式来找空位。+//Linear Probing// 带来的问题被称为 //**primary clustering**// (//turtling//)。该问题指当 hash map 中**连续**的区域越来越大时（这是必然的，因为递增找空最终会将整个 hashmap 变为连续的区块。），我们每做一次 Probing 找空位都要跨越之前的连续区块。因此，我们需要一种更快的方式来找空位。
 \\ \\  \\ \\ 
 一种方式是将之前计算 index 中的 ''(h + oriIndex) % backArray.length'' 更改为： 一种方式是将之前计算 index 中的 ''(h + oriIndex) % backArray.length'' 更改为：
  
 $$ $$
-\texttt{index = (h\^{}2 + oriIndex) mod backingArray.length} +\texttt{index = (h² + oriIndex) mod backingArray.length} 
 $$ $$
 +也就是 //Probing// 的实际次数会按照 //Probing// 的 step 的平方进行计算。我们将这样的 Probing 方式成为 //Quadratic Probing//。
 +==secondary clustering==
 +由于 //Quadratic Probing// 中 index 的计算方式是跳跃的，在某些情况下，该计算方式会导致 index 的计算结果一直在已经被占用的 index 之间来回横跳，从而导致 //Infinite Probing//。解决这个问题的两个策略：
 +  * resizing，直到 //Infinite Probing// 不再出现
 +  * 数学上，如果使用**质数**作为 Hash table 的长度，且 laoding factor 不超过 ''0.5''，则该种情况不会出现。
 +===Double Hashing===
 +//Double Hashing// 通过综合使用 linear / quadratic Probing，在降低 probing clustering 的同时，尽量优化了性能。通常，//Double Hashing// 包含两个 hash function：
 +  * $H(k)$：计算 index 的哈希函数：''h(k) % q''，''q'' 是小于哈希表长度的某个**质数**
 +  * $D(k)$: 基于 $H(k)$ 计算 probing 的值 ：''q - (h(k) % q''
 +<WRAP center round box 100%>
 +Linear Probing 可以被视作是 double hashing 的特殊形式。
 +</WRAP>
 +
 ====Preformance==== ====Preformance====
 ==SkipList== ==SkipList==
行 496: 行 509:
 ==Heap== ==Heap==
 ^Operation^Best^Average^Worst^ ^Operation^Best^Average^Worst^
-|Find Min / max|$O(1)$|$O(1)$|$O(1)$| +|**//Find Min// / max**|$O(1)$|$O(1)$|$O(1)$| 
-|Add|$O(1)$|$O(1)$|$O(n)/O(log(n))*$| +|**//Add//**|$O(1)$|$O(1)$|$O(n)/O(log(n))*$| 
-|Remove Min/max|$O(1)$|$O(log(n))$|$O(log(n))$| +|**//Remove Min/max//**|$O(1)$|$O(log(n))$|$O(log(n))$| 
-|Aribitray Search/Remove|$O(1)$|$O(n)$|$O(n)$| +|**//Aribitray Search//**/Remove|$O(1)$|$O(n)$|$O(n)$| 
-|BuildHeap|-$O(n)$|$O(n)$|$O(n)$| +|**//BuildHeap//**|-$O(n)$|$O(n)$|$O(n)$| 
-|Space Complexity|$O(n)$|$O(n)$|$O(n)$|+|**//Space Complexity//**|$O(n)$|$O(n)$|$O(n)$| 
 +==HashMap== 
 +^Operation^Best^Average^Worst^ 
 +|Put / Add New Key (Closed Addressing)|$O(1)$|$O(1)$|$O(n)$| 
 +|Put / Add New Key (Open Addressing)|$O(1)$|$O(1)$|$O(n)^*$ / $O(n^2)$| 
 +|Remove Key|$O(1)$|$O(1)$|$O(n)$| 
 +|Searching for a Key|$O(1)$|$O(1)$|$O(n)$| 
 +|Obtaining a KeySet|$O(1)$|$O(1)$|$O(n)$| 
 +|Obtaining a List of Values|$O(1)$|$O(1)$|$O(n)$| 
  • 最后更改: 2024/03/25 12:17
  • ©2022 YGwiki.com