大歐米茄和小歐米茄問題
我在Katz 和 Lindell的《現代密碼學簡介》第 2版（第 3版）的第 538 頁（第 576 頁）上找到了這一點。範例 A.6下的第三個要點說：
$$ \begin{array}{l}\text{Let }f(n)=n^4+3n+500.\text{ Then:}\ \quad\text{(…)}\ •;; f(n) = Ω(n^3 \log n).\text{ In fact, }f(n) = ω(n^3 \log n).\end{array} $$
我只是在尋找關於這意味著什麼的高級解釋，而不是數學證明或其他東西。
現在問題中引用的第一行定義了一個函式 $ f $ 變數的 $ n $ . 最後一行是關於該函式在何時增長的速度（輸出） $ n $ 向著 $ +\infty $ .
兩種說法 $ f(n) = Ω(n^3 \log n) $ 和 $ f(n) = ω(n^3 \log n) $ 是關於多快 $ f(n) $ 相對函式增長 $ g $ 被定義為 $ g(n)=n^3\log n $ . 第一條語句大致說明 $ f(n) $ 增長速度不低於 $ g(n) $ ，而第二個告訴 $ f(n) $ 長得更快。這兩個陳述都是正確的，並且很容易證明，所以當我們查看 $ f $ 和 $ g $ .
更新以下評論：
- 該聲明是嚴格關於所採取的價值 $ f(n) $ ，而不是計算的難度（時間、空間、成本） $ f $ . 那個值是什麼 $ f(n) $ 表示符號未說明。它不是定義的一部分 $ f $ . 可以通過定義數量來說明 $ f(n) $ 代表。這通常是某個算法佔用的時間或空間。它可以是一個整數的值，例如 RSA 公共模數。這在問題中或在整個附錄 A.2 中以及問題的引用中都沒有說明。
- “增長更快”與“更大”並不完全相同。抱歉，準確地說，我們需要數學定義。
那是使用所謂的(Bachmann-)Landau 表示法，它不尋常地使用 $ = $ 符號：平等通常具有及物性。需要一些時間來適應它。
任何更具體的內容都不符合問題中的“高級解釋”要求。但是，如果我們閱讀書中問題引述上方的幾行，或者關於(Bachmann-)Landau notation的內容，就會給出定義。
它擁有 $ f(n) = ω(g(n));\implies;f(n) = Ω(g(n)) $ . 這就是為什麼這句話有 $ \text{in fact} $ ，通常用於介紹更強有力或更精確的陳述，例如：那很好。事實上，它很好吃。
粗略地說，這個符號意味著當 $ n $ 成長： $$ \begin{array}{ll} f(n) = \omega(g(n))&f(n)\text{ grows faster than }g(n)\ f(n) = \Omega(g(n))&f(n)\text{ grows no slower than }g(n)\ f(n) = \Theta(g(n))&f(n)\text{ grows as fast as }g(n)\ f(n) = \mathcal O(g(n))&f(n)\text{ grows no faster than }g(n)\ f(n) = o(g(n))&f(n)\text{ grows slower than }g(n)\ \end{array} $$