演算法效率-wenkub.com
2025-01-20 15:00 本頁面
【正文】 分析演算法 最佳情況的時間複雜度 (循序搜尋法)n 基本運算：把 x與陣列中的一個項目進行比較n 輸入大?。?n，陣列中的項目個數(shù)n 因為 ，因此迴圈至少會走一次，如果 x=S[1]，那麼無論 n的大小為何，迴圈都是只走一次。 X位於第 k個位置的機率為 p/n， x不在陣列中的機率為 1p。根據(jù)這個資訊，對於 ， x位於第 k個位置的機率為 1/n。分析演算法 最差情況的時間複雜度 (循序搜尋法 )n 基本運算：將 x與陣中的一個項目進行比較n 輸入大小 ： n，陣列中的項目個數(shù)n 基本運算最多執(zhí)行 n次，也就是當(dāng) x位於陣列的尾端或 x不在陣列中時。n 基本運算：在最內(nèi)層的 for迴圈中的乘法指令n 輸入大?。?n，行數(shù)與列數(shù) fori迴圈的執(zhí)行次數(shù)恆為 n。在 fori迴圈第一次執(zhí)行過後， forj迴圈執(zhí)行 n1次；在 fori迴圈第二次執(zhí)行過後， forj迴圈執(zhí)行 n2次：在 fori迴圈第三次執(zhí)行過後， forj迴圈執(zhí)行 n3次， …… ，在 fori迴圈最後一次執(zhí)行過後， forj迴圈執(zhí)行 1次。因此，基本運算總是被執(zhí)行 n次 ,故可得 T(n)=n分析演算法 所有情況的時間複雜度 (交換排序法 )n 如同先前所提及，對於利用 key的比較來進行排序的演算法，我們可以把比較指令或是指定值指令當(dāng)作是基本運算來看。因此，我們稱這個指令為此演算法的基本運
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號-1