演算法的時間與空間復雜度
事后分析法
缺點：不同的資料規模，不同的機器下演算法運行的時間不同，無法做到計算運行時間
事前分析法
大O時間復雜度
漸進時間復雜度 隨著n的增長，程式運行時間跟隨n變化的趨勢
幾個原則
去掉常數項
2(n^2) =n^2
一段代碼取時間復雜度最高的
test(n) {
//時間復雜度n^3
for(int i = 0; i < n ; i++){
for(int i = 0; i < n ; i++){
for(int i = 0; i < n ; i++){
print(n);
}
}
}
//時間復雜度n^2
for(int i = 0; i < n ; i++){
for(int i = 0; i < n ; i++){
print(n);
}
}
//時間復雜度n
for(int i = 0; i < n ; i++){
print(n);
}
}
這段代碼的時間復雜度為n3+n2+n
當n足夠大時，n2和n與n3相比太小，可以忽略不計
常見復雜度
o(1)
i = i + 1;
o(n)
test(n){
for(int i = 0 ;i < n;i++){
print(i);
}
}
o(n^2)
test(n){
for(int i = 0 ;i < n;i++){
print(i);
for(int j = 0 ;j < n;j++){
print(i);
}
}
}
o(log2n)
PS:如果ax =N（a>0，且a≠1），那么數x叫做以a為底N的對數，記作x=logaN，讀作以a為底N的，其中a叫做對數的底數，N叫做真數，
test(n) {
int i = 1;
while (i <= n) {
i = 2 * i;
}
}
隨著回圈次數的增加，i的值變化如下
根據對數函式的公式 2的i次方等于n,i等于log2n
最好情況時間復雜度
資料比較有序的情況的時間復雜度
最壞情況時間復雜度
資料完全無序
空間復雜度
與n無關的代碼空間復雜度可以忽略
空間復雜度O(n)
test(n) {
//在記憶體中開辟了一個長度為n的陣列
List array = List(n);
print(array.length);
}
本文由博客群發一文多發等運營工具平臺 OpenWrite 發布
轉載請註明出處，本文鏈接：https://www.uj5u.com/yidong/229048.html
標籤：其他
上一篇：再也不用擔心問RecycleView了——面試真題詳解
下一篇：演算法的時間復雜度