更好地理解大 O 指的是什麼
我以為我對大 O 表示法的理解相對較好，但現在我不確定。特別是，我看過幾篇類似這樣的文章，討論離散對數問題（可能）是如何困難的，因為我們最好的算法在位數方面是指數級的。
如果我理解正確，找到一個 $ x $ 給定一個整數 $ y $ ， 發電機 $ g $ 和素數 $ p $ 英石 $$ g^x \equiv y\ \mod{p} $$ 最多需要 $ O(p) $ 試驗。但如果 $ p $ 是 $ k $ 位然後執行時間實際上是 $ O(2^k) $ .
我很難理解為什麼我們決定用位數來表示執行時。例如，排序可以在 $ O(n\log n) $ 時間在哪裡 $ n $ 是類數組結構中元素的數量。出色地 $ n $ 也有 $ k $ 位，這意味著執行時是 $ O(k*2^k) $ ; 排序是指數的？我顯然錯過了一些東西，所以任何幫助將不勝感激。
我們用位數來寫它，因為它準確地模擬了電腦如何工作的現實。電腦本身不支持在 1 個時間步中添加任意大小的數字。相反，他們將這些操作分解為不斷增加的數字（為簡單起見說位），然後使用這些作為一些算法的基礎來添加更大的數字。本質上，為了衡量某些算法的時間複雜度，我們需要說明哪些操作“花費”了 1 個時間步，並且我們做出的任何選擇都應該以電腦在實踐中的建構方式為依據。
您還稍微誤解了排序的複雜性。諸如快速排序之類的狀態表明您可以對 $ n $ -元素數組使用 $ O(n\log n) $ 比較。但是每次比較的成本是多少？如果數組中的所有元素都假定為恆定大小，則這是 $ O(1) $ , 所以整體時間複雜度為 $ O(n\log n) $ .
但是如果數組中元素的大小隨著整個數組的增長而增長呢？如果你有一個數組 $ n $ 元素，每個元素都是一個 $ n $ - 位數，快速排序仍然適用 $ O(n\log n) $ 比較。但是，每次比較的成本是多少？在位操作方面，應該是 $ O(n) $ 時間。因此，對該數組進行排序的複雜性是： $$ O(n\log n) \text{ comparisons} \times O(n) \frac{\text{time}}{\text{comparison}} = O(n^2\log n)\text{ time} $$ 所以排序這個數組其實就是 $ O(n^2\log n) $ 時間。
在您的範例中，您是對的 $ O(p) $ 試驗。如果 $ p $ 是 $ 2^k $ 位，為什麼這應該是“指數”？考慮算法的最基本部分，即設置一些計數器 $ i = 0 $ , 並一直遞增到 $ p $ . 算法的這個簡單部分需要多少位操作？雖然這聽起來像是一個愚蠢的問題，但實際設計算法並評估其成本（就位操作而言）可能對您的理解有用。