目標
算法分析重要性
學(xué)會使用算法分析工具大O記號來描述時間復(fù)雜度
理解常用數(shù)據(jù)結(jié)構(gòu)的時間復(fù)雜度
理解數(shù)據(jù)如何影響算法分析
如何對程序做基準測試 benchmark
什么是算法分析
考慮解決同一個問題采用不同的代碼解決所需要的計算機資源,或者考慮其執(zhí)行所需要花費的時間衬横。
很多情況下赃额,我們考慮時間彪标。
在程序中簿姨,可以
import time
start = time.time()
CODE BLOCK
end = time.time()
runtime= end - start
不同的計算機堕扶,語言等都會帶來時間的差異爱沟。因此徊件,這個time并不能真正度量奸攻。
我們通過一種大O記號來避開這些影響。
大O記號
我們以程序執(zhí)行的步數(shù)為基準庇忌,來計算時間舞箍。
亂序字符串
一個字符串是另一個字符串的重新排列。如
heart 和raeth皆疹。asdfg和gfdas.
如何判斷兩個字符串是否為亂序字符串?
- 排序法:兩字符串分別排序后是否相等疏橄,其時間復(fù)雜度需要考慮排序算法的時間復(fù)雜度。
- 窮舉法
- 字符計數(shù)