演算法效率(編輯修改稿)
2025-02-09 15:00 本頁(yè)面
【文章內(nèi)容簡(jiǎn)介】 裡分析比較的次數(shù)。n 基本運(yùn)算：比較 S[ j ]與 S[i]n 輸入大?。?n，被排序的項(xiàng)目個(gè)數(shù)n 我們必須求得 forj迴圈執(zhí)行的次數(shù)。給定n， fori迴圈執(zhí)行的次數(shù)恆為 n1。在 fori迴圈第一次執(zhí)行過(guò)後， forj迴圈執(zhí)行 n1次；在 fori迴圈第二次執(zhí)行過(guò)後， forj迴圈執(zhí)行 n2次：在 fori迴圈第三次執(zhí)行過(guò)後， forj迴圈執(zhí)行 n3次， …… ，在 fori迴圈最後一次執(zhí)行過(guò)後， forj迴圈執(zhí)行 1次。因此， forj迴圈總共執(zhí)行的次數(shù)可由下式求得 分析演算法 所有情況的時(shí)間複雜度 (矩陣乘法 )n 在最內(nèi)層的 for迴圈中只有一個(gè)由一個(gè)乘法與一個(gè)加法組成的指令。這個(gè)演算法可以被實(shí)作成執(zhí)行的加法個(gè)數(shù)遠(yuǎn)少於執(zhí)行的乘法個(gè)數(shù)。因此，我們將只設(shè)定乘法指令為基本運(yùn)算。n 基本運(yùn)算：在最內(nèi)層的 for迴圈中的乘法指令n 輸入大?。?n，行數(shù)與列數(shù) fori迴圈的執(zhí)行次數(shù)恆為 n。 fori迴圈每執(zhí)行一次， forj迴圈就執(zhí)行 n次； forj迴圈每執(zhí)行一次， fork迴圈就執(zhí)行 n次。因?yàn)榛具\(yùn)算在 fork迴圈的內(nèi)部，因此 最差情況時(shí)間複雜度n 對(duì)於一個(gè)給定的演算法， W(n)被定義為在輸入大小為 n的情況下，該演算法執(zhí)行基本運(yùn)算次數(shù)的最大值。因此 W(n)被稱為該演算法的最差情況時(shí)間複雜度，而其求得過(guò)程稱為最差情況時(shí)間複雜度分析。分析演算法 最差情況的時(shí)間複雜度 (循序搜尋法 )n
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1