計算復(fù)雜性理論介紹-文庫吧
2025-08-01 19:19 本頁面
【正文】 一小時內(nèi)可解決的最大問題的規(guī)模如下表所示： 時間復(fù)雜函數(shù) 用現(xiàn)在的計算機(jī) 用快 100 倍的計算機(jī) 用快 1000 倍的計算機(jī) n 2n 3n 5n 1N 2N 3N 4N 100 1N 10 2N 3N 4N 1000 1N 2N 10 3N 4N n2 n3 5N 6N 5N + 6N + 5N + 6N + 當(dāng) n 較大時： nannnnn ????? 532l o g 通過上表可以看出：指數(shù)函數(shù)隨自變量增加而迅速增加－－（指數(shù)爆炸的） ?多項(xiàng)式時間算法是好的算法，有效算法 。 指數(shù)時間算法不是好算法。 計算復(fù)雜性理論是問題難易程度的理論。 首先回憶復(fù)習(xí) O( )函數(shù) 一、 O( )函數(shù) 定義 : .)( )(,0,))(()( ?????????? xg xfxgOxf （一般省略 A）（表示兩個函數(shù)同階變化） .|)(|,01)()1()( ????????? xfxgOxf .211)( 32323 ???????xxxxxxxf ( 1?x ) ).()( 3xOxf ?? )()()1(5444)( 3333 xOxfxxxxxf ??????? 所以 )()( 3kxOxf ? 錯誤 kxOxf ?? )()( 3 錯誤 二、估計算法
公司管理相關(guān)推薦
鄂ICP備17016276號-1