線性結構是最好的分類生產嗎？

Question

通常考慮一種排序方法產品線性排序產品（如「1,7,8,13,109 ...」），其中消費O(N)進行查詢。

爲什麼不能在排序非線性順序，消費O(logN)或通過迭代或牛頓法等找到元素？製造這樣的高階排序結構是否昂貴？

簡而言之，對排序結果進行排序可以通過尋找ax^2 + bx + c = 0的根來訪問嗎？ （相比之下，通常它會找到ax + c = 0的根。）例如，我們有x1 = 1, x2 = 2作爲二次方程的根，並插入以下xi(s)。然後可以使用更智能的方式進行查詢。

---

我想困難可以通過這些方面會遇到：數據

1. 預測可能比較硬。因此我們不能構建一個通用公式來很好地描述以下數字（可能是散列值）。

2. 由於第一個難度，數字出一定範圍可以發散。由Google繪製的示例：the graph.從[-1,3]中導出的值非常大，以及執行原始公式時難度的快速增加。

3. 這實際上相當於散列，它創建一個包含值的表。生產規則是一個公式。

4. 由於算法本身的複雜性，執行「更智能」的查詢可能會很昂貴。

Answer 1

利用已知統計分佈的智能方案通常會更快一些。然而，這仍然使它們保持在O（log N），這與平凡的二進制搜索相同。原因在於，在每個步驟中，他們通常會縮小要搜索的元素的範圍R> 2，以進行簡單的二元搜索，即R = 2。但是你需要log（N）/ log（R）步驟將其縮小到恰好一個元素。

現在，這是否是一場網絡勝利取決於日誌（R）與每一步所需的工作。一個簡單的比較（二進制搜索）需要幾個週期。只要您需要比+ - * /（比如說exp或log）更復雜的預測下一個元素的位置，那麼需要更少步驟的收益就會消失。

因此，總之：使用二進制搜索是因爲對於許多真實世界的分佈，每一步都是有效的。