摘自《數(shù)據(jù)結(jié)構(gòu)和算法分析》Java語(yǔ)言描述

如果認(rèn)為兩個(gè)程序花費(fèi)大致相同的時(shí)間，要確定哪個(gè)程序更快的最好辦法很可能是將他們編碼并運(yùn)行。

一般地，存在集中算法思想，而我們總愿意盡早除去那些不好的算法思想，因此，通常需要分析算法.不僅如此,進(jìn)行分析的能力。不僅如此，進(jìn)行分析的能力常常提供對(duì)于計(jì)算優(yōu)先算法的動(dòng)產(chǎn)能力。一般來(lái)說(shuō)，分析還能準(zhǔn)確地確定瓶頸，這些地方值得仔細(xì)編碼。

為了簡(jiǎn)化分析，我們將采納如下的約定：不存在特定的時(shí)間單位。因此我們拋棄一些前導(dǎo)的常數(shù)，我們還將拋棄低階項(xiàng)，從而要做的事計(jì)算大O運(yùn)行時(shí)間。由于大O是一個(gè)上界，因此我們必須仔細(xì)，絕不要低估程序的運(yùn)行時(shí)間。實(shí)際上，分析的結(jié)果為程序在一定時(shí)間范圍內(nèi)能夠終止運(yùn)行提供了保障。程序可能提前結(jié)束，但是絕不可能錯(cuò)后。

?一個(gè)簡(jiǎn)單的例子：1^3+2^3+3^3+4^3+……+n^3+……

public static int sum(int n) {int partialSum;partialSum = 0;for (int i = 1; i <= n; i++) {partialSum += i *i * i;}return partialSum; }

對(duì)這個(gè)程序段的分析是簡(jiǎn)單的。所有的聲明均不計(jì)時(shí)間。partialSum = 0和return partialSum各占一個(gè)時(shí)間單位。partialSum += i *i * i每執(zhí)行一次占用4個(gè)時(shí)間單元（兩次乘法，一次加法和一次賦值），而執(zhí)行N次共占4N個(gè)時(shí)間單元。for循環(huán)在初始化i、測(cè)試i<=N和對(duì)i的自增運(yùn)算隱含著開(kāi)銷。所有這些總開(kāi)銷是初始化一個(gè)時(shí)間單元，所有測(cè)試為N+1個(gè)單位時(shí)間，而所有的自增運(yùn)算為N個(gè)單位時(shí)間，共2N+2個(gè)時(shí)間單元。我們忽略調(diào)用方法和返回值的開(kāi)銷，得到的總量是6N+4個(gè)時(shí)間單元。因此我們說(shuō)該方法是O(N)。

如果每次分析一個(gè)程序都要演示所有的這些工作，那么這項(xiàng)任務(wù)很快就會(huì)變成負(fù)擔(dān)。由于我們有了大O的結(jié)果，因此就存在許多可以采取的捷徑并且不影響最后的結(jié)果。例如每次都執(zhí)行的partialSum += i *i * i的時(shí)間明顯是類似O(1)，至于精確計(jì)算它究竟是2、3、或者4等是愚蠢的，因?yàn)檫@無(wú)關(guān)緊要。而int partialSum和for循環(huán)顯然是不重要的，所以在這里話費(fèi)時(shí)間是不明智的。這使我們得到若干法則。

法則1——for循環(huán)

一個(gè)for循環(huán)的運(yùn)行時(shí)間至多使該for循環(huán)內(nèi)部那些語(yǔ)句的運(yùn)行時(shí)間乘以迭代的次數(shù)。

法則2——嵌套的for循環(huán)

從里向外分析這些循環(huán)。在一組嵌套循環(huán)內(nèi)部的一條語(yǔ)句總的運(yùn)行時(shí)間為該語(yǔ)句的運(yùn)行時(shí)間乘以該組所有的for循環(huán)的大小的乘積。例如下列程序片段為O(N^2)

for (int i = 0; i < n; i++)for (int j = 0; j < n; j++)System.out.println();

法則3——順序語(yǔ)句

