a演算法時間復雜度

1. 數據結構中排序和查找各種時間復雜度

數據結構中排序和查找各種時間復雜度
(1)冒泡排序
冒泡排序就是把小的元素往前調或者把大的元素往後調。比較是相鄰的兩個元素比較，交換也發生在這兩個元素之間。所以相同元素的前後順序並沒有改變，所以冒泡排序是一種穩定排序演算法。
(2)選擇排序
選擇排序是給每個位置選擇當前元素最小的，比如給第一個位置選擇最小的。…… 例子說明好多了。序列5 8 5 2 9， 我們知道第一遍選擇第1個元素5會和2交換，那麼原序列中2個5的相對前後順序就被破壞了， 所以選擇排序不穩定的排序演算法
(3)插入排序
插入排序是在一個已經有序的小序列的基礎上，一次插入一個元素。比較是從有序序列的末尾開始，也就是想要插入的元素和已經有序的最大者開始比起，如果比它大則直接插入在其後面，否則一直往前找直到找到它該插入的位置。如果和插入元素相等，那麼插入元素把想插入的元素放在相等元素的後面。所以，相等元素的前後順序沒有改變。所以插入排序是穩定的。
(4)快速排序
快速排序有兩個方向，左邊的i下標一直往右走（往後），當a[i] <= a[center_index]，其中center_index是中樞元素的數組下標，一般取為數組第0個元素。而右邊的j下標一直往左走（往前），當a[j] > a[center_index]。如果i和j都走不動了，i <= j, 交換a[i]和a[j],重復上面的過程，直到i>j。 交換a[j]和a[center_index]，完成一趟快速排序。在中樞元素和a[j]交換的時候，很有可能把前面的元素的穩定性打亂，比如序列為 5 3 3 4 3 8 9 10 11， 現在中樞元素5和3(第5個元素，下標從1開始計)交換就會把元素3的穩定性打亂，所以快速排序是一個不穩定的排序演算法。（不穩定發生在中樞元素和a[j]交換的時刻）
(5)歸並排序
歸並排序是把序列遞歸地分成短序列，遞歸出口是短序列只有1個元素(認為直接有序)或者2個序列(1次比較和交換),然後把各個有序的段序列合並成一個有序的長序列。不斷合並直到原序列全部排好序。相等時不發生交換。所以，歸並排序也是穩定的排序演算法。
(6)基數排序
基數排序是按照低位先排序，然後收集；再按照高位排序，然後再收集；依次類推，直到最高位。有時候有些屬性是有優先順序順序的，先按低優先順序排序，再按高優先順序排序，最後的次序就是高優先順序高的在前，高優先順序相同的低優先順序高的在前。基數排序基於分別排序，分別收集，所以其是穩定的排序演算法。
(7)希爾排序(shell)
希爾排序是按照不同步長對元素進行插入排序，當剛開始元素很無序的時候，步長最大，所以插入排序的元素個數很少，速度很快；當元素基本有序了，步長很小，插入排序對於有序的序列效率很高。所以，希爾排序的時間復雜度會比o(n^2)好一些。由於多次插入排序，我們知道一次插入排序是穩定的，不會改變相同元素的相對順序，但在不同的插入排序過程中，相同的元素可能在各自的插入排序中移動，最後其穩定性就會被打亂，所以shell排序是不穩定的。
(8)堆排序
我們知道堆的結構是節點i的孩子為2*i和2*i+1節點，大頂堆要求父節點大於等於其2個子節點，小頂堆要求父節點小於等於其2個子節點。在一個長為n的序列，堆排序的過程是從第n/2開始和其子節點共3個值選擇最大(大頂堆)或者最小(小頂堆),這3個元素之間的選擇當然不會破壞穩定性。但當為n/2-1, n/2-2, ...1這些個父節點選擇元素時，就會破壞穩定性。有可能第n/2個父節點交換把後面一個元素交換過去了，而第n/2-1個父節點把後面一個相同的元素沒有交換，那麼這2個相同的元素之間的穩定性就被破壞了。所以，堆排序是不穩定的排序演算法
一、排序
排序法 平均時間 最差情形 穩定度 額外空間 備注
冒泡 O(n2) O(n2) 穩定 O(1) n小時較好
交換 O(n2) O(n2) 不穩定 O(1) n小時較好
選擇 O(n2) O(n2) 不穩定 O(1) n小時較好
插入 O(n2) O(n2) 穩定 O(1) 大部分已排序時較好
Shell O(nlogn) O(ns) 1<s<2 不穩定???="" o(1)???????="" s是所選分組</s
快速 O(nlogn) O(n2) 不穩定 O(nlogn) n大時較好
歸並 O(nlogn) O(nlogn) 穩定 O(1) n大時較好
堆 O(nlogn) O(nlogn) 不穩定 O(1) n大時較好
基數 O(logRB) O(logRB) 穩定 O(n) B是真數(0-9)，R是基數(個十百)
二、查找
未寫……
三 樹圖
克魯斯卡爾演算法的時間復雜度為O（eloge）
普里姆演算法的時間復雜度為O（n2）
迪傑斯特拉演算法的時間復雜度為O（n2）
拓撲排序演算法的時間復雜度為O（n+e）
關鍵路徑演算法的時間復雜度為O（n+e）

