1.讓我們了解大O符號的含義是什么?

在算法中執(zhí)行許多操作。這些操作可能包括遍歷集合，復(fù)制項目或整個集合，將項目追加到集合中，在集合的開始或結(jié)尾處插入項目，刪除項目或更新集合中的項目。

Big-O衡量算法運算的時間復(fù)雜度。它測量算法計算所需運算所需的時間。盡管我們也可以測量空間復(fù)雜度(算法占用多少空間)，但本文將重點介紹時間復(fù)雜度。

用最簡單的術(shù)語來說，BigO表示法是一種基于輸入大小(稱為n)來衡量操作性能的方法。

2.BigO表示法有何不同?

我們需要熟悉許多常見的BigO符號。

讓我們考慮n為輸入集合的大小。就時間復(fù)雜度而言：

O(1)：無論您的集合有多大，執(zhí)行操作所花費的時間都是恒定的。這是恒定的時間復(fù)雜度符號。這些操作盡可能快。例如，檢查集合內(nèi)部是否有任何項目的操作是O(1)操作。

O(logn)：當(dāng)集合的大小增加時，執(zhí)行操作所花費的時間對數(shù)增加。這是對數(shù)時間復(fù)雜度表示法。潛在優(yōu)化的搜索算法為O(logn)。

O(n)：執(zhí)行操作所需的時間與集合中的項目數(shù)成線性正比。這是線性時間復(fù)雜度符號。就性能而言，這介于兩者之間或中等。作為一個實例，如果我們想對一個集合中的所有項目求和，那么我們將不得不遍歷該集合。因此，集合的迭代是O(n)操作。

(nlogn)：執(zhí)行某項操作的性能是集合中項目數(shù)量的擬線性函數(shù)。這稱為準(zhǔn)線性時間復(fù)雜度表示法。優(yōu)化排序算法的時間復(fù)雜度通常為n(logn)。

O(n平方)：執(zhí)行操作所需的時間與集合中項目的平方成正比。這稱為二次時間復(fù)雜度表示法。

(n!)：當(dāng)在操作中計算集合的每個單個排列時，因此執(zhí)行操作所需的時間取決于集合中項目的大小。這稱為階乘時間復(fù)雜度表示法。非常慢。

該圖像概述了Big-O符號。

O(1)很快。O(n平方)很慢。O(n!)非常慢。

大O符號是相對的。大O表示法與機(jī)器無關(guān)，忽略常量，并且被包括數(shù)學(xué)家，技術(shù)人員，數(shù)據(jù)科學(xué)家等在內(nèi)的廣泛讀者所理解。

最佳，平均，最差情況

當(dāng)我們計算操作的時間復(fù)雜度時，我們可以根據(jù)最佳，平均或最壞情況產(chǎn)生復(fù)雜度。

最佳情況方案：顧名思義，這是當(dāng)數(shù)據(jù)結(jié)構(gòu)和集合中的項目以及參數(shù)處于最佳狀態(tài)時的方案。例如，假設(shè)我們要在集合中找到一個項目。如果該項目恰好是集合的第一項，那么這是該操作的最佳情況。

平均情況是根據(jù)輸入值的分布定義復(fù)雜度。

最壞的情況是可能需要一種操作，該操作需要在大型集合(例如列表)中找到位于最后一個項目的項目，并且算法會從第一個項目開始對集合進(jìn)行迭代。

以上內(nèi)容為大家介紹了Python數(shù)據(jù)結(jié)構(gòu)的時間復(fù)雜性，希望對大家有所幫助，如果想要了解更多Python相關(guān)知識，請關(guān)注IT培訓(xùn)機(jī)構(gòu):千鋒教育。http://m.2667701.com/