計(jì)算理論與算法分析設(shè)計(jì)第一章

1、教材教材: 1王王 王曉東王曉東,計(jì)算機(jī)算法設(shè)計(jì)與分析計(jì)算機(jī)算法設(shè)計(jì)與分析(第第4版版),電子工業(yè)電子工業(yè). 2S 唐常杰等譯唐常杰等譯, Sipser著著, 計(jì)算理論導(dǎo)引計(jì)算理論導(dǎo)引, 機(jī)械工業(yè)機(jī)械工業(yè). 參考資料參考資料:3C 潘金貴等譯潘金貴等譯, Cormen等著等著, 算法導(dǎo)論算法導(dǎo)論, 機(jī)械工業(yè)機(jī)械工業(yè). 4M 黃林鵬等譯黃林鵬等譯, Manber著著, 算法引論算法引論-一種創(chuàng)造性方一種創(chuàng)造性方法法, 電子電子. 5劉劉 劉汝佳等劉汝佳等, 算法藝術(shù)與信息學(xué)競賽算法藝術(shù)與信息學(xué)競賽, 清華大學(xué)清華大學(xué).6L Lewis等著等著, 計(jì)算理論基礎(chǔ)計(jì)算理論基礎(chǔ), 清華大學(xué)清華大學(xué). 計(jì)

2、算理論與計(jì)算理論與算法分析設(shè)計(jì)算法分析設(shè)計(jì) 劉劉 慶慶 暉暉 課程內(nèi)容課程內(nèi)容l算法算法: 概述概述, 遞歸與分治遞歸與分治, 動(dòng)態(tài)規(guī)劃動(dòng)態(tài)規(guī)劃, 貪心法貪心法, 回溯法回溯法, 分支限界法分支限界法, 概率算法概率算法, 線性規(guī)劃與網(wǎng)絡(luò)流線性規(guī)劃與網(wǎng)絡(luò)流l計(jì)算理論基礎(chǔ)計(jì)算理論基礎(chǔ): 集合關(guān)系與語言集合關(guān)系與語言, 有窮自動(dòng)機(jī)有窮自動(dòng)機(jī), 圖靈機(jī)圖靈機(jī), 不可判定性不可判定性, 計(jì)算復(fù)雜性計(jì)算復(fù)雜性, NP完全性等完全性等.l 56學(xué)時(shí)學(xué)時(shí)l成績成績l平時(shí)成績平時(shí)成績30%, 期末閉卷成績期末閉卷成績70 第一章第一章 算法概述算法概述第一部分第一部分 什么是算法什么是算法 第二部分第二部分

3、算法分析與分析起步算法分析與分析起步 第一部分第一部分什么是算法什么是算法什么是算法什么是算法教材教材(王王)上的解釋上的解釋是指解決問題的一種方法或一個(gè)過程是指解決問題的一種方法或一個(gè)過程是若干指令的有窮序列是若干指令的有窮序列, 滿足滿足: (1) 輸入輸入: 零個(gè)或多個(gè)外部提供的量零個(gè)或多個(gè)外部提供的量 (2) 輸出輸出: 產(chǎn)生至少一個(gè)量作為輸出產(chǎn)生至少一個(gè)量作為輸出 (3) 確定性確定性: 每條指令是清晰每條指令是清晰, 無歧義無歧義 (4) 有限性有限性: 每條指令的執(zhí)行次數(shù)每條指令的執(zhí)行次數(shù), 時(shí)間有限時(shí)間有限什么是算法什么是算法算法導(dǎo)論算法導(dǎo)論C:解決可計(jì)算問題的一個(gè)工具解決可計(jì)

4、算問題的一個(gè)工具將輸入轉(zhuǎn)換為輸出的一個(gè)可計(jì)算步驟序列將輸入轉(zhuǎn)換為輸出的一個(gè)可計(jì)算步驟序列韋氏大學(xué)詞典韋氏大學(xué)詞典:求解問題的一個(gè)過程求解問題的一個(gè)過程, 步驟有限步驟有限, 通常有重復(fù)操作通常有重復(fù)操作; 廣義地說廣義地說, 是按部就班解決一個(gè)問題的過程是按部就班解決一個(gè)問題的過程.以上這些都可以說是算法的直觀解釋以上這些都可以說是算法的直觀解釋 . 會(huì)不會(huì)有問題沒有算法呢會(huì)不會(huì)有問題沒有算法呢?找最大數(shù)問題找最大數(shù)問題l輸入輸入: 一個(gè)實(shí)數(shù)序列一個(gè)實(shí)數(shù)序列a1,an.l輸出輸出: max a1,an .l輸入樣例輸入樣例: 1.1, 2.3, 4, 10, 8, 7, 3, 8對應(yīng)輸出對應(yīng)輸