2. 時間復雜度怎麼計算

1. 一般情況下，演算法的基本操作重復執行的次數是模塊n的某一個函數f（n），因此，演算法的時間復雜度記做：T（n）=O（f（n））
分析：隨著模塊n的增大，演算法執行的時間的增長率和f（n）的增長率成正比，所以f（n）越小，演算法的時間復雜度越低，演算法的效率越高。
2. 在計算時間復雜度的時候，先找出演算法的基本操作，然後根據相應的各語句確定它的執行次數，再找出T（n）的同數量級（它的同數量級有以下：1，Log2n ，n ，nLog2n ，n的平方，n的三次方，2的n次方，n！），找出後，f（n）=該數量級，若T(n)/f(n)求極限可得到一常數c，則時間復雜度T（n）=O（f（n））
例：演算法：
for（i=1;i<=n;++i）
{
for(j=1;j<=n;++j)
{
c[ i ][ j ]=0; //該步驟屬於基本操作 執行次數：n的平方 次
for(k=1;k<=n;++k)
c[ i ][ j ]+=a[ i ][ k ]*b[ k ][ j ]; //該步驟屬於基本操作 執行次數：n的三次方 次
}
}
則有 T（n）= n的平方+n的三次方，根據上面括弧里的同數量級，我們可以確定 n的三次方 為T（n）的同數量級
則有f（n）= n的三次方，然後根據T（n）/f（n）求極限可得到常數c
則該演算法的 時間復雜度：T（n）=O（n的三次方）

3. 演算法復雜度的時間復雜度

