“幾乎可以忽略不計”是什麼意思？
我在論文“多項式函式的同態簽名”中遇到了這樣一句話，即“幾乎可以忽略不計的機率”會發生某些事情。但是，我無法完全弄清楚它們到底是什麼意思。我知道以微不足道的機率發生的事情的定義，它是“幾乎”讓我失望的事情。在他們引用的論文中，描述了它以機率發生 $ 1-2^{-\Omega(n)} $ ，所以我認為這一定是它發生的可能性幾乎可以忽略不計的定義？但是，我不知道它們是什麼意思 $ \Omega(n) $ ，我似乎無法在論文中找到定義。有人可以幫我收拾東西嗎？
$ \Omega(n) $ 是來自同一家族的數學符號 $ O(n) $ 來自。
回顧， $ O(n) $ 是從上面限定的；也就是說，如果我們這樣說 $ f(n) = O(g(n)) $ ，我們實際上要說的是，對於所有足夠大的 $ n $ , 存在一個常數 $ c > 0 $ 這樣 $ f(n) < c \cdot g(n) $ ， 那是， $ f(n) $ 增長速度不超過 $ g(n) $ .
$ \Omega(n) $ 是相同的，只是它是從下面界定的；也就是說，如果我們這樣說 $ f(n) = \Omega(g(n)) $ , 那麼（對於所有足夠大的 $ n $ ) 存在一個常數 $ c > 0 $ 這樣 $ f(n) > c \cdot g(n) $ ， 那是， $ f(n) $ 至少增長得一樣快 $ g(n) $ .
因此，當他們說 $ 1 - 2^{-\Omega(n)} $ , 有一個常數 $ c $ 這樣成功的機率總是 $ > 1 - 2^{-cn} $ （除了可能很小 $ n $ ); 因此，對於大 $ n $ ，機率相當高（但是，這並沒有說明“大”在這種情況下的含義:-)
如果您想知道，來自同一個家庭，我們也有“小哦”符號 $ f(n) = o(g(n)) $ （“f 的增長速度嚴格慢於 g”），小歐米茄表示法 $ f(n) = \omega(g(n)) $ （“f 的增長速度嚴格快於 g”）和 theta 表示法 $ f(n) = \Theta(g(n))) $ （“在乘法上限和下限內，f 的增長速度與 g 一樣快”）