數據結構與算法 java描述 第一章 算法及其複雜度
數據結構與算法 java描述 筆記
第一章 算法及其複雜度
算法的定義
在特定計算模型下，在信息處理過程中為了解決某一類問題而設計的一個指令序列。
要素
- 輸入：待處理的信息，即對具體問題的描述。
- 輸出：經過處理之後得到的信息，即問題的答案
- 確定性：任一算法都可以描述為由若干種基本操作組成的序列。
- 可行性：在相應的計算模型中，每一基本操作都可以實現，且能夠在常數時間內完成。
- 有窮性：對於任何輸入，按照算法，經過有窮次基本操作都可以得到正確的輸出。
算法性能的分析與評價
問題規模、運行時間及時間複雜度
為了簡化分析，我們通常只考慮輸入規模這一主要因素。
如果將某一算法為了處理規模為 n 的問題所需的時間記作 T(n)，那麼隨着問題規模 n 的增長，運行時間 T(n)將如何增長？我們將 T(n) 稱作算法的時間複雜度。
漸進複雜度
在評價算法的運行時間時，我們往往可以忽略其在處理小規模問題時的性能，轉而關注其在處理足夠大規模問題時的性能，即所謂的漸進複雜度（Asmpototic complexity）。
大 O 記號
如果存 在正常數 a、N 和一個函數 f(n)，使得對於任何 n > N，都有
T(n) < a × f(n)
我們就可以認為在 n 足夠大之後，f(n)給出了 T(n)的一個上界。
對於這種情況，我們記之為 T(n) = O(f(n)) 這裡的 O 稱作「大 O 記號（Big-O notation）」。
大Ω記號
如果存在正常數 a、N 和一個函數 g(n)，使得對於任何 n > N，都有
T(n) > a × g(n)
我們就可以認為在 n 足夠大之後，g(n)給出了 T(n)的一個下界。
對於這種情況，我們記之為 T(n) = Ω(g(n)) 這裡的Ω稱作「大Ω記號（Big-Ω notation）」。
Θ記號
如果存在正常數 a N，都有
a × h(n) < T(n) < b × h(n)
我們就可以認為在 n 足夠大之後，h(n)給出了 T(n)的一個確界。
對於這種情況，我們記之為 T(n) = Θ(h(n)) Θ記號是對算法執行效率的一種準確估計⎯⎯對於規模為 n 的任意輸入，算法的運行時間都與 Θ(h(n))同階。
空間複雜度
算法所需使用的存儲空間量，即算法空間複雜度。
就漸進複雜度的意義而言，在任何一個算法的任何一次運行過程中，其實際佔用的存 儲空間都不會多於其間執行的基本操作次數。
引入時間複雜度的各種記號來度量算法的空間複雜度。
算法複雜度及其分析
O(1)⎯⎯取非極端元素
問題：給定整數子集S, +∞ > |S| = n ≥ 3，從中找出一個元素 a∈S，使得 a ≠ max(S)且 a ≠ min(S)。也就是說，在最大、最小者之外，取出任意一個數。
算法：NonextremeElement(S[], n)
輸入：由n個整數構成的集合S
輸出：其中的任一非極端元素
{
任取的三個元素x, y, z ∈ S; //既然S是集合，這三個元素必互異
通過比較，找出其中的最小者min{x, y, z}和最大者max{x, y, z};
輸出最小、最大者之外的那個元素;
}
思路：
S 是有限集，故其中的最大、最小元素各有且僅有一個。
因此，無論 S 的規 模有多大，在前三個元素 S[0]、S[1]和 S[2]中，必包含至少一個非極端元素。
我們可以取 x = S[0]、y = S[1]和 z = S[ 2]，這隻需執行三次基本操作，耗費 O(3)時間。
為了確定這三個元 素的大小次序，我們最多需要做三次比較（請讀者自己給出證明），也是 O(3)時間。
最後，輸出居中 的那個元素只需 O(1)時間。
運行時間為： T(n) = O(3) + O(3) + O(1) = O(7) = O(1)
O(logn)⎯⎯進制轉換
問題：給定任一十進制整數，將其轉換為三進制表示。比如
23(10) = 212(3)
101(10) = 10202(3)
算法：BaseConversion(n)
輸入：十進制整數n
輸出：n的三進制表示
{
不斷循環，直到n = 0 {
輸出 n % 3; //取模
令 n = n/3; //整除
}
}
以 101(10)為例思路：
第一輪循環，輸出 101 mod 3 = 2，n = 100/3 = 33； 2
第二輪循環，輸出 33 mod 3 = 0，n = 33/3 = 11； 0
第三輪循環，輸出 11 mod 3 = 2，n = 11/3 = 3； 2
第四輪循環，輸出 3 mod 3 = 0，n = 3/3 = 1； 0
第五輪循環，輸出 1 mod 3 = 1，n = 1/3 = 0。 1
result=10202(3)
該算法由若干次循環構成， 每一輪循環內部，都只需進行兩次基本操作（取模、整除）。
每經過一輪循環，n都至少減少至 1/3。於是，至多經過
\]
次循環，即 可減小至 0。
因此，該算法需要運行 O(2×(1+[log3n])) = O(log3n)時間。
鑒於大 O 記號的性質，我們通常會忽略對數函數的常底數。比如這裡的底數為常數 3，故通常 將上述複雜度記作 O(logn)。
O(n)⎯⎯數組求和
問題：給定n個整數，計算它們的總和。
算法：Sum(A[], n)
輸入：由n個整數組成的數組A[]
輸出：A[]中所有元素的總和
{
令s = 0;
對於每一個A[i]，i = 0, 1, …, n-1
令s = s + A[i];
輸出s;
}
思路
對s的初始化需要O(1)時間。
每一輪循環中只需進行一次累 加運算，這屬於基本操作，可以在O(1)時間內完成。
O(1) + O(1)×n = O(n+1) = O(n)
O(n\(^2\) )⎯⎯起泡排序
問題：冒泡排序
算法：Bubblesort(S[], n)
輸入：n個元素組成的一個序列S[]，每個元素由[0..n-1]之間的下標確定，元素之間可以比較大小
輸出：重新調整S[]中元素的次序，使得它們按照非降次序排列
{
從S[0]和S[1]開始，依次檢查每一對相鄰的元素;
只要它們位置顛倒，則交換其位置;
反覆執行上述操作，直到每一對相鄰元素的次序都符合要求;
}
思路：
為了對n個整數排序，該算法的外循環最多需要做n輪。
經過第i輪循環，元素 S[n-i-1]必然就位，i = 0, 1, …, n-1。\(r\)
在第i輪外循環中，內循環需要做n-i-1 輪。
在每一輪內循環中， 需要做一次比較操作，另外至多需要做三次賦值操作，這些都屬於基本操作，可以在O(4)的時間內 完成。
\]
\]
鑒於大 O 記號的特性，低次項可以忽略，常係數可以簡化為 1，故再次得到 T(n) = O(n^2 )
O(2\(^r\) )⎯⎯冪函數
問題:慮冪函數的計算
算法：PowerBruteForce(r)
輸入：非負整數r
輸出：冪2^r
{
power = 1;
while (0 < r--)
power = power * 2;
return power;
}
共需要做r次迭代，每次迭代只涉及常數次基本操作，故總共需要運行O(r)時間。
問題的輸入規模為n，故有O(r) = O(2\(^n\) )。
計算模型
-
可解性
現代意義上的電子計算機所對應的計算模型，就是所謂的圖靈機
-
有效可解
具體來說就是指存在某一算法，能夠在多項式時間以內解決這一問題。反之，若某問題的任一 算法都具有不低於指數的複雜度，則不是有效可解的
-
下界
在任何一種特定計算模型下，對於任一可有效解決的問題，任何算法的時間複雜度都 不可能低於某一範圍，我們稱之為該問題在這一計算模型下的複雜度下界，或簡稱該問題的下界。
遞歸
當某個方法調用自己時，我們就稱之為遞歸調用（Recursive call ）。
線性遞歸
類方法的每個實例只能遞歸地調用自己至多一次.
最後一次遞歸調用被稱作遞歸的「基底」，簡稱「遞歸基」。
性質:經過有限的時間後，它必須能夠終止。
線性遞歸式算法都具有如下形式：
- 檢測遞歸基。首先要檢測是否到達遞歸基，也就是最基本、最簡單的情況，在這些平凡情 況下無需做進一步遞歸調用。
- 遞歸處理。如果尚未遇到平凡的情況，則執行一次遞歸調用。通常，遞歸調用有多種可能， 此時需要經過進一步的檢測以判斷具體應按何種方式做遞歸調用。
遞歸算法的複雜度分析
遞歸跟蹤法
一種直觀的、可視的分析方法,就是將遞歸方法的執行過程表示為圖形的形式.方法的每一實例都對應於一個方框，其中註明了該實例調用的參數；若方法實例 M 調用方法實例 N，則在 M 與 N 對 應的方框之間添加一條有向聯線，指明調用與被調用的關係。
遞推方程法
對遞歸的模式進行歸納從而導出關於複雜度函數的遞推方程，遞歸方程的解將給出算法的複雜度。
二分遞歸
將一個大問題分解為兩個子問題，然後分別通過遞歸調用來求解，這種情 況稱作二分遞歸（Binary recursion ）。
多分支遞歸
一個問題可能需要分解為不止兩個子問題，此時就要採用多分支遞歸（Multiple recursion）。