（1）時間頻度
一個演算法執行所耗費的時間，從理論上是不能算出來的，必須上機運行測試才能知道。但我們不可能也沒有必要對每個演算法都上機測試，只需知道哪個演算法花費的時間多，哪個演算法花費的時間少就可以了。並且一個演算法花費的時間與演算法中語句的執行次數成正比例，哪個演算法中語句執行次數多，它花費時間就多。一個演算法中的語句執行次數稱為語句頻度或時間頻度。記為T(n)。演算法的時間復雜度是指執行演算法所需要的計算工作量。
（2）時間復雜度
在剛才提到的時間頻度中，n稱為問題的規模，當n不斷變化時，時間頻度T(n)也會不斷變化。但有時我們想知道它變化時呈現什麼規律。為此，我們引入時間復雜度概念。
一般情況下，演算法中基本操作重復執行的次數是問題規模n的某個函數，用T(n)表示，若有某個輔助函數f(n),使得當n趨近於無窮大時，T(n)/f(n)的極限值為不等於零的常數，則稱f(n)是T(n)的同數量級函數。記作T(n)=O(f(n)),稱O(f(n)) 為演算法的漸進時間復雜度，簡稱時間復雜度。
在各種不同演算法中，若演算法中語句執行次數為一個常數，則時間復雜度為O(1),另外，在時間頻度不相同時，時間復雜度有可能相同，如T(n)=n^2+3n+4與T(n)=4n^2+2n+1它們的頻度不同，但時間復雜度相同，都為O(n^2)。
按數量級遞增排列，常見的時間復雜度有：
常數階O(1),對數階O(log2n)(以2為底n的對數，下同),線性階O(n),
線性對數階O(nlog2n),平方階O(n^2)，立方階O(n^3),...，
k次方階O(n^k),指數階O(2^n)。隨著問題規模n的不斷增大，上述時間復雜度不斷增大，演算法的執行效率越低。
演算法的時間性能分析
（1）演算法耗費的時間和語句頻度
一個演算法所耗費的時間=演算法中每條語句的執行時間之和
每條語句的執行時間=語句的執行次數(即頻度(Frequency Count))×語句執行一次所需時間
演算法轉換為程序後，每條語句執行一次所需的時間取決於機器的指令性能、速度以及編譯所產生的代碼質量等難以確定的因素。
若要獨立於機器的軟、硬體系統來分析演算法的時間耗費，則設每條語句執行一次所需的時間均是單位時間，一個演算法的時間耗費就是該演算法中所有語句的頻度之和。
求兩個n階方陣的乘積 C=A×B,其演算法如下:
# define n 100 // n 可根據需要定義,這里假定為100
void MatrixMultiply(int A[a]，int B [n][n]，int C[n][n])
{ //右邊列為各語句的頻度
int i ,j ,k;
(1) for(i=0; i<n;i++) n+1
(2) for (j=0;j<n;j++) { n(n+1)
(3) C[i][j]=0; n2
(4) for (k=0; k<n; k++) n2(n+1)
(5) C[i][j]=C[i][j]+A[i][k]*B[k][j];n3
}
}
該演算法中所有語句的頻度之和(即演算法的時間耗費)為：
T(n)=2n3+3n2+2n+1 (1.1)
分析：
語句(1)的循環控制變數i要增加到n，測試到i=n成立才會終止。故它的頻度是n+1。但是它的循環體卻只能執行n次。語句(2)作為語句(1)循環體內的語句應該執行n次，但語句(2)本身要執行n+1次，所以語句(2)的頻度是n(n+1)。同理可得語句(3)，(4)和(5)的頻度分別是n2，n2(n+1)和n3。
演算法MatrixMultiply的時間耗費T(n)是矩陣階數n的函數。
（2）問題規模和演算法的時間復雜度
演算法求解問題的輸入量稱為問題的規模(Size),一般用一個整數表示。
矩陣乘積問題的規模是矩陣的階數。
一個圖論問題的規模則是圖中的頂點數或邊數。
一個演算法的時間復雜度(Time Complexity, 也稱時間復雜性)T(n)是該演算法的時間耗費，是該演算法所求解問題規模n的函數。當問題的規模n趨向無窮大時，時間復雜度T(n)的數量級(階)稱為演算法的漸進時間復雜度。
演算法MatrixMultiply的時間復雜度T(n)如(1.1)式所示，當n趨向無窮大時，顯然有T(n)~O(n^3);
這表明，當n充分大時，T(n)和n^3之比是一個不等於零的常數。即T(n)和n^3是同階的，或者說T(n)和n^3的數量級相同。記作T(n)=O(n^3)是演算法MatrixMultiply的漸近時間復雜度。
（3）漸進時間復雜度評價演算法時間性能
主要用演算法時間復雜度的數量級(即演算法的漸近時間復雜度)評價一個演算法的時間性能。
演算法MatrixMultiply的時間復雜度一般為T(n)=O(n^3)，f(n)=n^3是該演算法中語句(5)的頻度。下面再舉例說明如何求演算法的時間復雜度。
交換i和j的內容。
Temp=i;
i=j;
j=temp;
以上三條單個語句的頻度均為1，該程序段的執行時間是一個與問題規模n無關的常數。演算法的時間復雜度為常數階，記作T(n)=O(1)。
注意：如果演算法的執行時間不隨著問題規模n的增加而增長，即使演算法中有上千條語句，其執行時間也不過是一個較大的常數。此類演算法的時間復雜度是O(1)。
變數計數之一：
(1) x=0;y=0;
(2) for(k-1;k<=n;k++)
(3) x++;
(4) for(i=1;i<=n;i++)
(5) for(j=1;j<=n;j++)
(6) y++;
一般情況下，對步進循環語句只需考慮循環體中語句的執行次數，忽略該語句中步長加1、終值判別、控制轉移等成分。因此，以上程序段中頻度最大的語句是(6)，其頻度為f(n)=n^2，所以該程序段的時間復雜度為T(n)=O(n^2)。
當有若干個循環語句時，演算法的時間復雜度是由嵌套層數最多的循環語句中最內層語句的頻度f(n)決定的。
變數計數之二：
(1) x=1;
(2) for(i=1;i<=n;i++)
(3) for(j=1;j<=i;j++)
(4) for(k=1;k<=j;k++)
(5) x++;
該程序段中頻度最大的語句是(5)，內循環的執行次數雖然與問題規模n沒有直接關系，但是卻與外層循環的變數取值有關，而最外層循環的次數直接與n有關，因此可以從內層循環向外層分析語句(5)的執行次數：
則該程序段的時間復雜度為T(n)=O(n^3/6+低次項)=O(n^3)。
（4）演算法的時間復雜度不僅僅依賴於問題的規模，還與輸入實例的初始狀態有關。
在數值A[0..n-1]中查找給定值K的演算法大致如下：
(1)i=n-1;
(2)while(i>=0&&(A[i]!=k))
(3) i--;
(4)return i;
此演算法中的語句(3)的頻度不僅與問題規模n有關，還與輸入實例中A的各元素取值及K的取值有關:
①若A中沒有與K相等的元素，則語句(3)的頻度f(n)=n；
②若A的最後一個元素等於K,則語句(3)的頻度f(n)是常數0。