5、出: 10 l算法算法: l1. 令令max=a1. l2. 對對 i = 2 到到 n, l3. 若若 max ai , 則則 max = ai . l4. 輸出輸出max. 輸入輸入,輸出輸出 確定性確定性有限性有限性可計(jì)算步驟可計(jì)算步驟 一個(gè)過程一個(gè)過程 有重復(fù)操作有重復(fù)操作 按部就班按部就班PCP問題沒有算法問題沒有算法Post Corresponding Problem(S)輸入輸入: 一簇骨牌一簇骨牌t1b1,t2b2tkbk解解(匹配匹配)是一個(gè)序列是一個(gè)序列i1,i2,il1,k, 使得使得lliiiiiibbbttt2121 l 輸出輸出: 給定骨牌簇是否有解給定骨牌簇是否有

6、解. bcaaabcaaabcc,2 1 3 2 43n+1問題目前不知道有沒有算法問題目前不知道有沒有算法l輸入輸入: 一個(gè)整數(shù)一個(gè)整數(shù)n,l映射映射: f(n) = n/2, 若若n是偶數(shù)是偶數(shù); f(n) = 3n+1, 若若n是奇數(shù)是奇數(shù). l迭代迭代: 5168, 到到1則停止則停止l輸出輸出: n可在可在f迭代下是否能停止迭代下是否能停止 l直接模擬是正確的算法嗎直接模擬是正確的算法嗎?l27需迭代需迭代111步步(見右圖見右圖) l151018都能到都能到1.(wiki)什么是正確的算法什么是正確的算法l對每個(gè)輸入樣例對每個(gè)輸入樣例, l 都能停機(jī)都能停機(jī), 并輸出正確的結(jié)果并輸

7、出正確的結(jié)果. (C)l什么是不正確的算法什么是不正確的算法? 為什么需要嚴(yán)格定義算法為什么需要嚴(yán)格定義算法? l什么問題被解決了什么問題被解決了? (找最大數(shù)找最大數(shù))什么問題沒有被解決什么問題沒有被解決? (3n+1問題問題)什么問題沒有解決方案什么問題沒有解決方案? (PCP問題問題)l將在計(jì)算理論部分給出算法的嚴(yán)格定義將在計(jì)算理論部分給出算法的嚴(yán)格定義. 程序程序=數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)+算法算法l數(shù)據(jù)結(jié)構(gòu)是數(shù)據(jù)結(jié)構(gòu)是l為方便獲取和修改數(shù)據(jù)而存儲(chǔ)組織數(shù)據(jù)的方為方便獲取和修改數(shù)據(jù)而存儲(chǔ)組織數(shù)據(jù)的方式式 l本課程主要關(guān)注算法本課程主要關(guān)注算法, l僅在有必要的時(shí)候講解相關(guān)數(shù)據(jù)結(jié)構(gòu)僅在有必要的時(shí)候

8、講解相關(guān)數(shù)據(jù)結(jié)構(gòu) 算法技術(shù)算法技術(shù)l很多著名算法書很多著名算法書:計(jì)算機(jī)程序設(shè)計(jì)藝術(shù)、算法導(dǎo)論計(jì)算機(jī)程序設(shè)計(jì)藝術(shù)、算法導(dǎo)論 等等可作為算法可作為算法“菜譜菜譜”.l但實(shí)際工作中總會(huì)遇到菜譜中沒有的問題但實(shí)際工作中總會(huì)遇到菜譜中沒有的問題.l所以需要學(xué)習(xí)算法設(shè)計(jì)和分析技術(shù)所以需要學(xué)習(xí)算法設(shè)計(jì)和分析技術(shù)l本課程涉及的技術(shù)本課程涉及的技術(shù)(王王)有有:分治分治, 動(dòng)態(tài)規(guī)劃動(dòng)態(tài)規(guī)劃, 貪心貪心, 回溯回溯, 分支限界分支限界, 隨機(jī)等隨機(jī)等 l本課程約涉及本課程約涉及50個(gè)問題個(gè)問題(王王):01背包問題背包問題,單源最短路單源最短路, 旅行售貨員問題等旅行售貨員問題等算法的效率算法的效率l什么是高效

