訂閱
糾錯(cuò)
加入自媒體

數(shù)據(jù)結(jié)構(gòu)與算法的概念引入

2019-02-20 16:32
QYFabc
關(guān)注

數(shù)據(jù)結(jié)構(gòu)與算法是對(duì)于程序員來說是很重要的東西,可能很長(zhǎng)時(shí)間都用不到,可是用到的時(shí)候?qū)?huì)大大提高和優(yōu)化代碼的執(zhí)行效率。

引入

先來看一道題,已這道題為例:

如果 a+b+c=1000,且 a^2+b^2=c^2(a,b,c 為自然數(shù)),如何求出所有a、b、c可能的組合?

窮舉法、枚舉法

這種方法最麻煩,也是最容易想到的,但是耗時(shí)會(huì)很長(zhǎng)

import timestart_time = time.time()for a in range(0, 1001):

for b in range(0, 1001):

for c in range(0, 1001):

# 為了防止少寫等號(hào)導(dǎo)致代碼運(yùn)行失誤,將常量放在左邊

if 1000 == a + b + c and a**2 + b**2 == c**2:

print("a, b, c: {}, {}, {}".format(a, b, c))

end_time = time.time()print("用時(shí):{}".format(end_time - start_time))
輸出結(jié)果及耗時(shí)a, b, c: 0, 500, 500a, b, c: 200, 375, 425a, b, c: 375, 200, 425a, b, c: 500, 0, 500用時(shí):190.22626113891602Process finished with exit code 0優(yōu)化for a in range(0, 1001):

for b in range(0, 1001):

c = 1000 - a - b

if a**2 + b**2 == c**2:

print("a, b, c: {}, {}, {}".format(a, b, c))

end_time = time.time()print("用時(shí):{}".format(end_time - start_time))# 耗時(shí)a, b, c: 0, 500, 500a, b, c: 200, 375, 425a, b, c: 375, 200, 425a, b, c: 500, 0, 500用時(shí):1.1040208339691162Process finished with exit code 0算法的概念

算法是計(jì)算機(jī)處理信息的本質(zhì),因?yàn)橛?jì)算機(jī)程序本質(zhì)上是一個(gè)算法來告訴計(jì)算機(jī)確切的步驟來執(zhí)行一個(gè)指定的任務(wù)。一般地,當(dāng)算法在處理信息時(shí),會(huì)從輸入設(shè)備或數(shù)據(jù)的存儲(chǔ)地址讀取數(shù)據(jù),把結(jié)果寫入輸出設(shè)備或某個(gè)存儲(chǔ)地址供以后再調(diào)用。

算法是獨(dú)立存在的一種解決問題的方法和思想。

對(duì)于算法而言,實(shí)現(xiàn)的語言并不重要,重要的是思想。

算法可以有不同的語言描述實(shí)現(xiàn)版本(如C描述、C++描述、Python描述等),這里是在用Python語言進(jìn)行描述實(shí)現(xiàn)

算法的五大特性

輸入: 算法具有0個(gè)或多個(gè)輸入

輸出: 算法至少有1個(gè)或多個(gè)輸出

有窮性: 算法在有限的步驟之后會(huì)自動(dòng)結(jié)束而不會(huì)無限循環(huán),并且每一個(gè)步驟可以在可接受的時(shí)間內(nèi)完成

確定性:算法中的每一步都有確定的含義,不會(huì)出現(xiàn)二義性

可行性:算法的每一步都是可行的,也就是說每一步都能夠執(zhí)行有限的次數(shù)完成

算法效率衡量執(zhí)行時(shí)間反應(yīng)算法效率

對(duì)于同一問題,我們給出了兩種解決算法,在兩種算法的實(shí)現(xiàn)中,我們對(duì)程序執(zhí)行的時(shí)間進(jìn)行了測(cè)算,發(fā)現(xiàn)兩段程序執(zhí)行的時(shí)間相差懸殊(214.583347秒相比于0.182897秒),由此我們可以得出結(jié)論:實(shí)現(xiàn)算法程序的執(zhí)行時(shí)間可以反應(yīng)出算法的效率,即算法的優(yōu)劣。