4. 如何計算時間復雜度

1、先找出演算法的基本操作，然後根據相應的各語句確定它的執行次數，再找出T（n）的同數量級（它的同數量級有以下：1，Log2n ，n ，nLog2n ，n的平方，n的三次方，2的n次方，n！），找出後，f（n）=該數量級，若T(n)/f(n)求極限可得到一常數c，則時間復雜度T（n）=O（f（n））。

2、舉例

for（i=1;i<=n;++i）

{for(j=1;j<=n;++j)

{c[ i ][ j ]=0; //該步驟屬於基本操作 執行次數：n的平方次

for(k=1;k<=n;++k)

c[ i ][ j ]+=a[ i ][ k ]*b[ k ][ j ]; //該步驟屬於基本操作 執行次數：n的三次方次}}

則有 T（n）= n的平方+n的三次方，根據上面括弧里的同數量級，我們可以確定 n的三次方為T（n）的同數量級

則有f（n）= n的三次方，然後根據T（n）/f（n）求極限可得到常數c

則該演算法的 時間復雜度：T（n）=O（n的三次方）

),線性階O(n),線性對數階O(nlog2n),平方階O(n^2)，立方階O(n^3),...，

k次方階O(n^k),指數階O(2^n)。隨著問題規模n的不斷增大，上述時間復雜度不斷增大，演算法的執行效率越低。

關於對其的理解

《數據結構（C語言版）》 ------嚴蔚敏 吳偉民編著 第15頁有句話「整個演算法的執行時間與基本操作重復執行的次數成正比。」

基本操作重復執行的次數是問題規模n的某個函數f(n)，於是演算法的時間量度可以記為：T(n) = O(f(n))

如果按照這么推斷，T(n)應該表示的是演算法的時間量度，也就是演算法執行的時間。

而該頁對「語句頻度」也有定義：指的是該語句重復執行的次數。

如果是基本操作所在語句重復執行的次數，那麼就該是f(n)。

上邊的n都表示的問題規模。

5. 請問演算法的時間復雜度是怎麼計算出來的

首先假設任意一個簡單運算的時間都是1，例如a=1;a++;a=a*b;這些運算的時間都是1.

那麼例如
for(int i=0;i<n;++i)
{
for(int j=0;j<m;++j)
a++; //注意，這里計算一次的時間是1.
}
那麼上面的這個例子的時間復雜度就是 m*n

再例如冒泡排序的時間復雜度是N*N；快排的時間復雜度是log(n)。

詳細的情況，建議你看《演算法導論》，裡面有一章節，具體講這個的。

6. 演算法時間復雜度怎麼算

一、概念
時間復雜度是總運算次數表達式中受n的變化影響最大的那一項(不含系數)
比如：一般總運算次數表達式類似於這樣：
a*2^n+b*n^3+c*n^2+d*n*lg(n)+e*n+f
a ！ =0時，時間復雜度就是O(2^n);
a=0,b<>0 =>O(n^3);
a,b=0,c<>0 =>O(n^2)依此類推
eg:
(1) for(i=1;i<=n;i++) //循環了n*n次，當然是O(n^2)
for(j=1;j<=n;j++)
s++;
(2) for(i=1;i<=n;i++)//循環了(n+n-1+n-2+...+1)≈(n^2)/2，因為時間復雜度是不考慮系數的，所以也是O(n^2)
for(j=i;j<=n;j++)
s++;
(3) for(i=1;i<=n;i++)//循環了(1+2+3+...+n)≈(n^2)/2,當然也是O(n^2)
for(j=1;j<=i;j++)
s++;
(4) i=1;k=0;
while(i<=n-1){
k+=10*i; i++; }//循環了n-1≈n次，所以是O(n)(5) for(i=1;i<=n;i++)
for(j=1;j<=i;j++)
for(k=1;k<=j;k++)
x=x+1;
//循環了(1^2+2^2+3^2+...+n^2)=n(n+1)(2n+1)/6(這個公式要記住哦)≈(n^3)/3，不考慮系數，自然是O(n^3)
另外，在時間復雜度中，log(2,n)(以2為底)與lg(n)(以10為底)是等價的，因為對數換底公式：
log(a,b)=log(c,b)/log(c,a)
所以，log(2,n)=log(2,10)*lg(n),忽略掉系數，二者當然是等價的
二、計算方法1.一個演算法執行所耗費的時間，從理論上是不能算出來的，必須上機運行測試才能知道。但我們不可能也沒有必要對每個演算法都上機測試，只需知道哪個演算法花費的時間多，哪個演算法花費的時間少就可以了。並且一個演算法花費的時間與演算法中語句的執行次數成正比例，哪個演算法中語句執行次數多，它花費時間就多。
一個演算法中的語句執行次數稱為語句頻度或時間頻度。記為T(n)。
2.一般情況下，演算法的基本操作重復執行的次數是模塊n的某一個函數f（n），因此，演算法的時間復雜度記做：T（n）=O（f（n））。隨著模塊n的增大，演算法執行的時間的增長率和f（n）的增長率成正比，所以f（n）越小，演算法的時間復雜度越低，演算法的效率越高。
在計算時間復雜度的時候，先找出演算法的基本操作，然後根據相應的各語句確定它的執行次數，再找出T（n）的同數量級（它的同數量級有以下：1，Log2n ，n ，nLog2n ，n的平方，n的三次方，2的n次方，n！），找出後，f（n）=該數量級，若T(n)/f(n)求極限可得到一常數c，則時間復雜度T（n）=O（f（n））。
3.常見的時間復雜度
按數量級遞增排列，常見的時間復雜度有：
常數階O(1), 對數階O(log2n), 線性階O(n), 線性對數階O(nlog2n), 平方階O(n^2)， 立方階O(n^3),...， k次方階O(n^k), 指數階O(2^n) 。
其中，1.O(n)，O(n^2)， 立方階O(n^3),...， k次方階O(n^k) 為多項式階時間復雜度，分別稱為一階時間復雜度，二階時間復雜度。。。。2.O(2^n)，指數階時間復雜度，該種不實用3.對數階O(log2n), 線性對數階O(nlog2n)，除了常數階以外，該種效率最高
例：演算法：
for（i=1;i<=n;++i）
{
for(j=1;j<=n;++j)
{
c[ i ][ j ]=0; //該步驟屬於基本操作 執行次數：n^2
for(k=1;k<=n;++k)
c[ i ][ j ]+=a[ i ][ k ]*b[ k ][ j ]; //該步驟屬於基本操作 執行次數：n^3
}
}
則有 T（n）= n^2+n^3，根據上面括弧里的同數量級，我們可以確定 n^3為T（n）的同數量級
則有f（n）= n^3，然後根據T（n）/f（n）求極限可得到常數c
則該演算法的 時間復雜度：T（n）=O（n^3)
四、

