數(shù)據(jù)結(jié)構(gòu)與算法的概念引入
數(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

發(fā)表評(píng)論
請(qǐng)輸入評(píng)論內(nèi)容...
請(qǐng)輸入評(píng)論/評(píng)論長(zhǎng)度6~500個(gè)字
最新活動(dòng)更多
-
3月27日立即報(bào)名>> 【工程師系列】汽車電子技術(shù)在線大會(huì)
-
4月30日立即下載>> 【村田汽車】汽車E/E架構(gòu)革新中,新智能座艙挑戰(zhàn)的解決方案
-
5月15-17日立即預(yù)約>> 【線下巡回】2025年STM32峰會(huì)
-
即日-5.15立即報(bào)名>>> 【在線會(huì)議】安森美Hyperlux™ ID系列引領(lǐng)iToF技術(shù)革新
-
5月15日立即下載>> 【白皮書】精確和高效地表征3000V/20A功率器件應(yīng)用指南
-
5月16日立即參評(píng) >> 【評(píng)選啟動(dòng)】維科杯·OFweek 2025(第十屆)人工智能行業(yè)年度評(píng)選
推薦專題
- 1 UALink規(guī)范發(fā)布:挑戰(zhàn)英偉達(dá)AI統(tǒng)治的開始
- 2 北電數(shù)智主辦酒仙橋論壇,探索AI產(chǎn)業(yè)發(fā)展新路徑
- 3 降薪、加班、裁員三重暴擊,“AI四小龍”已折戟兩家
- 4 “AI寒武紀(jì)”爆發(fā)至今,五類新物種登上歷史舞臺(tái)
- 5 國(guó)產(chǎn)智駕迎戰(zhàn)特斯拉FSD,AI含量差幾何?
- 6 光計(jì)算迎來商業(yè)化突破,但落地仍需時(shí)間
- 7 東陽光:2024年扭虧、一季度凈利大增,液冷疊加具身智能打開成長(zhǎng)空間
- 8 地平線自動(dòng)駕駛方案解讀
- 9 封殺AI“照騙”,“淘寶們”終于不忍了?
- 10 優(yōu)必選:營(yíng)收大增主靠小件,虧損繼續(xù)又逢關(guān)稅,能否乘機(jī)器人東風(fēng)翻身?