計(jì)算復(fù)雜性理論介紹(已修改)
2025-09-15 19:19 本頁面
【正文】 第四節(jié)．計(jì)算復(fù)雜性理論介紹 (參考書：“計(jì)算機(jī)和難解性”． 〖美〗 . 加里， . 約翰遜 , 科學(xué)出版社 ) 如何比較兩個(gè)算法的優(yōu)劣： 要比較算法 A 和算法 B 的速度，需要在同一機(jī)器上，同種條件下，同一輸入數(shù)據(jù)運(yùn)行兩個(gè)程序，并比較其時(shí)間。 一般來說，兩個(gè)算法的速度比較應(yīng)獨(dú)立于機(jī)器。而考慮問題規(guī)模，在一般情況下和最壞情況下需要多少次運(yùn)算。 例 1： for（ i=0； in。 i++) for (j=0。 jn。 j++) k=i+j。 規(guī)模為 2n 例 n的二叉樹，要訪問所有結(jié)點(diǎn)。規(guī)模為： n2 （ n：問題規(guī)模 ) 例 !n 時(shí)間復(fù)雜函數(shù) 10 20 30 40 50 60 n 2n 3n 5n 秒 秒 秒 秒 0. 0016秒 秒 0. 0025秒 分 秒 n2 n3 0. 007秒 1. 0 秒 58分 127天 3855世紀(jì) 2* 810 世紀(jì) 360世紀(jì) * 1310世紀(jì)
公司管理相關(guān)推薦
鄂ICP備17016276號-1