定義：如果一個問題的規模是n，解這一問題的某一演算法所需要的時間為T(n)，它是n的某一函數
T(n)稱為這一演算法的「時間復雜性」。

當輸入量n逐漸加大時，時間復雜性的極限情形稱為演算法的「漸近時間復雜性」。

我們常用大O表示法表示時間復雜性，注意它是某一個演算法的時間復雜性。大O表示只是說有上界，由定義如果f(n)=O(n)，那顯然成立f(n)=O(n^2)，它給你一個上界，但並不是上確界，但人們在表示的時候一般都習慣表示前者。

此外，一個問題本身也有它的復雜性，如果某個演算法的復雜性到達了這個問題復雜性的下界，那就稱這樣的演算法是最佳演算法。

「大O記法」：在這種描述中使用的基本參數是
n，即問題實例的規模，把復雜性或運行時間表達為n的函數。這里的「O」表示量級 (order)，比如說「二分檢索是 O(logn)的」,也就是說它需要「通過logn量級的步驟去檢索一個規模為n的數組」記法 O ( f(n) )表示當 n增大時，運行時間至多將以正比於 f(n)的速度增長。

這種漸進估計對演算法的理論分析和大致比較是非常有價值的，但在實踐中細節也可能造成差異。例如，一個低附加代價的O(n2)演算法在n較小的情況下可能比一個高附加代價的 O(nlogn)演算法運行得更快。當然，隨著n足夠大以後，具有較慢上升函數的演算法必然工作得更快。