9、的算法什么是高效的算法?l 運(yùn)行速度和占用空間可以用來度量效率運(yùn)行速度和占用空間可以用來度量效率輸入規(guī)模輸入規(guī)模n n耗費(fèi)時(shí)間耗費(fèi)時(shí)間1 1小時(shí)小時(shí)/ /天天/ /年可解的問題實(shí)例的最大規(guī)模年可解的問題實(shí)例的最大規(guī)模計(jì)算機(jī)計(jì)算機(jī)快快100100倍計(jì)算機(jī)倍計(jì)算機(jī)快快10001000倍計(jì)算機(jī)倍計(jì)算機(jī)多多項(xiàng)項(xiàng)式式時(shí)時(shí)間間n nN1N1100 N1100 N11000 N11000 N1n2n2N2N210 N210 N231.6 N231.6 N2n3n3N3N34.64 N34.64 N310 N310 N3n5n5N4N42.5 N42.5 N43.98 N43.98 N4指數(shù)指數(shù)時(shí)間時(shí)間2n2

10、nN5N5N5 + 6.64N5 + 6.64N5 + 9.97N5 + 9.973n3nN6N6N6 + 4.19N6 + 4.19N6 + 6.29N6 + 6.29高效的算法高效的算法l多項(xiàng)式時(shí)間算法在理論上是高效的算法多項(xiàng)式時(shí)間算法在理論上是高效的算法l指數(shù)時(shí)間完全問題指數(shù)時(shí)間完全問題l 例例: 全量詞化布爾公式是否真全量詞化布爾公式是否真(TQBF)x1y1x2y2P(x1,y1,x2,y2,) 其中其中P是布爾是布爾公式公式lNP(非確定性多項(xiàng)式時(shí)間非確定性多項(xiàng)式時(shí)間)完全問題完全問題l 也是可以多項(xiàng)式時(shí)間驗(yàn)證解正確性的問題也是可以多項(xiàng)式時(shí)間驗(yàn)證解正確性的問題.l 例例: 布爾公式

