三元搜索的平均情況複雜度

我需要解決三元搜索的平均情況複雜度。在最壞的情況下，你會做兩個比較，所以我假定最壞情況的複雜性是這樣的：三元搜索的平均情況複雜度

C(n) = C(n/3) + 2

然後可以證明是O（LOGN），但是你會在平均情況是什麼樣子？我想可能是這樣的：

C(n) = C(n/3) + 1.5

因爲您平均可能做1〜2比較，以便（1 + 2）/ 3 = 1.5

來源

2013-10-07 dood

不是三元搜索*總是*每次迭代執行兩次查找？ – templatetypedef

@templatetypedef你爲什麼需要？如果（e <數據[n/3]）看起來還有其他的話，如果（e <數據[2n/3]）看起來中間還有其他的看起來是正確的（好吧，稍微複雜一點考慮平等，但是相同數量的比較）。 – Dukeling

我覺得你在三元搜索中混淆了三元搜索TREE。你的問題和澄清對於一棵樹來說是有意義的，但對於一般的三元搜索來說並不合適。 –

如果我們都在談論搜索的元素被排序的陣列，我認爲平均來說你必須做5/3的比較。假設您首先檢查要找到的元素x是高於還是低於放置在A（n/3）中的元素，其中A是您的排序數組，n是其長度。統計上，由於1/3的元素低於A（n/3），2/3高，因此x有1/3的機會降低，2/3的機會更高。如果x較低，則不需要進行第二次比較，所以您只需要1. x越高，您需要將其與A（2n/3）進行比較，因此您需要2. 所以平均來說，你需要（1/3）* 1 +（2/3）* 2 = 5/3。

但是，這並沒有改變任何東西的全球複雜性，這將永遠是O（log n）。唯一的區別將是恆定的因素。

來源

2013-10-07 07:13:12 Traklon

三元搜索的平均情況複雜度

回答

相關問題