單靠時(shí)間值絕對(duì)可信嗎?

假設(shè)我們將第二次嘗試的算法程序運(yùn)行在一臺(tái)配置古老性能低下的計(jì)算機(jī)中,情況會(huì)如何?很可能運(yùn)行的時(shí)間并不會(huì)比在我們的電腦中運(yùn)行算法一的214.583347秒快多少。

單純依靠運(yùn)行的時(shí)間來比較算法的優(yōu)劣并不一定是客觀準(zhǔn)確的!

程序的運(yùn)行離不開計(jì)算機(jī)環(huán)境(包括硬件和操作系統(tǒng)),這些客觀原因會(huì)影響程序運(yùn)行的速度并反應(yīng)在程序的執(zhí)行時(shí)間上。那么如何才能客觀的評(píng)判一個(gè)算法的優(yōu)劣呢?

時(shí)間復(fù)雜度與“大O記法”

我們假定計(jì)算機(jī)執(zhí)行算法每一個(gè)基本操作的時(shí)間是固定的一個(gè)時(shí)間單位,那么有多少個(gè)基本操作就代表會(huì)花費(fèi)多少時(shí)間單位。顯然對(duì)于不同的機(jī)器環(huán)境而言,確切的單位時(shí)間是不同的,但是對(duì)于算法進(jìn)行多少個(gè)基本操作(即花費(fèi)多少時(shí)間單位)在規(guī)模數(shù)量級(jí)上卻是相同的,由此可以忽略機(jī)器環(huán)境的影響而客觀的反應(yīng)算法的時(shí)間效率。

對(duì)于算法的時(shí)間效率,我們可以用“大O記法”來表示。

“大O記法”:對(duì)于單調(diào)的整數(shù)函數(shù)f,如果存在一個(gè)整數(shù)函數(shù)g和實(shí)常數(shù)c>0,使得對(duì)于充分大的n總有f(n)<=c*g(n),就說函數(shù)g是f的一個(gè)漸近函數(shù)(忽略常數(shù)),記為f(n)=O(g(n))。也就是說,在趨向無窮的極限意義下,函數(shù)f的增長(zhǎng)速度受到函數(shù)g的約束,亦即函數(shù)f與函數(shù)g的特征相似。

時(shí)間復(fù)雜度:假設(shè)存在函數(shù)g,使得算法A處理規(guī)模為n的問題示例所用時(shí)間為T(n)=O(g(n)),則稱O(g(n))為算法A的漸近時(shí)間復(fù)雜度,簡(jiǎn)稱時(shí)間復(fù)雜度,記為T(n)

如何理解“大O記法”

對(duì)于算法進(jìn)行特別具體的細(xì)致分析雖然很好,但在實(shí)踐中的實(shí)際價(jià)值有限。對(duì)于算法的時(shí)間性質(zhì)和空間性質(zhì),最重要的是其數(shù)量級(jí)和趨勢(shì),這些是分析算法效率的主要部分。而計(jì)量算法基本操作數(shù)量的規(guī)模函數(shù)中那些常量因子可以忽略不計(jì)。例如,可以認(rèn)為3n2和100n2屬于同一個(gè)量級(jí),如果兩個(gè)算法處理同樣規(guī)模實(shí)例的代價(jià)分別為這兩個(gè)函數(shù),就認(rèn)為它們的效率“差不多”,都為n2級(jí)。

最壞時(shí)間復(fù)雜度

分析算法時(shí),存在幾種可能的考慮:

算法完成工作最少需要多少基本操作,即最優(yōu)時(shí)間復(fù)雜度

算法完成工作最多需要多少基本操作,即最壞時(shí)間復(fù)雜度

算法完成工作平均需要多少基本操作,即平均時(shí)間復(fù)雜度

對(duì)于最優(yōu)時(shí)間復(fù)雜度,其價(jià)值不大,因?yàn)樗鼪]有提供什么有用信息,其反映的只是最樂觀最理想的情況,沒有參考價(jià)值。

對(duì)于最壞時(shí)間復(fù)雜度,提供了一種保證,表明算法在此種程度的基本操作中一定能完成工作。

