clrs

2熱度

1回答

這個問題是從CLRS PG 362 整體最佳的解決方案結合了兩個相關的子問題的最佳解決方案相關的動態規劃和具體杆切削的問題。整體最佳解決方案是通過尋找最佳的解決方案，以個別子問題，然後以某種方式俱樂部他們。我無法理解直覺和概念。任何鏈接，例子？感謝

3熱度

1回答

最大重疊點

假設我們希望跟蹤一組間隔中的最大重疊點 - 數據庫中具有最大間隔數的點與其重疊。 a。顯示總是有一個最大重疊點，它是其中一個段的終點。 b。設計一個有效支持INTERVAL-INSERT，INTERVAL-DELETE和FIND-POM操作的數據結構，它返回最大重疊點。（提示：保留所有端點的紅黑樹，將值+1與每個左端點相關聯，並將值-1與每個正確的端點相關聯。使用一些額外信息增加樹的每個節點以維

2熱度

2回答

爲什麼17612864的14個最重要的位是67？

在CLRS的第264頁的底部，作者說在獲得r0 = 17612864之後，r0的14個最高有效位產生散列值h（k）= 67。我不明白爲什麼它給出了67，因爲67以二進制是1000011這是7位。 EDIT 在教科書：作爲一個例子，假設我們有K = 123456，P = 14，M = 2^14 = 16384，以及w = 32適應Knuth的建議，我們選擇A是（\ sqrt（5） - 1）/ 2最

4熱度

1回答

最大和快速排序

的最小深度這是CLR的（算法導論）問題的問題去如下：假設在快速排序的每一級的分裂是在比例1 - αα，其中， 0 <α≤1/2是一個常數。表明，在遞歸樹中的葉的最小深度爲大約 - LG N/LGα和最大深度爲約-lg N/LG（1 - α）。（不要擔心整數四捨五入）。http://integrator-crimea.com/ddu0043.html 我沒有得到如何實現這個解決方案。根據鏈接他們

0熱度

1回答

動態集合中的後繼和前代最壞情況運行時間

以下動態集合運算的漸近最差情況運行時間是多少？後續（L，X）爲未分選的單獨&雙向鏈表前身（L，X）爲未排序雙向鏈表 L：列表中，x：指針的條目（其實這是本書第10-1題的一部分：「算法導論，第三版」，我搜索了答案，答案是O（n），但我找不到任何解釋）

2熱度

1回答

爲什麼我們不在紅黑樹插入中添加黑節點而不是紅節點？

在紅黑樹插入，我們總是選擇添加一個新的節點爲紅色，以便我們能夠避免改變樹的黑色高度。爲什麼這比添加黑節點更可取？

0熱度

2回答

從CLRS

的運動了解的運行時間分析，下面是我在尋找一個答案的問題：數組A [1個... N]包含所有從0到n的整數只有一個除外。通過使用輔助數組B [0 ... n]來記錄哪些數字出現在A中，可以很容易地確定O（n）時間中缺失的整數。但是，在這個問題中，我們無法訪問整個整數在一個單一的操作。 A的元素爲，用二進制表示，我們唯一可用來訪問它們的操作是「獲取A [i]的第j位」，其中需要恆定的時間。

2熱度

3回答

前邊緣在無向圖

CLRS - 第22章定理22.10 在深度優先搜索的無向圖G，G的每一條邊是採用樹邊緣或背邊緣。證明設（u，v）是G的任意一條邊，並且假設沒有損失概率，即u.d < v.d.然後，搜索必須發現並完成v 才能完成u（而u是灰色的），因爲v在u的鄰接列表中。如果第一次搜索探測邊緣（u，v），它在從u到v的方向，則v未被發現（白色），直到時間，否則搜索將已經探索到該邊緣已經在從v到u的方

2熱度

1回答

CLRS第二版中的紅黑樹刪除修復，Clojure

我正在CLRS第二版，第四版印刷，第288-9頁之後爲間隔樹實施紅黑樹刪除。摘要錯誤的： RB-刪除 - Fixup時如果x和w是前哨淋巴結，這是RB-刪除的可能的結果，那麼顏色（左的評價（w）的）和RB-Delete-Fixup中的顏色（右（w））在while循環的第一次迭代中遭受空指針異常。 (if (and (= (get-color (get-left @w)) black)

2熱度

3回答

遞歸矩陣乘法

我正在閱讀CLRS算法簡介。書示出了用於簡單分僞代碼而治之矩陣乘法： n = A.rows let c be a new n x n matrix if n == 1 c11 = a11 * b11 else partition A, B, and C C11 = SquareMatrixMultiplyRecursive(A11, B11) + Square