算法是計(jì)算機(jī)處理信息的本質(zhì)捉貌，因?yàn)橛?jì)算機(jī)程序本質(zhì)上是一個(gè)算法來(lái)告訴計(jì)算機(jī)確切的步驟來(lái)執(zhí)行一個(gè)指定的任務(wù)。算法是獨(dú)立存在的一種解決問(wèn)題的方法和思想冬念，對(duì)于算法而言趁窃，實(shí)現(xiàn)的語(yǔ)言并不重要，重要的是思想急前。

算法的五大特性：

1醒陆、輸入:?算法具有0個(gè)或多個(gè)輸入

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

3裆针、有窮性:?算法在有限步驟之后會(huì)自動(dòng)結(jié)束而不會(huì)無(wú)限循環(huán)刨摩，且每一個(gè)步驟要在可接受的時(shí)間內(nèi)完成

4、確定性：算法中的每一步都有確定的含義世吨，不會(huì)出現(xiàn)二義性（比如數(shù)值的相加和字符串的拼接）

5澡刹、可行性：算法的每一步都是可行的，也就是說(shuō)每一步都能夠執(zhí)行有限的次數(shù)完成

實(shí)現(xiàn)算法程序的執(zhí)行時(shí)間可以反應(yīng)出算法的效率耘婚，即算法的優(yōu)劣罢浇，但是單純依靠運(yùn)行的時(shí)間來(lái)比較算法的優(yōu)劣并不一定是客觀準(zhǔn)確的！程序的運(yùn)行離不開(kāi)計(jì)算機(jī)環(huán)境（包括硬件和操作系統(tǒng)）沐祷，這些客觀原因會(huì)影響程序運(yùn)行的速度并反應(yīng)在程序的執(zhí)行時(shí)間上嚷闭。

我們假定計(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)境的影響，從客觀的角度看待算法的時(shí)間效率，對(duì)于算法的時(shí)間效率色乾，我們可以用“大O記法”來(lái)表示誊册。

“大O記法”：

對(duì)于單調(diào)的整數(shù)函數(shù)f，如果存在一個(gè)整數(shù)函數(shù)g和實(shí)常數(shù)c>0暖璧，使得對(duì)于充分大的n總有f(n)<=c*g(n)案怯，就說(shuō)函數(shù)g是f的一個(gè)漸近函數(shù)（忽略常數(shù)），記為f(n)=O(g(n))澎办。也就是說(shuō)嘲碱，在趨向無(wú)窮的極限意義下，函數(shù)f的增長(zhǎng)速度受到函數(shù)g的約束局蚀，亦即函數(shù)f與函數(shù)g的特征相似麦锯。

時(shí)間復(fù)雜度：

假設(shè)存在函數(shù)g，使得算法A處理規(guī)模為n的問(wèn)題所用時(shí)間為T(mén)(n)=O(g(n))琅绅，則稱(chēng)O(g(n))為算法A的漸近時(shí)間復(fù)雜度扶欣，簡(jiǎn)稱(chēng)時(shí)間復(fù)雜度，記為T(mén)(n)

如何理解“大O記法”

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

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

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

1巷帝、·算法完成工作最少需要多少基本操作忌卤，即最優(yōu)時(shí)間復(fù)雜度

2、·算法完成工作最多需要多少基本操作楞泼，即最壞時(shí)間復(fù)雜度

3驰徊、·算法完成工作平均需要多少基本操作，即平均時(shí)間復(fù)雜度

我們主要關(guān)注算法的最壞情況堕阔，亦即最壞時(shí)間復(fù)雜度棍厂。

時(shí)間復(fù)雜度的幾條基本計(jì)算規(guī)則：

1.、基本操作超陆，即只有常數(shù)項(xiàng)牺弹，認(rèn)為其時(shí)間復(fù)雜度為O(1)

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

3.张漂、循環(huán)結(jié)構(gòu)晶默，時(shí)間復(fù)雜度按乘法進(jìn)行計(jì)算

4.、分支結(jié)構(gòu)航攒，時(shí)間復(fù)雜度取最大值

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

6.币他、在沒(méi)有特殊說(shuō)明時(shí)，我們所分析的算法的時(shí)間復(fù)雜度都是指最壞時(shí)間復(fù)雜度

常見(jiàn)時(shí)間復(fù)雜度：

常見(jiàn)時(shí)間復(fù)雜度之間的關(guān)系：

所消耗的時(shí)間從小到大：

O(1)?<?O(logn)?<?O(n)?<?O(nlogn)?<?O(n2)?<?O(n3)?<?O(2n)?<?O(n!)?<?O(nn)

測(cè)試程序的運(yùn)行時(shí)間：timeit模塊

下面以5種方式創(chuàng)建列表憔狞，對(duì)比其運(yùn)行時(shí)間：