第十七課：數(shù)據(jù)結(jié)構(gòu)（上）-全文預(yù)覽
【正文】 i++) if (array[i] == target) return true。 a = t1 + t2 ? 、最差、平均性能 對每一個算法不能只考慮單一的增長率，而應(yīng)該給出最佳、最差、平均的增長率函數(shù) . 2 查找算法 ? 從數(shù)組的第一個元素開始查找，并將其與查找值比較，如果相等則停止，否則繼續(xù)下一個元素查找，直到找到匹配值。 t4 } 假設(shè) t1 t4分別代表每條語句的執(zhí)行時間，那么，以上代碼的總執(zhí)行時間為： t1 + t2 + n(t3 + 2t4).其中 n = test_data,當(dāng) test_data增大時， t1和 t2可以忽略不計，也就是說，對于很大的 n,執(zhí)行時間可以近似于： n(t3 + 2t4) ? 一個算法中包含的對象和引用的數(shù)目，越多則內(nèi)存使用越高，反之越低 ?比較增長率 ? 條件 1： c≦ f(n)/g(n) ≦ d (其中 c和 d為正常數(shù)， n代表輸入大小 ) 當(dāng)滿足以上條件 1時，則 f(n)和 g(n)具備相同的增長率，或者兩函數(shù)復(fù)雜度的階相同！ 如： f(n) = n + 100 和 g(n) = + 10 上兩函數(shù)就具備相同的增長率。 t2 for (int i = 1。兩種類型指令：不管輸入大小，執(zhí)行次數(shù)永遠不變；執(zhí)行次數(shù)隨著輸入大小改變而改變。 ?算法的效率分析標(biāo)準(zhǔn) ?簡單性和清晰度 ?空間效率 ?時間效率 ?算法的類型 ? 貪婪算法 (greedy algorithm) ? 分治算法 (divideandconquer algorithm) ? 回溯算法 (backtracking algorithm) ?計算增長率的方式 ? 通過 ()方法來測試 * 缺點： ，測試時間會變得不切實際！ ? 指令 指編寫算法的代碼 .對一個算法的實現(xiàn)代碼計算執(zhí)行指令次數(shù)。 t1 int testVar = 0。 t4 testVar。請比較以上兩函數(shù)增長率是否一樣，如果不一樣，誰的增長率小？ ? O表示法 如果 f的增長率小于或者等于 g的增長率，則我們可以用如下的大 O表示法： f = O(g) O表示 on the order of 將代碼 1的代數(shù)增長率函數(shù)的大 O表達式如下： f(n) = t1 + t2 + n(t3 + 2t4) = a1*n + a = O(n) 其中 a1 = t3 + 2t4。 i 。也就是說只需比較一次就可達到目的，因此最佳情況的大 O表達式為： O(1) 要查找的值在數(shù)組的末尾或者不存在，則對大小為 n的數(shù)組必須比較 n次，大O表達式為： O(n)
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號-1