算法是什么？
舉個(gè)簡(jiǎn)單例子：
我們要做一份蛋炒飯：
- 拿錢包，出門，去菜市場(chǎng)購(gòu)買雞蛋和大米以及油和鹽——購(gòu)買蛋炒飯的材料
- 回家將大米淘洗干凈放進(jìn)電飯煲——煮熟大米
- 將鍋放在電磁爐上加熱——往鍋里倒適量油
- 將雞蛋打開放入油鍋——翻炒雞蛋至七分熟
- 將適量煮熟的米飯倒入鍋中，加鹽——翻炒兩分鐘
以上就是制作一份簡(jiǎn)單蛋炒飯的步驟
如果把這些交給機(jī)器來做，也是如此，并且步驟將更加細(xì)分和嚴(yán)謹(jǐn)
簡(jiǎn)單來講，這就是算法
那么算法到底是什么呢？
先來看一道簡(jiǎn)單的高中數(shù)學(xué)題：
現(xiàn)有a,b,c三個(gè)自然數(shù)，要求滿足以下條件：
1.a+b+c = 1000
2.a^2 + b^2 = c^2 (^代表平方)
分析：
首先排除數(shù)學(xué)公式，我們使用機(jī)器思維來計(jì)算這道題，能想到的辦法也很簡(jiǎn)單，即一個(gè)一個(gè)數(shù)嘗試
，直到試出準(zhǔn)確答案為止，此種方法我們稱之為 枚舉法
上面數(shù)學(xué)題使用Python來實(shí)現(xiàn)：
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("time:%d" % (end_time - start_time))
print("finished!")
代碼執(zhí)行結(jié)果：
C:\python3\setup\python.exe C:/Users/limia/Desktop/DataS/01_枚舉組合.py
a, b, c: 0, 500,500
a, b, c: 200, 375,425
a, b, c: 375, 200,425
a, b, c: 500, 0,500
time:121
finished!
Process finished with exit code 0
注釋： 在上面的代碼中：計(jì)算這道數(shù)學(xué)題的同時(shí)，還引入了time模塊來計(jì)算這段代碼的運(yùn)行時(shí)間，以方便之后對(duì)比算法效率
通過分析這道題，我們可以得知，a+b+c=1000，在有了a和b的值之后，c的值自然就可以計(jì)算為：1000-a-b，分析至此，則代碼可以改進(jìn)為以下：
import time
start_time = time.time()
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: %d, %d,%d" % (a, b, c))
end_time = time.time()
print("time:%d" % (end_time - start_time))
print("finished!")
代碼執(zhí)行結(jié)果：
C:\python3\setup\python.exe C:/Users/limia/Desktop/DataS/01_枚舉組合.py
a, b, c: 0, 500,500
a, b, c: 200, 375,425
a, b, c: 375, 200,425
a, b, c: 500, 0,500
time:1
finished!
Process finished with exit code 0
通過對(duì)比，可以一目了然的發(fā)現(xiàn)，改進(jìn)后的代碼執(zhí)行效率（1s）明顯高于第一種代碼執(zhí)行效率（121s）
算法的概念：
算法是計(jì)算機(jī)處理信息的本質(zhì)
算法是獨(dú)立存在的一種解決問題的方法和思想
計(jì)算機(jī)程序本質(zhì)上是一個(gè)算法來告訴計(jì)算機(jī)確切的步驟來執(zhí)行一個(gè)指定的任務(wù)
單純以時(shí)間衡量算法效率是否是科學(xué)的、客觀的？
答案：不客觀
假設(shè)在一臺(tái)古老的計(jì)算機(jī)上運(yùn)行上面的兩個(gè)程序，則其所消耗的時(shí)間都將是極長(zhǎng)的，因此單純以時(shí)間計(jì)算算法的效率是不科學(xué)的。
在衡量算法的效率時(shí)，應(yīng)當(dāng)脫離計(jì)算機(jī)來估算
因此引入時(shí)間復(fù)雜度來衡量算法的效率
每臺(tái)計(jì)算機(jī)執(zhí)行的總時(shí)間不同，但是執(zhí)行基本運(yùn)算數(shù)量大體相同
上面的兩個(gè)程序，以時(shí)間復(fù)雜度來表示算法效率：
T = 1000 * 1000 * 1000 * 2
==》 當(dāng)計(jì)算的不是a+b+c=1000，而是a+b+c=2000時(shí)，以時(shí)間復(fù)雜度表示則
T = 2000 * 2000 * 2000 * 2
==》 當(dāng)計(jì)算的不是1000或者2000,而是n呢？
T(n) = n * n * n * 2
簡(jiǎn)化：
T(n) = n^3 * 2
則此時(shí) **T(n) = n^3 * 2 ** 即為這個(gè)程序算法的時(shí)間復(fù)雜度函數(shù)
通過函數(shù) T(n) = n^3 * 2 ,可做出曲線圖
系數(shù)對(duì)曲線形狀改變不大，只是陡峭不同，因此 T(n) = n^3 * 2 可以簡(jiǎn)化為T(n) = n^3
T(n) = n^3 則可以叫做 T(n) = n^3 * 2 的漸進(jìn)函數(shù)
大O表示法
上述 **T(n) = n^3 ** 就是 ** T(n) = n^3 * 2 ** 的大O 表示法
總結(jié)： 大O表示法只留下表示特征的部分
常見時(shí)間復(fù)雜度之間的關(guān)系
O(1) < O(logn) < O(n) < O(nlogn) < O(n^2) < O(n^3) < O(2^n) < O(n!) < O(n^n)
個(gè)人博客地址：www.limiao.tech
微信公眾號(hào)：TechBoard
慕課網(wǎng)：techLee
如果覺得文章對(duì)您有所幫助，那就伸出小手 ==>> 點(diǎn)擊下方 [ like ] 吧
