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