建站
咨詢
售后
建站咨詢
新聞中心
摘要
公司專注于為企業(yè)提供網(wǎng)站設(shè)計、網(wǎng)站建設(shè)、微信公眾號開發(fā)、商城網(wǎng)站開發(fā)，重慶小程序開發(fā)，軟件按需定制設(shè)計等一站式互聯(lián)網(wǎng)企業(yè)服務。憑借多年豐富的經(jīng)驗，我們會仔細了解各客戶的需求而做出多方面的分析、設(shè)計、整合，為客戶設(shè)計出具風格及創(chuàng)意性的商業(yè)解決方案，創(chuàng)新互聯(lián)公司更提供一系列網(wǎng)站制作和網(wǎng)站推廣的服務。
本文介紹了CPython中數(shù)據(jù)結(jié)構(gòu)的關(guān)鍵操作的Big-O表示法。 big-o標記本質(zhì)上是一種衡量操作時間復雜度的方法。 本文還說明了列表，集合和字典的許多常用操作。
為算法設(shè)計和選擇正確的數(shù)據(jù)結(jié)構(gòu)至關(guān)重要。
希望能幫助到你。
為什么我們需要知道時間復雜性?
對于數(shù)據(jù)科學家程序員而言，為工作選擇正確的數(shù)據(jù)結(jié)構(gòu)至關(guān)重要。 特別是，如果算法需要大量計算，例如訓練機器學習模型的算法或處理大量數(shù)據(jù)的算法，那么確保選擇合適的數(shù)據(jù)結(jié)構(gòu)時要特別小心。
選擇正確的數(shù)據(jù)類型通常會被忽略，并且最終會嚴重影響應用程序的性能。
文章目的
本文介紹了CPython中數(shù)據(jù)結(jié)構(gòu)的關(guān)鍵操作的Big-O表示法。 big-O表示法是一種衡量操作時間復雜度的方法。
[[283387]]
1.讓我們了解大O符號的含義是什么?
在算法中執(zhí)行許多操作。 這些操作可能包括遍歷集合，復制項目或整個集合，將項目追加到集合中，在集合的開始或結(jié)尾處插入項目，刪除項目或更新集合中的項目。
Big-O衡量算法運算的時間復雜度。 它測量算法計算所需運算所需的時間。 盡管我們也可以測量空間復雜度(算法占用多少空間)，但本文將重點介紹時間復雜度。
用最簡單的術(shù)語來說，Big O表示法是一種基于輸入大小(稱為n)來衡量操作性能的方法。
2. Big O表示法有何不同?
我們需要熟悉許多常見的Big O符號。
讓我們考慮n為輸入集合的大小。 就時間復雜度而言：
- O(1)：無論您的集合有多大，執(zhí)行操作所花費的時間都是恒定的。 這是恒定的時間復雜度符號。 這些操作盡可能快。 例如，檢查集合內(nèi)部是否有任何項目的操作是O(1)操作。
- O(log n)：當集合的大小增加時，執(zhí)行操作所花費的時間對數(shù)增加。 這是對數(shù)時間復雜度表示法。 潛在優(yōu)化的搜索算法為O(log n)。
- O(n)：執(zhí)行操作所需的時間與集合中的項目數(shù)成線性正比。 這是線性時間復雜度符號。 就性能而言，這介于兩者之間或中等。 作為一個實例，如果我們想對一個集合中的所有項目求和，那么我們將不得不遍歷該集合。 因此，集合的迭代是O(n)操作。
- (n log n)：執(zhí)行某項操作的性能是集合中項目數(shù)量的擬線性函數(shù)。 這稱為準線性時間復雜度表示法。 優(yōu)化排序算法的時間復雜度通常為n(log n)。
- O(n平方)：執(zhí)行操作所需的時間與集合中項目的平方成正比。 這稱為二次時間復雜度表示法。
- (n!)：當在操作中計算集合的每個單個排列時，因此執(zhí)行操作所需的時間取決于集合中項目的大小。 這稱為階乘時間復雜度表示法。 非常慢。
該圖像概述了Big-O符號。
O(1)很快。 O(n平方)很慢。 O(n!)非常慢。
大O符號是相對的。 大O表示法與機器無關(guān)，忽略常量，并且被包括數(shù)學家，技術(shù)人員，數(shù)據(jù)科學家等在內(nèi)的廣泛讀者所理解。
最佳，平均，最差情況
當我們計算操作的時間復雜度時，我們可以根據(jù)最佳，平均或最壞情況產(chǎn)生復雜度。
最佳情況方案：顧名思義，這是當數(shù)據(jù)結(jié)構(gòu)和集合中的項目以及參數(shù)處于最佳狀態(tài)時的方案。 例如，假設(shè)我們要在集合中找到一個項目。 如果該項目恰好是集合的第一項，那么這是該操作的最佳情況。
平均情況是根據(jù)輸入值的分布定義復雜度。
最壞的情況是可能需要一種操作，該操作需要在大型集合(例如列表)中找到位于最后一個項目的項目，并且算法會從第一個項目開始對集合進行迭代。
Python集合和時間復雜度
在本文的這一部分中，我將記錄CPython中的常見集合，然后概述它們的時間復雜性。
我將特別關(guān)注平均情況。
1.List
List是迄今為止Python中最重要的數(shù)據(jù)結(jié)構(gòu)之一。 我們可以將列表用作堆棧(添加的最后一項是第一項)或隊列(添加的第一項是第一項)。 列表是有序且可變的集合，因為我們可以隨意更新項目。
讓我們回顧一下常見列表操作及其Big-O表示法
- 插入：Big-O表示法是O(n)
- 獲取項目：Big-O表示法為O(1)
- 刪除項目：Big-O表示法是O(n)
- 迭代：Big-O表示法是O(n)
- 獲得長度：Big-O表示法為O(1)
[[283389]]
Joshua Sortino在Unsplash上拍攝的照片
2.Set
集合也是Python中使用最廣泛的數(shù)據(jù)集合之一。 集合本質(zhì)上是無序集合。 集合不允許重復，因此集合中的每個項目都是唯一的。 集合支持許多數(shù)學運算，例如聯(lián)合，差，集合的交集等。
讓我們回顧一下通用Set操作
- 檢查集合中的項目：Big-O表示法是O(1)
- 集合A與集合B的區(qū)別：大O表示法是O(A的長度)
- 集A和B的交集：大O表示法是O(A或B的長度的最小值)
- 集A和B的并集：相對于長度(A)+長度(B)，它的Big-O表示法是O(N)
[[283390]]
fabio在Unsplash上的照片
3.Dict 字典
最后，我想提供字典數(shù)據(jù)收集的概述。 字典是鍵值對集合。 鍵在字典中是唯一的，以防止項目沖突。 這是非常有用的數(shù)據(jù)收集。
字典由鍵索引，其中鍵可以是字符串，數(shù)字甚至是帶有字符串，數(shù)字或元組的元組。
我們可以對字典執(zhí)行許多操作，例如存儲鍵的值，或基于鍵檢索項目，或遍歷項目等。
讓我們回顧一下常見的詞典時間復雜度：
在這里，我們認為該密鑰用于獲取，設(shè)置或刪除項目。
- 獲取項目：Big-O表示法為O(1)
- 設(shè)定項目：Big-O表示法是O(1)
- 刪除項目：Big-O表示法是O(1)
- 遍歷字典：Big-O表示法是O(n)
[[283391]]
NASA在Unsplash上拍攝的照片
文章標題：Python數(shù)據(jù)結(jié)構(gòu)的時間復雜性
標題URL：http://www.dlmjj.cn/article/dhgodgo.html
