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