對(duì)于平均時(shí)間復(fù)雜度,是對(duì)算法的一個(gè)全面評(píng)價(jià),因此它完整全面的反映了這個(gè)算法的性質(zhì)。但另一方面,這種衡量并沒有保證,不是每個(gè)計(jì)算都能在這個(gè)基本操作內(nèi)完成。而且,對(duì)于平均情況的計(jì)算,也會(huì)因?yàn)閼?yīng)用算法的實(shí)例分布可能并不均勻而難以計(jì)算。

因此,我們主要關(guān)注算法的最壞情況,亦即最壞時(shí)間復(fù)雜度。

時(shí)間復(fù)雜度的幾條基本計(jì)算規(guī)則基本操作,即只有常數(shù)項(xiàng),認(rèn)為其時(shí)間復(fù)雜度為O(1)

順序結(jié)構(gòu),時(shí)間復(fù)雜度按加法進(jìn)行計(jì)算

循環(huán)結(jié)構(gòu),時(shí)間復(fù)雜度按乘法進(jìn)行計(jì)算

分支結(jié)構(gòu),時(shí)間復(fù)雜度取最大值

判斷一個(gè)算法的效率時(shí),往往只需要關(guān)注操作數(shù)量的最高次項(xiàng),其它次要項(xiàng)和常數(shù)項(xiàng)可以忽略

在沒有特殊說明時(shí),我們所分析的算法的時(shí)間復(fù)雜度都是指最壞時(shí)間復(fù)雜度

空間復(fù)雜度

類似于時(shí)間復(fù)雜度的討論,一個(gè)算法的空間復(fù)雜度S(n)定義為該算法所耗費(fèi)的存儲(chǔ)空間,它也是問題規(guī)模n的函數(shù)。

漸近空間復(fù)雜度也常常簡(jiǎn)稱為空間復(fù)雜度。

空間復(fù)雜度(SpaceComplexity)是對(duì)一個(gè)算法在運(yùn)行過程中臨時(shí)占用存儲(chǔ)空間大小的量度。

算法的時(shí)間復(fù)雜度和空間復(fù)雜度合稱為算法的復(fù)雜度。

常見時(shí)間復(fù)雜度

| 執(zhí)行次數(shù)函數(shù)舉例 | 階       | 非正式術(shù)語 |

| ———————— | ———— | ————— |

| 12               | O(1)     | 常數(shù)階     |

| 2n+3             | O(n)     | 線性階     |

| 3n2+2n+1         | O(n2)    | 平方階     |

| 5log2n+20        | O(logn)  | 對(duì)數(shù)階     |

| 2n+3nlog2n+19    | O(nlogn) | nlogn階    |

| 6n3+2n2+3n+4     | O(n3)    | 立方階     |

| 2n               | O(2n)    | 指數(shù)階     |

注意,經(jīng)常將log2n(以2為底的對(duì)數(shù))簡(jiǎn)寫成logn

1  2  下一頁(yè)>  
聲明: 本文由入駐維科號(hào)的作者撰寫,觀點(diǎn)僅代表作者本人,不代表OFweek立場(chǎng)。如有侵權(quán)或其他問題,請(qǐng)聯(lián)系舉報(bào)。

發(fā)表評(píng)論

0條評(píng)論,0人參與

請(qǐng)輸入評(píng)論內(nèi)容...

請(qǐng)輸入評(píng)論/評(píng)論長(zhǎng)度6~500個(gè)字

您提交的評(píng)論過于頻繁,請(qǐng)輸入驗(yàn)證碼繼續(xù)

  • 看不清,點(diǎn)擊換一張  刷新

暫無評(píng)論

暫無評(píng)論

    掃碼關(guān)注公眾號(hào)
    OFweek人工智能網(wǎng)
    獲取更多精彩內(nèi)容
    文章糾錯(cuò)
    x
    *文字標(biāo)題:
    *糾錯(cuò)內(nèi)容:
    聯(lián)系郵箱:
    *驗(yàn) 證 碼:

    粵公網(wǎng)安備 44030502002758號(hào)