算法的定義

算法是解決特定問題求解步驟的描述，在計算機中表現(xiàn)為指令的有限序列，并且每條指令表示一個或者是多個操作。

算法的特性

1.輸入輸出：算法具有零個或者多個輸入，對于絕大多數(shù)情況來說，輸入?yún)?shù)是很有必要的，擔(dān)當(dāng)有些情況僅僅需要我們輸出，比如打印一個“hello world”對于這樣的需求我們只需要輸出就可以了，因此算法至少有一個或者多個輸出。

2.有窮性：算法在執(zhí)行有限的步驟后，會自動結(jié)束而不會出現(xiàn)無限循環(huán)，并且每一個步驟都可以在人們能夠接受的時間內(nèi)完成。

3.確定性：算法的每一個步驟都應(yīng)當(dāng)具有確定的含義，不會出現(xiàn)二義性，即算法在一定的條件下，只有一條執(zhí)行路徑，對于相同的輸入只能有一個輸出結(jié)果。

4.可行性：算法的每一步必須是可行的，即算法的每一步都可以通過執(zhí)行有限次數(shù)完成。

1.正確性：算法至少應(yīng)該具有輸入、輸出和加工處理無歧義性、能正確反映問題的需求，能夠得到問題的正確答案。

2.可讀性：算法設(shè)計出來是為了給人看的，是為了方便解決實際問題，因此需要算法設(shè)計便于閱讀、理解和交流。

3.健壯性：當(dāng)輸入的數(shù)據(jù)不合法時，算法也能做出相應(yīng)的回應(yīng)而不是產(chǎn)生異?；蛘呤悄婷畹慕Y(jié)果。

4.時間效率高和存儲量低：設(shè)計算法應(yīng)該盡量滿足時間效率高和存儲量低的需求，在實際生活中，人們都希望花最少的時間辦成最大的事情，算法也是這樣，最好是利用最少的空間、花費最少的時間來解決問題。

算法的時間復(fù)雜度即算法的時間量度，記作T(n) = O(f(n))。隨著問題規(guī)模n的增長，算法執(zhí)行時間的增長率和f(n)的增長率相同，稱作算法的漸近時間復(fù)雜度，簡稱為時間復(fù)雜度。其中f(n)是問題規(guī)模n的函數(shù)。

1.用常數(shù)1取代運行時間中的所有加法常數(shù)。

2.在修改的運行次數(shù)函數(shù)中只保留最高階項。

3.如果最高階存在且不為1，則去除與這個項相乘的常數(shù)。

與n的大小無關(guān)，執(zhí)行時間恒定的算法，稱之具有O(1)階的時間復(fù)雜度又叫作常數(shù)階。

O(1)

當(dāng)一個循環(huán)體需要執(zhí)行n次的時候，該循環(huán)的時間復(fù)雜度為O(n)

O(n)

我們先看一個例子

O(logn)

上面的代碼每次count值乘以2，就距離n更近了點，也就是說有多少個2相乘之后便會大于n從而退出循環(huán)。由2^x = n 可以得到 x = log2n，即這個循環(huán)的時間復(fù)雜度為O(logn)。

我們先來看一段代碼

O(n^2)

不難看出，循環(huán)中嵌套著一個循環(huán)，每個循環(huán)都要執(zhí)行n次，于是共要執(zhí)行n * n = n^2次，算法的時間復(fù)雜度為O(n^2)。我們可以得出一個結(jié)論：

循環(huán)的時間復(fù)雜度 = 循環(huán)體的時間復(fù)雜度 * 循環(huán)運行的次數(shù)

O(1)<O(logn)<O(n)<O(nlogn)<O(n^2)<O(n^3)<O(2^n)<O(n!)<O(n^n)

注：一般后面三種不予以考慮

求下列代碼的時間復(fù)雜度

練習(xí)

答案是O(n^2)