第四節(jié)．計算復(fù)雜性理論介紹-文庫吧資料
2024-09-13 15:24本頁面
【正文】 作為子程序，如果把 B 的子程序作為一個Step， A 的算法是多項式時間算法。 這樣分兩步做： (1)猜想 (2)驗證 NP 類問題＝ {對問題的一個猜想存在多項式時間算法來驗證它的判定問題 } 抓住了多項式時間內(nèi)可驗證性。但如果回答“是”，我們?nèi)绻麘岩删驼埶o一條這樣的旅行路線經(jīng)證實。 即：時間復(fù)雜度函數(shù)是 ))(( npO 的算法 指數(shù)時間算法：時間復(fù)雜性函數(shù)不能表示成 ))(( npO 的算法（包括：nnlog ：非多項式函數(shù)，不是指數(shù)函數(shù)） P 類問題＝ {有多項式時間算法解決的判定問題 }。 問：是否有 C 的一個旅行路線，全長不超過 B。 對不確定的循環(huán)次數(shù) ?估計最壞情況下的計算量（如 while 循環(huán)） 三、決策（判定）問題 判定問題就是回答“是”或“否”的問題。 計算復(fù)雜性理論是問題難易程度的理論。規(guī)模為： n2 （ n：問題規(guī)模 ) 例 !n 時間復(fù)雜函數(shù) 10 20 30 40 50 60 n 2n 3n 5n 秒 秒 秒 秒 0. 0016秒 秒 0. 0025秒 分 秒 n2 n3
公司管理相關(guān)推薦
鄂ICP備17016276號-1