摘要

本文介紹了CPython中數(shù)據(jù)結(jié)構(gòu)的關(guān)鍵操作的Big-O表示法。 big-o標(biāo)記本質(zhì)上是一種衡量操作時(shí)間復(fù)雜度的方法。 本文還說(shuō)明了列表，集合和字典的許多常用操作。

為算法設(shè)計(jì)和選擇正確的數(shù)據(jù)結(jié)構(gòu)至關(guān)重要。

希望能幫助到你。

為什么我們需要知道時(shí)間復(fù)雜性?

對(duì)于數(shù)據(jù)科學(xué)家程序員而言，為工作選擇正確的數(shù)據(jù)結(jié)構(gòu)至關(guān)重要。 特別是，如果算法需要大量計(jì)算，例如訓(xùn)練機(jī)器學(xué)習(xí)模型的算法或處理大量數(shù)據(jù)的算法，那么確保選擇合適的數(shù)據(jù)結(jié)構(gòu)時(shí)要特別小心。

選擇正確的數(shù)據(jù)類(lèi)型通常會(huì)被忽略，并且最終會(huì)嚴(yán)重影響應(yīng)用程序的性能。

文章目的

本文介紹了CPython中數(shù)據(jù)結(jié)構(gòu)的關(guān)鍵操作的Big-O表示法。 big-O表示法是一種衡量操作時(shí)間復(fù)雜度的方法。

1.讓我們了解大O符號(hào)的含義是什么?

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

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

用最簡(jiǎn)單的術(shù)語(yǔ)來(lái)說(shuō)，Big O表示法是一種基于輸入大小(稱(chēng)為n)來(lái)衡量操作性能的方法。

2. Big O表示法有何不同?

我們需要熟悉許多常見(jiàn)的Big O符號(hào)。

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

• O(1)：無(wú)論您的集合有多大，執(zhí)行操作所花費(fèi)的時(shí)間都是恒定的。 這是恒定的時(shí)間復(fù)雜度符號(hào)。 這些操作盡可能快。 例如，檢查集合內(nèi)部是否有任何項(xiàng)目的操作是O(1)操作。
• O(log n)：當(dāng)集合的大小增加時(shí)，執(zhí)行操作所花費(fèi)的時(shí)間對(duì)數(shù)增加。 這是對(duì)數(shù)時(shí)間復(fù)雜度表示法。 潛在優(yōu)化的搜索算法為O(log n)。
• O(n)：執(zhí)行操作所需的時(shí)間與集合中的項(xiàng)目數(shù)成線(xiàn)性正比。 這是線(xiàn)性時(shí)間復(fù)雜度符號(hào)。 就性能而言，這介于兩者之間或中等。 作為一個(gè)實(shí)例，如果我們想對(duì)一個(gè)集合中的所有項(xiàng)目求和，那么我們將不得不遍歷該集合。 因此，集合的迭代是O(n)操作。
• (n log n)：執(zhí)行某項(xiàng)操作的性能是集合中項(xiàng)目數(shù)量的擬線(xiàn)性函數(shù)。 這稱(chēng)為準(zhǔn)線(xiàn)性時(shí)間復(fù)雜度表示法。 優(yōu)化排序算法的時(shí)間復(fù)雜度通常為n(log n)。
• O(n平方)：執(zhí)行操作所需的時(shí)間與集合中項(xiàng)目的平方成正比。 這稱(chēng)為二次時(shí)間復(fù)雜度表示法。
• (n!)：當(dāng)在操作中計(jì)算集合的每個(gè)單個(gè)排列時(shí)，因此執(zhí)行操作所需的時(shí)間取決于集合中項(xiàng)目的大小。 這稱(chēng)為階乘時(shí)間復(fù)雜度表示法。 非常慢。

該圖像概述了Big-O符號(hào)。

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

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

最佳，平均，最差情況

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

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

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

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

Python集合和時(shí)間復(fù)雜度

在本文的這一部分中，我將記錄CPython中的常見(jiàn)集合，然后概述它們的時(shí)間復(fù)雜性。

我將特別關(guān)注平均情況。

1.List

List是迄今為止Python中最重要的數(shù)據(jù)結(jié)構(gòu)之一。 我們可以將列表用作堆棧(添加的最后一項(xiàng)是第一項(xiàng))或隊(duì)列(添加的第一項(xiàng)是第一項(xiàng))。 列表是有序且可變的集合，因?yàn)槲覀兛梢噪S意更新項(xiàng)目。

讓我們回顧一下常見(jiàn)列表操作及其Big-O表示法

• 插入：Big-O表示法是O(n)
• 獲取項(xiàng)目：Big-O表示法為O(1)
• 刪除項(xiàng)目：Big-O表示法是O(n)
• 迭代：Big-O表示法是O(n)
• 獲得長(zhǎng)度：Big-O表示法為O(1)

2.Set

集合也是Python中使用最廣泛的數(shù)據(jù)集合之一。 集合本質(zhì)上是無(wú)序集合。 集合不允許重復(fù)，因此集合中的每個(gè)項(xiàng)目都是唯一的。 集合支持許多數(shù)學(xué)運(yùn)算，例如聯(lián)合，差，集合的交集等。

讓我們回顧一下通用Set操作

• 檢查集合中的項(xiàng)目：Big-O表示法是O(1)
• 集合A與集合B的區(qū)別：大O表示法是O(A的長(zhǎng)度)
• 集A和B的交集：大O表示法是O(A或B的長(zhǎng)度的最小值)
• 集A和B的并集：相對(duì)于長(zhǎng)度(A)+長(zhǎng)度(B)，它的Big-O表示法是O(N)

3.Dict 字典

最后，我想提供字典數(shù)據(jù)收集的概述。 字典是鍵值對(duì)集合。 鍵在字典中是唯一的，以防止項(xiàng)目沖突。 這是非常有用的數(shù)據(jù)收集。

字典由鍵索引，其中鍵可以是字符串，數(shù)字甚至是帶有字符串，數(shù)字或元組的元組。

我們可以對(duì)字典執(zhí)行許多操作，例如存儲(chǔ)鍵的值，或基于鍵檢索項(xiàng)目，或遍歷項(xiàng)目等。

讓我們回顧一下常見(jiàn)的詞典時(shí)間復(fù)雜度：

在這里，我們認(rèn)為該密鑰用于獲取，設(shè)置或刪除項(xiàng)目。

• 獲取項(xiàng)目：Big-O表示法為O(1)
• 設(shè)定項(xiàng)目：Big-O表示法是O(1)
• 刪除項(xiàng)目：Big-O表示法是O(1)
• 遍歷字典：Big-O表示法是O(n)