將各個(gè)語(yǔ)句的運(yùn)行時(shí)間求和即可（這意味著，，其中的最大值就是所得的運(yùn)行時(shí)間）例如，下面的程序片段顯示花費(fèi)O(N)，接著使O(N^2)，因此總量也是O(N^2)，而忽略O(shè)(N)

for (int i = 1; i < n; i++) {System.out.println(); } for (int i = 0; i < n; i++)for (int j = 0; j < n; j++)System.out.println();

法則4——if/else語(yǔ)句

if(condition)S1 else S2

一個(gè)if/else語(yǔ)句的運(yùn)行時(shí)間從不超過(guò)判斷的運(yùn)行時(shí)間再加上S1和S2中運(yùn)行時(shí)間長(zhǎng)者的總的運(yùn)行時(shí)間，即運(yùn)行時(shí)間不會(huì)超過(guò) 判斷運(yùn)行時(shí)間加上S1或者S2中較大的運(yùn)行時(shí)間。

…………

其他的法則都是冥想的，但是分析的基本策略使從內(nèi)部（或最深層部分）向外開(kāi)展工作的。如果有方法調(diào)用，那么要首先分析這些調(diào)用。如果有遞歸過(guò)程，那么存在幾種情況：若遞歸實(shí)際上只是被薄面紗遮住的for循環(huán)（很容易轉(zhuǎn)換成for循環(huán)），則分析很簡(jiǎn)單。如下面遞歸實(shí)際上就是一個(gè)for循環(huán)：

public static long factorial(int n) {if (n <= 1)return 1;elsereturn n * factorial(n - 1); }

這是一個(gè)特殊的例子，但當(dāng)遞歸被正常使用時(shí)，很難將其轉(zhuǎn)換成循環(huán)結(jié)構(gòu)。這種情況下，分析將設(shè)計(jì)求解一個(gè)遞推關(guān)系。

public static long fib(int n) {if (n <= 1)return 1;elsereturn fib(n - 1) + fib(n - 2); }

如果將程序編碼并使N為40左右運(yùn)行，程序效率特別低。令T(N)為調(diào)用函數(shù)fib(n)的運(yùn)行時(shí)間。如果N=0或者N=1，則運(yùn)行時(shí)間是個(gè)常數(shù)，因?yàn)槌?shù)不重要并且為了方便計(jì)算，我們可以將T(0)=T(1)=1。對(duì)于N的其他值的運(yùn)行時(shí)間則都是基于基準(zhǔn)情形的運(yùn)行時(shí)間來(lái)度量的。若N>2，則執(zhí)行時(shí)間是判斷時(shí)間加上else語(yǔ)句上的執(zhí)行時(shí)間，而else語(yǔ)句有一次家發(fā)和兩次方法調(diào)用組成。第一次方法調(diào)用是fib(n-1),及T(N-1)運(yùn)行時(shí)間。以此類推可以得到fib(n)的運(yùn)行時(shí)間：
T(N)=T(N-1)+T(N-2)+2 并且

fib(N)=fib(N-1)+fib(N-2)

由歸納法很容易的可以得出T(N)>=fib(N)的結(jié)論。而由fib(N)=fib(N-1)+fib(N-2)使用歸納法可以得出fib(N)>=(3/2)^N，及可得出T(N)>=(3/2)^N，可以看出運(yùn)行時(shí)間以指數(shù)的速度增長(zhǎng)。

這個(gè)程序之所以運(yùn)行緩慢，是因?yàn)榇嬖诖罅慷嘤嗟墓ぷ饕觥Ｔ趂ib(n - 1) + fib(n - 2)語(yǔ)句中，fib(n - 1)調(diào)用的時(shí)候?qū)嶋H上已經(jīng)計(jì)算過(guò)一次fib(n - 2)，而這個(gè)信息被拋棄，之后在+之后又計(jì)算了一次fib(n - 2)。這些拋棄的信息遞歸地合起來(lái)就導(dǎo)致了巨大的運(yùn)行時(shí)間。這或許是“計(jì)算任何事情不要超過(guò)一次”的最好的實(shí)例，但它不應(yīng)使你被嚇得遠(yuǎn)離遞歸而不敢使用。

?

總結(jié)

以上是生活随笔為你收集整理的算法运行时间计算的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。