欧美bbbwbbbw肥妇,免费乱码人妻系列日韩,一级黄片

Python算法中的時間復(fù)雜度問題

 更新時間:2019年11月19日 09:24:14   作者:軟件測試開發(fā)技術(shù)棧  
時間復(fù)雜度用于度量算法的計算工作量,空間復(fù)雜度用于度量算法占用的內(nèi)存空間。這篇文章主要介紹了Python算法中的時間復(fù)雜度,需要的朋友可以參考下

在實現(xiàn)算法的時候,通常會從兩方面考慮算法的復(fù)雜度,即時間復(fù)雜度和空間復(fù)雜度。顧名思義,時間復(fù)雜度用于度量算法的計算工作量,空間復(fù)雜度用于度量算法占用的內(nèi)存空間。

本文將從時間復(fù)雜度的概念出發(fā),結(jié)合實際代碼示例分析算法的時間復(fù)雜度。

漸進時間復(fù)雜度

時間復(fù)雜度是算法運算所消耗的時間,因為不同大小的輸入數(shù)據(jù),算法處理所要消耗的時間是不同的,因此評估一個算運行時間是比較困難的,所以通常關(guān)注的是時間頻度,即算法運行計算操作的次數(shù),記為T(n),其中n稱為問題的規(guī)模。

同樣,因為n是一個變量,n發(fā)生變化時,時間頻度T(n) 也在發(fā)生變化,我們稱時間復(fù)雜度的極限情形稱為算法的漸近時間復(fù)雜度,記為O(n),不包含函數(shù)的低階和首項系數(shù)。

我們以如下 例子來解釋一下:

如上例子中,我們根據(jù)代碼上執(zhí)行的平均時間假設(shè),計算 run_time(n) 函數(shù)的時間復(fù)雜度,如下:

上述時間復(fù)雜度計算公式T(n) ,是我們對函數(shù) run_time(n) 進行的時間復(fù)雜度的估算。當(dāng)n 值非常大的時候,T(n)函數(shù)中常數(shù)項 time0 以及n的系數(shù) (time1+time2+time3+time4) 對n的影響也可以忽略不計了,因此這里函數(shù)run_time(n) 的時間復(fù)雜度我們可以表示為 O(n)。

因為我們計算的是極限狀態(tài)下(如,n非常大)的時間復(fù)雜度,因此其中存在以下兩種特性:

低階項相對于高階項產(chǎn)生的影響很小,可以忽略不計。 最高項系數(shù)對最高項的影響也很小,可以忽略不計。

根據(jù)上述兩種特性,時間復(fù)雜度的計算方法:

1.只取最高階項,去掉低階項。

2.去掉最高項的系數(shù)。

3.針對常數(shù)階,取時間復(fù)雜度為O(1)。

我們通過下面例子理解一下常見的時間復(fù)雜度,如下:

時間復(fù)雜度:常數(shù)階 O(1)

時間復(fù)雜度:線性階 O(n)

時間復(fù)雜度:線性階 O(n)

時間復(fù)雜度:平方階 O(n^2)

時間復(fù)雜度:平方階 O(n^2)

時間復(fù)雜度:平方階 O(n^2)

時間復(fù)雜度:立方階 O(n^3)

時間復(fù)雜度:對數(shù)階 O(logn)

隨著問題規(guī)模n的不斷增大,上述時間復(fù)雜度不斷增大,算法的執(zhí)行效率越低,時間復(fù)雜度排序如下:

練習(xí)一下

如下count_sort 函數(shù)實現(xiàn)了計數(shù)排序,列表中的數(shù)范圍都在0到100之間,列表長度大約為100萬。

如上count_sort 函數(shù)的 空間復(fù)雜度為 O(n),公式如下:

總結(jié)

以上所述是小編給大家介紹的Python算法中的時間復(fù)雜度問題,希望對大家有所幫助,如果大家有任何疑問請給我留言,小編會及時回復(fù)大家的。在此也非常感謝大家對腳本之家網(wǎng)站的支持!
如果你覺得本文對你有幫助,歡迎轉(zhuǎn)載,煩請注明出處,謝謝!

相關(guān)文章

  • Python爬蟲通過替換http request header來欺騙瀏覽器實現(xiàn)登錄功能

    Python爬蟲通過替換http request header來欺騙瀏覽器實現(xiàn)登錄功能

    這篇文章主要介紹了Python爬蟲通過替換http request header來欺騙瀏覽器實現(xiàn)登錄功能,需要的朋友可以參考下
    2018-01-01
  • 對Matlab中共軛、轉(zhuǎn)置和共軛裝置的區(qū)別說明

    對Matlab中共軛、轉(zhuǎn)置和共軛裝置的區(qū)別說明

    這篇文章主要介紹了對Matlab中共軛、轉(zhuǎn)置和共軛裝置的區(qū)別說明,具有很好的參考價值,希望對大家有所幫助。一起跟隨小編過來看看吧
    2020-05-05
  • 如何運行Python程序的方法

    如何運行Python程序的方法

    以下均基于windows下操作,并且安裝的是最新的python3.3版本。
    2013-04-04
  • Python使用smtp和pop簡單收發(fā)郵件完整實例

    Python使用smtp和pop簡單收發(fā)郵件完整實例

    這篇文章主要介紹了Python使用smtp和pop簡單收發(fā)郵件完整實例,簡單介紹了smtp和pop,然后分享了相關(guān)實例代碼,具有一定借鑒價值,需要的朋友可以參考下
    2018-01-01
  • python的time模塊和datetime模塊實例解析

    python的time模塊和datetime模塊實例解析

    這篇文章主要介紹了python的time模塊和datetime模塊實例解析,文中通過示例代碼介紹的非常詳細,對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價值,需要的朋友可以參考下
    2019-11-11
  • Python實現(xiàn)softmax反向傳播的示例代碼

    Python實現(xiàn)softmax反向傳播的示例代碼

    這篇文章主要為大家詳細介紹了Python實現(xiàn)softmax反向傳播的相關(guān)資料,文中的示例代碼講解詳細,具有一定的參考價值,感興趣的可以了解一下
    2023-04-04
  • Django的Modelforms用法簡介

    Django的Modelforms用法簡介

    這篇文章主要介紹了Django的Modelforms用法簡介,文中通過示例代碼介紹的非常詳細,對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價值,需要的朋友可以參考下
    2019-07-07
  • Python在圖片中添加文字的兩種方法

    Python在圖片中添加文字的兩種方法

    這篇文章主要給大家介紹了在Python在圖片中添加文字的兩種方法,分別是使用OpenCV和PIL這兩個方法實現(xiàn),在實際應(yīng)用中要在這兩種方法中擇優(yōu)使用。兩種方法都給出了詳細示例代碼,需要的朋友可以參考下。
    2017-04-04
  • Python中的支持向量機SVM的使用(附實例代碼)

    Python中的支持向量機SVM的使用(附實例代碼)

    這篇文章主要介紹了Python中的支持向量機SVM的使用(附實例代碼),文中通過示例代碼介紹的非常詳細,對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價值,需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧
    2019-06-06
  • Keras實現(xiàn)DenseNet結(jié)構(gòu)操作

    Keras實現(xiàn)DenseNet結(jié)構(gòu)操作

    這篇文章主要介紹了Keras實現(xiàn)DenseNet結(jié)構(gòu)操作,具有很好的參考價值,希望對大家有所幫助。一起跟隨小編過來看看吧
    2020-07-07

最新評論