替代大O符號？

Question

下午好一切，

我們說一個hashtable有O（前提是我們有鑰匙）（1）查找，而linked list有O（1）下一個節點查找（前提是我們有一個參考到當前節點）。

然而，由於如何Big-O notation作品，這不是在表達（或分化）的算法X的成本是非常有用的，VS的算法X +米的成本。

例如，即使我們的標籤的哈希表的查找和鏈表的查找爲O（1）這兩個，這兩個O（1）■歸結到一個非常不同數量的確實步驟，

的鏈接列表的查找固定爲x步驟數。但是，哈希表的查找是變量。哈希表的查找的成本取決於散列函數的成本，所以爲哈希表的查找所需的步驟數是：X +米，

1. 其中X是固定數目

2. 和米是未知可變值

換句話說，即使我們所說的兩種操作O（1），哈希表的查找成本是幅度比鏈表的查找的成本較高。

的大O符號是具體地約輸入數據集合的大小。這確實有它的優點，但它也有它的缺點，如我們將所有非變量歸併爲1時我們可以看到的。我們不能再看到它裏面的m變量（哈希函數）。

除了大O符號，有另一個（建立）的符號，我們可以使用用於表達固定成本O（1），這意味着X操作和可變成本O（1），這意味着x + m（m，散列函數）的操作次數？

Answer 1

問題是「操作次數」與上下文高度相關。事實上，這就是爲什麼大-O符號被髮明出來的原因 - 它在模擬大量計算機方面似乎工作得很好。除此之外，程序員「操作」的數量並不意味着它實際需要多少時間（例如，它是否已經在緩存中？）或者硬件實際需要多少步驟（你的處理器做了什麼？ - 它是否有微操作？），甚至有多少操作被指定給處理器（你的編譯器爲你做了什麼？）。即使你試圖定義一個抽象的精確概念以便有用，這些都是關注點。

所以。現在，它是Big-O與「運營」 - 無論「運營」在當時對您和您的同事意味着什麼。

Answer 2

字面O（1），這意味着正好1操作

除了它沒有。大的O-Notation涉及與輸入相關的複雜性的相對比較。如果算法確實需要一個固定的步驟數量，完全獨立於輸入的大小，那麼確切的步驟數量並不重要。

看一看O（n）的（正規）的定義：

這意味着：有一定的k使得對於每個n功能f比函數g較小。

在上述情況下，散列表查找和鏈接列表查找將是f，而g將是g(n) = 1。對於每種情況，您都可以找到f(n) <= g(n) * k的k。

現在，這個k不需要固定，它可以根據平臺，實現，具體硬件而有所不同。唯一有趣的一點是它存在。這就是爲什麼哈希表查找和鏈表節點查找都是O（1）：無論輸入如何，它們都具有恆定的複雜度。當評估算法時，這是有趣的，而不是物理步驟。

具體地關於哈希表查找

是，散列函數確實需要的操作（根據實現）的可變量。但是，根據輸入的大小，它不需要進行可變數量的操作。 Big O-Nation具體約爲輸入數據集合大小。散列函數需要單個元素。對於算法的評估，如果操作次數沒有隨着輸入大小而增加，則某個函數需要10,20,50或100次操作並不重要，它是O（1）。沒有辦法在大的O-Notation中區分這一點，因爲這不是什麼大的O-Notation。

Answer 3

「〜」包含常數因子 - 見the family of bachmann functions