O(1)

Temp=i;i=j;j=temp;

以上三條單個語句的頻度均為1，該程序段的執行時間是一個與問題規模n無關的常數。演算法的時間復雜度為常數階，記作T(n)=O(1)。如果演算法的執行時間不隨著問題規模n的增加而增長，即使演算法中有上千條語句，其執行時間也不過是一個較大的常數。此類演算法的時間復雜度是O(1)。

O(n^2)

2.1.
交換i和j的內容
sum=0；（一次）
for(i=1;i<=n;i++)（n次 ）
for(j=1;j<=n;j++)
（n^2次 ）
sum++；（n^2次 ）
解：T(n)=2n^2+n+1 =O(n^2)

2.2.
for (i=1;i<n;i++)
{
y=y+1;①
for
(j=0;j<=(2*n);j++)
x++;②
}
解：
語句1的頻度是n-1
語句2的頻度是(n-1)*(2n+1)=2n^2-n-1
f(n)=2n^2-n-1+(n-1)=2n^2-2
該程序的時間復雜度T(n)=O(n^2).

O(n)

2.3.
a=0;
b=1;①
for
(i=1;i<=n;i++) ②
{
s=a+b;③
b=a;④
a=s;⑤
}
解：語句1的頻度：2,
語句2的頻度：
n,
語句3的頻度： n-1,
語句4的頻度：n-1,
語句5的頻度：n-1,
T(n)=2+n+3(n-1)=4n-1=O(n).

O(log2n
)

2.4.
i=1;①
while (i<=n)
i=i*2; ②
解： 語句1的頻度是1,
設語句2的頻度是f(n),則：2^f(n)<=n;f(n)<=log2n
取最大值f(n)=
log2n,
T(n)=O(log2n )

O(n^3)

2.5.
for(i=0;i<n;i++)
{
for(j=0;j<i;j++)
{
for(k=0;k<j;k++)
x=x+2;
}
}
解：當i=m,
j=k的時候,內層循環的次數為k當i=m時, j 可以取 0,1,...,m-1 , 所以這里最內循環共進行了0+1+...+m-1=(m-1)m/2次所以,i從0取到n, 則循環共進行了: 0+(1-1)*1/2+...+(n-1)n/2=n(n+1)(n-1)/6所以時間復雜度為O(n^3).


