-
算法引入：
如果a+b+c=1000，且a2+b2=c^2（a,b,c為自然數(shù)）去件，如何求出所有a，b扰路，c可能的組合尤溜？
解決：枚舉法 思路：a=0，b=0汗唱，c=1/2/3....
import time start_time = time.time() for a in range(0,1001): for b in range(0,1001): for c in range(0,1001): if a + b + c == 1000 and a**2 + b**2 == c**2: print("a,b,c:%d,%d,%d"%(a,b,c)) end_time = time.time() print("times:%ds"%(end_time-start_time)) print("finished") 輸出： a,b,c:0,500,500 a,b,c:200,375,425 a,b,c:375,200,425 a,b,c:500,0,500 times:261s finished 算法是獨(dú)立存在的一種解決問題的方法與思想宫莱，對(duì)于算法而言，實(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ù)完成
二、復(fù)雜度分析
1框弛、算法效率衡量
-
上述例子算法改進(jìn)：
import time start_time = time.time() for a in range(0,1001): for b in range(0,1001): c = 1000 - a - b #給出了a,b后,c的值就已經(jīng)是確定下來的了 if a**2 + b**2 == c**2: print("a,b,c:%d,%d,%d"%(a,b,c)) end_time = time.time() print("times:%ds"%(end_time-start_time)) print("finished") 輸出： a,b,c:0,500,500 a,b,c:200,375,425 a,b,c:375,200,425 a,b,c:500,0,500 times:2s finished
-
執(zhí)行時(shí)間反應(yīng)算法效率
由上述的兩段程序的執(zhí)行時(shí)間（261秒與2秒）辛辨，可以得出結(jié)論：實(shí)現(xiàn)算法程序的執(zhí)行時(shí)間可以反應(yīng)出算法的效率，即算法的優(yōu)劣。
-
單靠時(shí)間值是不絕對(duì)可信的斗搞！
假設(shè)第二次的算法實(shí)在一臺(tái)性能很差的計(jì)算機(jī)中運(yùn)行指攒，運(yùn)行時(shí)間可能與第一次運(yùn)行時(shí)間差不了多少，故：單純依靠運(yùn)行時(shí)間來比較算法的優(yōu)劣并不一定是客觀準(zhǔn)確的僻焚！程序的運(yùn)行離不開計(jì)算機(jī)環(huán)境（包括硬件和操作系統(tǒng)）允悦，客觀原因影響程序運(yùn)行的速度，即每臺(tái)機(jī)器執(zhí)行的總時(shí)間不同虑啤，但是執(zhí)行的基本運(yùn)算數(shù)量大體相同隙弛，故下述引入時(shí)間復(fù)雜度概念。
2狞山、時(shí)間復(fù)雜度
（1）什么是大O驶鹉？
-
n表示數(shù)據(jù)規(guī)模，O(f(n))表示算法所需要執(zhí)行的指令數(shù)铣墨，和f(n)成正比。其中f(n)是n的一個(gè)函數(shù)办绝。
在業(yè)界伊约，O(f(n))表示算法執(zhí)行的最低上界。（更詳細(xì)概念請(qǐng)百度）記T為執(zhí)行指令數(shù)
上述第一個(gè)python代碼：T = 1000 * 1000 * 1000 * 2 (三個(gè)循環(huán)孕蝉，一條if語句屡律，一條print語句)
若題目變?yōu)閍+b+c = 2000，則T = 2000 * 2000 * 2000 * 2
改為a+b+c = n ,則T=n * n * n * 2
總結(jié)：對(duì)于一個(gè)算法來說降淮，T與數(shù)據(jù)規(guī)模n有關(guān)超埋，即T(n)= n^3*2，當(dāng)n較大時(shí)佳鳖，T(n)= n^3霍殴，常數(shù)不計(jì)。
算法 所需執(zhí)行指令數(shù) 二分查找法O(logn) a*logn 尋找數(shù)組中的最大/最小值O(n) b*n 歸并排序算法O(nlogn) c*nlogn 選擇排序法O(n^2) d*n^2 對(duì)于算法的時(shí)間性質(zhì)與空間性質(zhì)系吩，最重要的是其數(shù)量級(jí)和趨勢来庭，這些是分析算法效率的主要部分，而計(jì)量算法基本操作數(shù)量的規(guī)模函數(shù)中那些常量因子可以忽略不計(jì)穿挨。如上：a,b,c,d均為常數(shù) 月弛，當(dāng)數(shù)據(jù)規(guī)模較大時(shí)，算法消耗的時(shí)間復(fù)雜度與這些常數(shù)關(guān)系不大科盛，而是與n所在項(xiàng)相關(guān)帽衙，故此時(shí)一般省略常數(shù)！
例如：
算法A：O(n) 所需執(zhí)行指令數(shù)：10000*n
算法B：O(n^2) 所需執(zhí)行指令數(shù)：10*n^2
對(duì)比不同n規(guī)模時(shí)算法A贞绵，B的指令數(shù)情況：
n A的指令數(shù)10000n B的指令數(shù)10n^2 倍數(shù) 10 10^5 10^3 100 100 10^6 10^5 10 1000 10^7 10^7 1 10000 10^8 10^9 0.1 10^5 10^9 10^11 0.01 10^6 10^10 10^13 0.001 可見厉萝，時(shí)間復(fù)雜度大O衡量的是量級(jí)的差異。當(dāng)n達(dá)到某個(gè)值時(shí)，時(shí)間復(fù)雜度低的算法一定比時(shí)間復(fù)雜度高的算法運(yùn)算時(shí)間快冀泻，n越大常侣，差距越明顯。（數(shù)據(jù)規(guī)模較小時(shí)弹渔，時(shí)間復(fù)雜度高的算法有常數(shù)上的優(yōu)勢胳施，還是可以使用的，一般情況下肢专，使用復(fù)雜度較低的算法更優(yōu)）
-
若設(shè)計(jì)的算法有兩部分舞肆，則整個(gè)算法以量級(jí)最高的作為主導(dǎo)的時(shí)間復(fù)雜度。如：
O(nlogn+n)= O(nlogn)
O(nlogn+n^2)$= $O(n^2)
注：上面式子的前提是 ：這兩部分對(duì)應(yīng)的規(guī)模n是一樣的博杖，而像O(AlogA+B)這種類型的椿胯，此處A和B的規(guī)模可能不一樣剃根，故不能省略掉AlogA這部分（對(duì)鄰接表實(shí)現(xiàn)的圖進(jìn)行遍歷哩盲，時(shí)間復(fù)雜度是O(V+E)，V是頂點(diǎn)數(shù)狈醉，E是邊數(shù)廉油，不能隨便替換）
（2）最壞時(shí)間復(fù)雜度
-
分析算法時(shí)，存在幾種可能的考慮：
算法完成工作最少需要多少基本步驟苗傅，即最優(yōu)時(shí)間復(fù)雜度
算法完成工作最多需要多少基本步驟抒线，即最壞時(shí)間復(fù)雜度
算法完成工作平均需要多少基本步驟，即平均時(shí)間復(fù)雜度
對(duì)于最優(yōu)時(shí)間復(fù)雜度渣慕，其參考價(jià)值不大嘶炭，反映的是最樂觀最理想的情況；對(duì)于最壞時(shí)間復(fù)雜度逊桦，提供了一種保證眨猎，表明算法在此種程度的基本操作中一定能完成工作；對(duì)于平均時(shí)間復(fù)雜度卫袒，全面反映算法的性質(zhì)宵呛，但其也會(huì)因?yàn)閼?yīng)用算法的實(shí)例分布不均勻而難以計(jì)算；因此夕凝，我們主要關(guān)注算法的最壞情況宝穗，即最壞時(shí)間復(fù)雜度
-
算法復(fù)雜度在有些情況是用例相關(guān)（即與待排數(shù)據(jù)分布情況有關(guān)）的，比如：
插入排序算法O(n^2)：最差情況：O(n^2)码秉；最好情況：O(n) 逮矛；平均情況（業(yè)界）：O(n^2)
快速排序算法O(nlogn)：最差情況：O(n^2) (隨機(jī)化情況下，退化成最差情況的概率比較低)转砖；最好情況：O(nlogn)须鼎；平均情況（業(yè)界）：O(nlogn)
（3）時(shí)間復(fù)雜度計(jì)算
-
時(shí)間復(fù)雜度的幾條計(jì)算規(guī)則
- 基本操作鲸伴，即只有常數(shù)項(xiàng)，認(rèn)為其時(shí)間復(fù)雜度為O(1)
- 順序結(jié)構(gòu)晋控，時(shí)間復(fù)雜度按加法計(jì)算
- 循環(huán)結(jié)構(gòu)汞窗，時(shí)間復(fù)雜度按乘法計(jì)算
- 分支結(jié)構(gòu)，時(shí)間復(fù)雜度取最大值
- 判斷一個(gè)算法的效率時(shí)赡译，往往只需關(guān)注操作數(shù)量的最高次項(xiàng)仲吏，其他次要項(xiàng)和常數(shù)項(xiàng)可以忽略
- 在沒有特殊說明時(shí)，我們所分析的算法的時(shí)間復(fù)雜度都是指最壞時(shí)間復(fù)雜度
常見時(shí)間復(fù)雜度消耗時(shí)間大序蚍佟：
O(1) < O(logn) < O(n) < O(nlogn) < O(n^2) < O(n^3) < O(n!) < O(2^n)-
問題：有一個(gè)字符串?dāng)?shù)組裹唆，將數(shù)組中每一個(gè)字符串按照字母序排序；之后再將整個(gè)字符串?dāng)?shù)組按照字典序排序只洒。整個(gè)操作的時(shí)間復(fù)雜度许帐？
錯(cuò)誤解答：把字符串?dāng)?shù)組長度與每一個(gè)字符串的長度都統(tǒng)一當(dāng)成了n O(n*nlogn+nlogn)=O(n^2log2n) 正確解答： --假設(shè)最長的字符串長度為s（因?yàn)榇驩算的是上界）；數(shù)組中有n個(gè)字符串 --對(duì)每個(gè)字符串排序：O(slogs) --將數(shù)組中的每一個(gè)字符串按照字母序排序：O(n*slogs) --將整個(gè)字符串?dāng)?shù)組按照字典序排序：O(s*nlog(n)) （排序算法中nlogn表示的是比較的次數(shù)毕谴，通常說的對(duì)整型數(shù)組排序只需進(jìn)行nlogn次比較成畦，是因?yàn)閮蓚€(gè)整數(shù)進(jìn)行比較在計(jì)算機(jī)中是O(1)級(jí)別的，而此處字符串比較字典序涝开，還需耗費(fèi)O(s) --綜上：O(n*slogs)+O(s*nlog(n))=O(n*slogs+s*nlog(n))=O(n*s*(logs+logn))