11、是否有真賦值布爾公式是否有真賦值(CNF-SAT)=(x)y) (x(z)有真賦值有真賦值(x,y,z)=(F,T,F) 例例: 3-SAT, CLIQUE, 頂點(diǎn)覆蓋頂點(diǎn)覆蓋, 哈密頓回路等哈密頓回路等 NP完全問題完全問題l目前還沒有找到多項(xiàng)式時(shí)間算法目前還沒有找到多項(xiàng)式時(shí)間算法七大千禧問題之一七大千禧問題之一l密碼系統(tǒng)設(shè)計(jì)密碼系統(tǒng)設(shè)計(jì)l說明目前沒有好算法說明目前沒有好算法l解決方案解決方案: 修改問題修改問題, 或使用近似算法或使用近似算法第二部分第二部分算法設(shè)計(jì)與分析起步算法設(shè)計(jì)與分析起步設(shè)計(jì)算法的步驟設(shè)計(jì)算法的步驟: 確定問題確定問題 給出算法給出算法, 分析算法復(fù)雜度分析算法復(fù)雜度

12、 尋求最優(yōu)算法尋求最優(yōu)算法 找最大數(shù)問題找最大數(shù)問題l輸入輸入: 一個(gè)實(shí)數(shù)序列一個(gè)實(shí)數(shù)序列a1,an.l輸出輸出: max a1,an .序列序列32572918最大最大33577999修改次數(shù)修改次數(shù)10110100比較次數(shù)比較次數(shù)01111111l輸入樣例的規(guī)模輸入樣例的規(guī)模 N = 8l輸入樣例輸入樣例 I = 3,2,5,7,2,9,1,8l時(shí)間復(fù)雜度時(shí)間復(fù)雜度: c1N T(N,I) c2 N (很難計(jì)算精確很難計(jì)算精確值值) l以比較次數(shù)以比較次數(shù)(N)計(jì)算時(shí)間復(fù)雜度比較合理計(jì)算時(shí)間復(fù)雜度比較合理關(guān)于算法復(fù)雜度的度量關(guān)于算法復(fù)雜度的度量l 如何計(jì)算算法的復(fù)雜度如何計(jì)算算法的復(fù)雜度?

13、l 時(shí)間時(shí)間: 時(shí)間復(fù)雜度時(shí)間復(fù)雜度l 空間空間: 空間復(fù)雜度空間復(fù)雜度l 輸入規(guī)模輸入規(guī)模l 同樣輸入規(guī)模需要的時(shí)間空間也經(jīng)常不同同樣輸入規(guī)模需要的時(shí)間空間也經(jīng)常不同l 最壞時(shí)間復(fù)雜度最壞時(shí)間復(fù)雜度, 平均時(shí)間復(fù)雜度平均時(shí)間復(fù)雜度 f(n)l 系統(tǒng)不同、緩存大小不同等系統(tǒng)不同、緩存大小不同等 諸多影響因素諸多影響因素 l 需要約定輸入規(guī)模的度量需要約定輸入規(guī)模的度量: 數(shù)列數(shù)列, 圖等圖等找最大次大數(shù)問題找最大次大數(shù)問題(M): 方法一方法一l輸入輸入: 一個(gè)實(shí)數(shù)序列一個(gè)實(shí)數(shù)序列a1,an.l輸出輸出: 最大和次大的數(shù)最大和次大的數(shù).序列序列32572918最大最大3次大次大2比較次數(shù)比較次

14、數(shù)1l輸入規(guī)模輸入規(guī)模 N = 8, I = 3,2,5,7,2,9,1,8找最大次大數(shù)問題找最大次大數(shù)問題(M): 方法一方法一l輸入輸入: 一個(gè)實(shí)數(shù)序列一個(gè)實(shí)數(shù)序列a1,an.l輸出輸出: 最大和次大的數(shù)最大和次大的數(shù).序列序列32572918最大最大35次大次大23比較次數(shù)比較次數(shù)11l輸入規(guī)模輸入規(guī)模 N = 8, I = 3,2,5,7,2,9,1,8找最大次大數(shù)問題找最大次大數(shù)問題(M): 方法一方法一l輸入輸入: 一個(gè)實(shí)數(shù)序列一個(gè)實(shí)數(shù)序列a1,an.l輸出輸出: 最大和次大的數(shù)最大和次大的數(shù).序列序列32572918最大最大357次大次大235比較次數(shù)比較次數(shù)111l輸入規(guī)模輸入

15、規(guī)模 N = 8, I = 3,2,5,7,2,9,1,8找最大次大數(shù)問題找最大次大數(shù)問題(M): 方法一方法一l輸入輸入: 一個(gè)實(shí)數(shù)序列一個(gè)實(shí)數(shù)序列a1,an.l輸出輸出: 最大和次大的數(shù)最大和次大的數(shù).序列序列32572918最大最大3577次大次大2355比較次數(shù)比較次數(shù)1112l輸入規(guī)模輸入規(guī)模 N = 8, I = 3,2,5,7,2,9,1,8找最大次大數(shù)問題找最大次大數(shù)問題(M): 方法一方法一l輸入輸入: 一個(gè)實(shí)數(shù)序列一個(gè)實(shí)數(shù)序列a1,an.l輸出輸出: 最大和次大的數(shù)最大和次大的數(shù).序列序列32572918最大最大3577999次大次大2355778比較次數(shù)比較次數(shù)11121

16、22l輸入規(guī)模輸入規(guī)模 N = 8, I = 3,2,5,7,2,9,1,8l對所有規(guī)模對所有規(guī)模N輸入輸入, 比較次數(shù)最多比較次數(shù)最多2(N-2)+1=2N-3 l漸近意義上已經(jīng)最優(yōu)漸近意義上已經(jīng)最優(yōu) , 但是能否進(jìn)一步改進(jìn)但是能否進(jìn)一步改進(jìn)? 最大次大最大次大(M): 方法二方法二-分治分治l分治法分治法: 設(shè)規(guī)模設(shè)規(guī)模n比較次數(shù)最多比較次數(shù)最多T(n)T(n) = 2T(n/2) + 2, l T(2)=1, T(3)=3l若若n=2k, T(n)=1.5n-2; (M)l若若n=32k, T(n)=5n/3-2l對一般對一般n, 可歸納證明可歸納證明 1.5n-2 T(n) 5n/3-

17、2 l 證明見本證明見本ppt附錄附錄. 3 2 5 7 2 9 1 83 2 5 72 9 1 8759898找最大次大數(shù)問題找最大次大數(shù)問題(M): 方法三方法三l輸入輸入: 一個(gè)實(shí)數(shù)序列一個(gè)實(shí)數(shù)序列a1,an.l輸出輸出: 最大和次大的數(shù)最大和次大的數(shù).序列序列32572918最大最大3次大次大2比較次數(shù)比較次數(shù)1找最大次大數(shù)問題找最大次大數(shù)問題(M): 方法三方法三l輸入輸入: 一個(gè)實(shí)數(shù)序列一個(gè)實(shí)數(shù)序列a1,an.l輸出輸出: 最大和次大的數(shù)最大和次大的數(shù).序列序列32572918最大最大377次大次大255比較次數(shù)比較次數(shù)112找最大次大數(shù)問題找最大次大數(shù)問題(M): 方法三方法三l

18、輸入輸入: 一個(gè)實(shí)數(shù)序列一個(gè)實(shí)數(shù)序列a1,an.l輸出輸出: 最大和次大的數(shù)最大和次大的數(shù).序列序列32572918最大最大37799次大次大25527比較次數(shù)比較次數(shù)11212找最大次大數(shù)問題找最大次大數(shù)問題(M): 方法三方法三l輸入輸入: 一個(gè)實(shí)數(shù)序列一個(gè)實(shí)數(shù)序列a1,an.l輸出輸出: 最大和次大的數(shù)最大和次大的數(shù).序列序列32572918最大最大3779989次大次大2552718比較次數(shù)比較次數(shù)1121212對所有規(guī)模對所有規(guī)模n輸入輸入, 比較次數(shù)最多比較次數(shù)最多 3(n-2)/2 +1 = 3 n/2 - 2 1.5n-2 注注: C中對最大最小數(shù)問題使用了這個(gè)算法中對最大最小

19、數(shù)問題使用了這個(gè)算法. 找最大次大數(shù)問題找最大次大數(shù)問題(M): 方法四方法四3 2 5 7 2 9 1 83 2 5 72 9 1 875,398,297,8,22 95 71 83 2修改的分治修改的分治: 維護(hù)可能次大集維護(hù)可能次大集 比較次數(shù)比較次數(shù):n-1+log2n32759281復(fù)雜度復(fù)雜度f(n)的漸近記法的漸近記法l稱稱g(n)是是f(n)的漸進(jìn)上界的漸進(jìn)上界, 即即f(n) = O(g(n), 若若 c0, N0, nN, f(n) c g(n) 例例: n2 n = O(n3), n2 n = O(n2) l稱稱g(n)是是f(n)的漸進(jìn)下界的漸進(jìn)下界, 即即f(n) =

20、 (g(n), 若若 c0, N0, nN, f(n) c g(n)例例: n2 n = (n), n2 n = (n2) lf(n) = (g(n) 漸近同階漸近同階 ( 王王, C), 若若 f(n) = O(g(n) 且且 f(n) = (g(n) 例例: n2 n = (n2) l注注: n0, n2 n2 n 10001n2. 漸近記法的等價(jià)極限定義漸近記法的等價(jià)極限定義O, , 示意圖示意圖f(n)c0g(n)c1g(n)n0f(n) = (g(n) f(n)cg(n)n0f(n) = O(g(n) f(n)cg(n)n0f(n) = (g(n) 常用漸近函數(shù)常用漸近函數(shù)f(n)

21、= O(g(n) 為方便為方便, g(n)通常取通常取 nk, /多項(xiàng)式多項(xiàng)式 nklogn, /含對數(shù)項(xiàng)含對數(shù)項(xiàng) en 或或 eO(n) /指數(shù)函數(shù)指數(shù)函數(shù)注注: 為本課程為本課程ppt書寫方便書寫方便logn是是log2n 例如例如: log n3 = O(log n), log 3n = O(n)時(shí)間復(fù)雜度的分析技巧時(shí)間復(fù)雜度的分析技巧l直接估計(jì)、遞推關(guān)系直接估計(jì)、遞推關(guān)系l均攤分析均攤分析l 累計(jì)法累計(jì)法, 記賬法記賬法, 勢能法勢能法(C) l例例: k位二進(jìn)制計(jì)數(shù)器問題位二進(jìn)制計(jì)數(shù)器問題l從從0執(zhí)行加執(zhí)行加1操作操作, 直到到直到到n. l關(guān)鍵量關(guān)鍵量: 位反轉(zhuǎn)次數(shù)位反轉(zhuǎn)次數(shù)l粗略

22、估計(jì)粗略估計(jì)O(kn)或或O(nlogn) 從從0到到n需要的時(shí)間需要的時(shí)間-累計(jì)法累計(jì)法累計(jì)法累計(jì)法: 每位反轉(zhuǎn)總次數(shù)每位反轉(zhuǎn)總次數(shù) n+n/2+n/4+2n 均攤均攤: (累計(jì)后均攤累計(jì)后均攤) 每次操作平均反轉(zhuǎn)每次操作平均反轉(zhuǎn)2次次 從從0到到n需要的時(shí)間需要的時(shí)間-記賬法記賬法Ai我我時(shí)間時(shí)間0變變11變變02元元1元元0元元1元元 每次每次+1 只有只有1位從位從0變變1 總收入總收入 = 2n, 總支出總支出 2n 2n-k 從從0到到n需要的時(shí)間需要的時(shí)間-勢能法勢能法勢能法的原理勢能法的原理Di : 第第i次操作后的數(shù)據(jù)結(jié)構(gòu)次操作后的數(shù)據(jù)結(jié)構(gòu), i=0:n ci : 第第i次操

23、作的實(shí)際耗費(fèi)時(shí)間次操作的實(shí)際耗費(fèi)時(shí)間, i=1:n : 勢能函數(shù)勢能函數(shù), 將將Di映射為一個(gè)實(shí)數(shù)映射為一個(gè)實(shí)數(shù) (Di) di = ci + (Di) - (Di-1)第第i次操作的均攤時(shí)間次操作的均攤時(shí)間 i=1n di = i=1n (ci + (Di) - (Di-1) = i=1n ci + (Dn) - (D0)若若 (Di) (D0) (勢能勢能), 則則 i=1n di i=1n ci . 應(yīng)用到計(jì)數(shù)器問題應(yīng)用到計(jì)數(shù)器問題. (Di) = Di中中1的個(gè)數(shù)的個(gè)數(shù). di = ci + (Di) - (Di-1) = 2 證明證明: 設(shè)從設(shè)從Di-1到到Di有有b位位1變變0,

24、1位位0變變1, 則則ci=1+b, (Di) - (Di-1) =1-b一些符號(hào)和公式一些符號(hào)和公式 x : 小于等于小于等于x的最大整數(shù)的最大整數(shù), x :大于等于大于等于x 的最小整數(shù)的最小整數(shù) anbbnaloglog )1(1()(2!nennnn 1110 xxxnnkknkOnk1) 1 (ln1log n! = (n log n) 等比級(jí)數(shù)求和等比級(jí)數(shù)求和 調(diào)和級(jí)數(shù)調(diào)和級(jí)數(shù) Stirling公式公式本章小結(jié)和作業(yè)本章小結(jié)和作業(yè)算法分析題算法分析題 1-1, 1-2, 1-4 1-1 求下列函數(shù)的漸近表達(dá)式求下列函數(shù)的漸近表達(dá)式: 3n2+10n; n2/10+2n; 21+1/

25、n; log n3; 10log3n. 1-2 試論試論O(1)與與O(2)的區(qū)別的區(qū)別. 1-4 (1) 假設(shè)某算法在輸入規(guī)模為假設(shè)某算法在輸入規(guī)模為n時(shí)的計(jì)算時(shí)間為時(shí)的計(jì)算時(shí)間為T(n)=32n. 在某臺(tái)計(jì)算機(jī)在某臺(tái)計(jì)算機(jī)上上實(shí)現(xiàn)并完成該算法的時(shí)間為實(shí)現(xiàn)并完成該算法的時(shí)間為t秒秒. 現(xiàn)有另一臺(tái)計(jì)算機(jī)現(xiàn)有另一臺(tái)計(jì)算機(jī), 其運(yùn)行速度是第一臺(tái)的其運(yùn)行速度是第一臺(tái)的64倍倍, 那么在這臺(tái)新機(jī)器上用同一算法在那么在這臺(tái)新機(jī)器上用同一算法在t秒內(nèi)能解輸入規(guī)模為多大的問題秒內(nèi)能解輸入規(guī)模為多大的問題?(2) 若上述算法的計(jì)算時(shí)間改進(jìn)為若上述算法的計(jì)算時(shí)間改進(jìn)為T(n)=n2, 其余條件不變其余條件不變, 則在新機(jī)器上用則在新機(jī)器上用t秒秒時(shí)間能解輸入規(guī)模為多大的問題時(shí)間能解輸入規(guī)模為多大的問題?(3) 若上述算法的計(jì)算時(shí)間改進(jìn)為若上述算法的計(jì)算時(shí)間改進(jìn)為T(n