Python 大O符號(hào)

必須分析算法的效率和準(zhǔn)確性，以便對(duì)它們進(jìn)行比較，并為特定場(chǎng)景選擇特定的算法。進(jìn)行這種分析的過(guò)程稱為漸近分析。它是指以數(shù)學(xué)計(jì)算單位計(jì)算任何操作的運(yùn)行時(shí)間。例如，一個(gè)操作的運(yùn)行時(shí)間被計(jì)算為f（n），并且可能針對(duì)另一個(gè)操作被計(jì)算為g（n2）。這意味著第一次運(yùn)行時(shí)間將隨著n的增加而線性增加，第二次運(yùn)行的運(yùn)行時(shí)間將隨著n的增加呈指數(shù)增長(zhǎng)。同樣，如果n很小，兩個(gè)操作的運(yùn)行時(shí)間將幾乎相同。

通常，算法所需的時(shí)間分為三種類型 -

• 最佳案例 - 程序執(zhí)行所需的最短時(shí)間。
• 平均情況 - 程序執(zhí)行所需的平均時(shí)間。
• 最差情況 - 程序執(zhí)行所需的最長(zhǎng)時(shí)間。

漸近符號(hào)

以下是計(jì)算算法運(yùn)行時(shí)間復(fù)雜度的常用漸近符號(hào)。

• Ο表示法
• Ω符號(hào)
• θ符號(hào)

大O符號(hào)

符號(hào)Ο（n）是表達(dá)算法運(yùn)行時(shí)間上限的形式化方式。它測(cè)量算法可能需要完成的最壞情況時(shí)間復(fù)雜度或最長(zhǎng)時(shí)間。

例如，對(duì)于函數(shù) f （n）

Ο( _f_ (n)) = { _g_ (n) : there exists c > 0 and n0 such that _f_ (n) ≤ c. _g_ (n) for all n > n0. }

歐米茄符號(hào)Ω

符號(hào)Ω（n）是表達(dá)算法運(yùn)行時(shí)間下限的形式化方式。它可以衡量算法可能需要完成的最佳案例時(shí)間復(fù)雜度或最佳時(shí)間量。

例如，對(duì)于函數(shù) f （n）

Ω( _f_ (n)) ≥ { _g_ (n) : there exists c > 0 and n0 such that _g_ (n) ≤ c. _f_ (n) for all n > n0. }

Theta符號(hào)θ

符號(hào)θ（n）是表達(dá)算法運(yùn)行時(shí)間的下限和上限的形式化方式。它表示如下 -

θ( _f_ (n)) = { _g_ (n) if and only if _g_ (n) =  Ο( _f_ (n)) and _g_ (n) = Ω( _f_ (n)) for all n > n0. }

常用的漸近符號(hào)

以下是一些常見漸近符號(hào)的列表 -