我們還應該區分演算法的最壞情況的行為和期望行為。如快速排序的最
壞情況運行時間是 O(n^2)，但期望時間是 O(nlogn)。通過每次都仔細 地選擇基準值，我們有可能把平方情況 (即O(n^2)情況)的概率減小到幾乎等於 0。在實際中，精心實現的快速排序一般都能以 (O(nlogn)時間運行。
下面是一些常用的記法：


訪問數組中的元素是常數時間操作，或說O(1)操作。一個演算法如 果能在每個步驟去掉一半數據元素，如二分檢索，通常它就取 O(logn)時間。用strcmp比較兩個具有n個字元的串需要O(n)時間。常規的矩陣乘演算法是O(n^3)，因為算出每個元素都需要將n對
元素相乘並加到一起，所有元素的個數是n^2。
指數時間演算法通常來源於需要求出所有可能結果。例如，n個元 素的集合共有2n個子集,所以要求出所有子集的演算法將是O(2n)的。指數演算法一般說來是太復雜了，除非n的值非常小，因為，在 這個問題中增加一個元素就導致運行時間加倍。不幸的是，確實有許多問題 (如著名的「巡迴售貨員問題」 )，到目前為止找到的演算法都是指數的。如果我們真的遇到這種情況，通常應該用尋找近似最佳結果的演算法替代之。

7. A*演算法的時間復雜度是多少

從數學上定義，給定演算法A，如果存在函數F(n)，當n=k時，F(k)表示演算法A在輸入規模為k的情況下的運行時間，則稱F(n)為演算法A的時間復雜度。這里首先要明確輸入規模的概念。關於輸入規模，不是很好下定義，非嚴格的講，輸入規模是指演算法A所接受輸入的自然獨立體的大小。例如，對於排序演算法來說，輸入規模一般就是待排序元素的個數，而對於求兩個同型方陣乘積的演算法，輸入規模可以看作是單個方陣的維數。為了簡單起見，總是假設演算法的輸入規模是用大於零的整數表示的，即n=1,2,3,……,k,…… 對於同一個演算法，每次執行的時間不僅取決於輸入規模，還取決於輸入的特性和具體的硬體環境在某次執行時的狀態。所以想要得到一個統一精確的F(n)是不可能的。為了解決這個問題，做以下兩個說明： 1.忽略硬體及環境因素，假設每次執行時硬體條件和環境條件是完全一致的。 2.對於輸入特性的差異，將從數學上進行精確分析並帶入函數解析式。

8. (11) 演算法的時間復雜度是指______。 A. 執行演算法程序所需要的時間 B. 演算法程序的長度 C. 演算法執行過程中所

（11）[答案]C
[考點]數據結構與演算法
[評析]
演算法的復雜度分時間復雜度和空間復雜度。
時間復雜度：在運行演算法時所耗費的時間為f(n)(即 n的函數)。
空間復雜度：實現演算法所佔用的空間為g(n)（也為n的函數）。
稱O(f(n))和O(g(n))為該演算法的復雜度。
簡單的例子比如常見的順序結構時間復雜度為O(1),1層循環裡面次數為n，時間復雜度就是O(n),2層循環for i=1 to n,for j=1 to n演算法時間復雜度為O(n2)（裡面為n的平方），復雜度主要用於演算法的效率比較與優化，比如排序，查找…

9. 求最短路徑的A*演算法的時間復雜度與空間復雜度是多少

從數學上定義，給定演算法A，如果存在函數F(n)，當n=k時，F(k)表示演算法A在輸入規模為k的情況下的運行時間，則稱F(n)為演算法A的時間復雜度。這里首先要明確輸入規模的概念。關於輸入規模，不是很好下定義，非嚴格的講，輸入規模是指演算法A所接受輸入的自然獨立體的大小。例如，對於排序演算法來說，輸入規模一般就是待排序元素的個數，而對於求兩個同型方陣乘積的演算法，輸入規模可以看作是單個方陣的維數。為了簡單起見，總是假設演算法的輸入規模是用大於零的整數表示的，即n=1,2,3,……,k,…… 對於同一個演算法，每次執行的時間不僅取決於輸入規模，還取決於輸入的特性和具體的硬體環境在某次執行時的狀態。所以想要得到一個統一精確的F(n)是不可能的。為了解決這個問題，做以下兩個說明： 1.忽略硬體及環境因素，假設每次執行時硬體條件和環境條件是完全一致的。 2.對於輸入特性的差異，將從數學上進行精確分析並帶入函數解析式。