Python算法中時(shí)間復(fù)雜度問題的示例分析-創(chuàng)新互聯(lián)

這篇文章主要介紹了Python算法中時(shí)間復(fù)雜度問題的示例分析，具有一定借鑒價(jià)值，感興趣的朋友可以參考下，希望大家閱讀完這篇文章之后大有收獲，下面讓小編帶著大家一起了解一下。

創(chuàng)新互聯(lián)是一家集成都做網(wǎng)站、成都網(wǎng)站制作、網(wǎng)站頁面設(shè)計(jì)、網(wǎng)站優(yōu)化SEO優(yōu)化為一體的專業(yè)網(wǎng)站制作公司，已為成都等多地近百家企業(yè)提供網(wǎng)站建設(shè)服務(wù)。追求良好的瀏覽體驗(yàn),以探求精品塑造與理念升華,設(shè)計(jì)最適合用戶的網(wǎng)站頁面。 合作只是第一步，服務(wù)才是根本,我們始終堅(jiān)持講誠(chéng)信，負(fù)責(zé)任的原則，為您進(jìn)行細(xì)心、貼心、認(rèn)真的服務(wù),與眾多客戶在蓬勃發(fā)展的市場(chǎng)環(huán)境中,互促共生。

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

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

漸進(jìn)時(shí)間復(fù)雜度

時(shí)間復(fù)雜度是算法運(yùn)算所消耗的時(shí)間，因?yàn)椴煌笮〉妮斎霐?shù)據(jù)，算法處理所要消耗的時(shí)間是不同的，因此評(píng)估一個(gè)算運(yùn)行時(shí)間是比較困難的，所以通常關(guān)注的是時(shí)間頻度，即算法運(yùn)行計(jì)算操作的次數(shù)，記為T(n)，其中n稱為問題的規(guī)模。

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

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

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

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

因?yàn)槲覀冇?jì)算的是極限狀態(tài)下(如，n非常大)的時(shí)間復(fù)雜度，因此其中存在以下兩種特性：

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

根據(jù)上述兩種特性，時(shí)間復(fù)雜度的計(jì)算方法：

1.只取最高階項(xiàng)，去掉低階項(xiàng)。

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

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

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

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

時(shí)間復(fù)雜度：線性階 O(n)

時(shí)間復(fù)雜度：線性階 O(n)

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

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

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

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

時(shí)間復(fù)雜度：對(duì)數(shù)階 O(logn)

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

練習(xí)一下

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

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

感謝你能夠認(rèn)真閱讀完這篇文章，希望小編分享的“Python算法中時(shí)間復(fù)雜度問題的示例分析”這篇文章對(duì)大家有幫助，同時(shí)也希望大家多多支持創(chuàng)新互聯(lián)，關(guān)注創(chuàng)新互聯(lián)行業(yè)資訊頻道，更多相關(guān)知識(shí)等著你來學(xué)習(xí)!

網(wǎng)頁題目：Python算法中時(shí)間復(fù)雜度問題的示例分析-創(chuàng)新互聯(lián)
文章URL：http://muchs.cn/article20/dpoico.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供品牌網(wǎng)站建設(shè)、商城網(wǎng)站、App設(shè)計(jì)、建站公司、手機(jī)網(wǎng)站建設(shè)、移動(dòng)網(wǎng)站建設(shè)

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請(qǐng)盡快告知，我們將會(huì)在第一時(shí)間刪除。文章觀點(diǎn)不代表本網(wǎng)站立場(chǎng)，如需處理請(qǐng)聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時(shí)需注明來源： 創(chuàng)新互聯(lián)