簡述演算法復雜度的分析方法

1. 什麼是演算法復雜度

演算法復雜度，即演算法在編寫成可執行程序後，運行時所需要的資源，資源包括時間資源和內存資源。
同一問題可用不同演算法解決，而一個演算法的質量優劣將影響到演算法乃至程序的效率。演算法分析的目的在於選擇合適演算法和改進演算法。一個演算法的評價主要從時間復雜度和空間復雜度來考慮。
時間復雜度
（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)) 為演算法的漸進時間復雜度，簡稱時間復雜度。
空間復雜度
與時間復雜度類似，空間復雜度是指演算法在計算機內執行時所需存儲空間的度量。記作:
S(n)=O(f(n))
演算法執行期間所需要的存儲空間包括3個部分：
·演算法程序所佔的空間；
·輸入的初始數據所佔的存儲空間；
·演算法執行過程中所需要的額外空間。
在許多實際問題中，為了減少演算法所佔的存儲空間，通常採用壓縮存儲技術。

2. 演算法復雜度的復雜度分析

通常一個演算法的復雜度是由其輸入量決定的，隨著輸入的增加，不同演算法的復雜度增長速度如右圖所示：
為了降低演算法復雜度，應當同時考慮到輸入量，設計較好的演算法。

3. 請明白人教下,演算法時間復雜度分析.

演算法（Algorithm）是一系列解決問題的清晰指令，也就是說，能夠對一定規范的輸入，在有限時間內獲得所要求的輸出。如果一個演算法有缺陷，或不適合於某個問題，執行這個演算法將不會解決這個問題。不同的演算法可能用不同的時間、空間或效率來完成同樣的任務。一個演算法的優劣可以用空間復雜度與時間復雜度來衡量。
演算法可以理解為有基本運算及規定的運算順序所構成的完整的解題步驟。或者看成按照要求設計好的有限的確切的計算序列，並且這樣的步驟和序列可以解決一類問題。
一個演算法應該具有以下五個重要的特徵：
1、有窮性： 一個演算法必須保證執行有限步之後結束；
2、確切性： 演算法的每一步驟必須有確切的定義；
3、輸入：一個演算法有0個或多個輸入，以刻畫運算對象的初始情況，所謂0個輸入是指演算法本身定除了初始條件；
4、輸出：一個演算法有一個或多個輸出，以反映對輸入數據加工後的結果。沒有輸出的演算法是毫無意義的；
5、可行性： 演算法原則上能夠精確地運行，而且人們用筆和紙做有限次運算後即可完成。
計算機科學家尼克勞斯-沃思曾著過一本著名的書《數據結構十演算法= 程序》，可見演算法在計算機科學界與計算機應用界的地位。
同一問題可用不同演算法解決，而一個演算法的質量優劣將影響到演算法乃至程序的效率。演算法分析的目的在於選擇合適演算法和改進演算法。一個演算法的評價主要從時間復雜度和空間復雜度來考慮。
時間復雜度
演算法的時間復雜度是指演算法需要消耗的時間資源。一般來說，計算機演算法是問題規模n 的函數f(n)，演算法的時間復雜度也因此記做
T(n)=Ο(f(n))
因此，問題的規模n 越大，演算法執行的時間的增長率與f(n) 的增長率正相關，稱作漸進時間復雜度（Asymptotic Time Complexity）。
空間復雜度
演算法的空間復雜度是指演算法需要消耗的空間資源。其計算和表示方法與時間復雜度類似，一般都用復雜度的漸近性來表示。同時間復雜度相比，空間復雜度的分析要簡單得多。
詳見網路詞條"演算法復雜度"
1.遞推法
遞推法是利用問題本身所具有的一種遞推關系求問題解的一種方法。它把問題分成若干步，找出相鄰幾步的關系，從而達到目的，此方法稱為遞推法。
2.遞歸
遞歸指的是一個過程：函數不斷引用自身，直到引用的對象已知
3.窮舉搜索法
窮舉搜索法是對可能是解的眾多候選解按某種順序進行逐一枚舉和檢驗，並從眾找出那些符合要求的候選解作為問題的解。
4.貪婪法
貪婪法是一種不追求最優解，只希望得到較為滿意解的方法。貪婪法一般可以快速得到滿意的解，因為它省去了為找最優解要窮盡所有可能而必須耗費的大量時間。貪婪法常以當前情況為基礎作最優選擇，而不考慮各種可能的整體情況，所以貪婪法不要回溯。
5.分治法
把一個復雜的問題分成兩個或更多的相同或相似的子問題，再把子問題分成更小的子問題……直到最後子問題可以簡單的直接求解，原問題的解即子問題的解的合並。
6.動態規劃法
動態規劃是一種在數學和計算機科學中使用的，用於求解包含重疊子問題的最優化問題的方法。其基本思想是，將原問題分解為相似的子問題，在求解的過程中通過子問題的解求出原問題的解。動態規劃的思想是多種演算法的基礎，被廣泛應用於計算機科學和工程領域。
7.迭代法
迭代是數值分析中通過從一個初始估計出發尋找一系列近似解來解決問題（一般是解方程或者方程組）的過程，為實現這一過程所使用的方法統稱為迭代法。

4. 演算法時間復雜度的分析

不是呢。
關鍵要看n的大小和常量系數。
比如： O(N)的演算法實際是20n， 而O(n^2)的演算法實際是n^2
當輸入數據規模n=10的時候，前者 是20*10 = 200 > 10^2 = 100.

5. 進行演算法的復雜度分析以及漸進效率分析

(1) C=105和N0=1 是什麼意思
這里只是給出例子, 說明C 和n0不是固定的, 但只要找到一組確定的C, n0, 就表示符合O(g(n))
(2) C2g（n）=<t(n)=<C1g(n)
這里也是類似，
考慮n(n-1)/2<=n^2/2時， 可取c1=1/2, n0=0
考慮n(n-1)/ >= n^2/4時，可取c2=1/4, n0=2
最終取n0=2即可滿足上限和下限要求。

6. 時間復雜度(計算方法,如果計算,及其解釋)

時間復雜度
1.
演算法復雜度分為
時間復雜度和空間復雜度。
作用:
時間復雜度是度量演算法執行的時間長短;而空間復雜度是度量演算法所需存儲空間的大小。
2.
一般情況下，演算法的基本操作重復執行的次數是模塊n的某一個函數f(n)，因此，演算法的時間復雜度記做:T(n)=O(f(n))
分析:隨著模塊n的增大，演算法執行的時間的增長率和f(n)的增長率成正比，所以f(n)越小，演算法的時間復雜度越低，演算法的效率越高。
3.
在計算時間復雜度的時候，先找出演算法的基本操作，然後根據相應的各語句確定它的執行次數，在找出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的三次方)

7. 如何計算一個演算法的時間復雜度

求解演算法的時間復雜度的具體步驟是：

1、找出演算法中的基本語句：

演算法中執行次數最多的那條語句就是基本語句，通常是最內層循環的循環體。

2、計算基本語句的執行次數的數量級：

（1）只需計算基本語句執行次數的數量級，這就意味著只要保證基本語句執行次數的函數中的最高次冪正確即可，可以忽略所有低次冪和最高次冪的系數。

（2）這樣能夠簡化演算法分析，並且使注意力集中在最重要的一點上：增長率。

3、用大Ο記號表示演算法的時間性能：

（1）將基本語句執行次數的數量級放入大Ο記號中。

（2）如果演算法中包含嵌套的循環，則基本語句通常是最內層的循環體，如果演算法中包含並列的循環，則將並列循環的時間復雜度相加。例如：

for(i=1;i<=n;i++)x++;for(i=1;i<=n;i++)
for(j=1;j<=n;j++)x++;

（3）第一個for循環的時間復雜度為Ο(n)，第二個for循環的時間復雜度為Ο(n2)，則整個演算法的時間復雜度為Ο(n+n2)=Ο(n2)。

8. 如何分析演算法的時間復雜度 知乎

求解演算法的時間復雜度的具體步驟是：⑴找出演算法中的基本語句；演算法中執行次數最多的那條語句就是基本語句，通常是最內層循環的循環體。⑵計算基本語句的執行次數的數量級；只需計算基本語句執行次數的數量級，這就意味著只要保證基本語句執行次數

9. 遞歸演算法時間復雜度怎麼分析

1、遞歸
是指對一個問題的求解，可以通過同一問題的更簡單的形式的求解來表示. 並通過問題的簡單形式的解求出復雜形式的解. 遞歸是解決一類問題的重要方法. 遞歸程序設計是程序設計中常用的一種方法，它可以解決所有有遞歸屬性的問題，並且是行之有效的. 但對於遞歸程序運行的效率比較低，無論是時間還是空間都比非遞歸程序更費，若在程序中消除遞歸調用，則其運行時間可大為節省. 以下討論遞歸的時間效率分析方法，以及與非遞歸設計的時間效率的比較.
2 時間復雜度的概念及其計算方法
演算法是對特定問題求解步驟的一種描述. 對於演算法的優劣有其評價准則，主要在於評價演算法的時間效率，演算法的時間通過該演算法編寫的程序在計算機中運行的時間來衡量，所花費的時間與演算法的規模n有必然的聯系，當問題的規模越來越大時，演算法所需時間量的上升趨勢就是要考慮的時間度量.
演算法的時間度量是依據演算法中最大語句頻度（指演算法中某條語句重復執行的次數）來估算的，它是問題規模n的某一個函數f(n). 演算法時間度量記作：T（n）=O（f（n））
它表示隨問題規模n的增大，演算法執行時間的增長率和f（n）的增長率相同，稱作演算法的時間復雜度，簡稱時間復雜度[2].
例如下列程序段：
（1）x=x+1;（2）for(i=1;i<=n;i++) x=x+1;（3）for(j=1;j<=n;j++) for(k=1;k<=n;k++) x=x+1. 以上三個程序段中，語句x=x+1的頻度分別為1，n，n2，則這三段程序的時間復雜度分別為O（1），O（n），O（n2）.
求解過程為：先給出問題規模n的函數的表達式，然後給出其時間復雜度T（n）.
但是在現實程序設計過程中，往往遇到的問題都是比較復雜的演算法，就不能很容易地寫出規模n的表達式，也比較難總結其時間復雜度. 遞歸函數就是屬於這種情況. 下面舉例說明遞歸函數的時間復雜度的分析方法.

10. 什麼是並行演算法的復雜度復雜度作用可以通過哪些指標來分析

1. 時間復雜度

2. 演算法的時間復雜度是指執行演算法所需要的時間。一般來說，計算機演算法是問題規模n 的函數f(n)，演算法的時間復雜度也因此記做。

4. T(n)=Ο(f(n))

6. 因此，問題的規模n 越大，演算法執行的時間的增長率與f(n) 的增長率正相關，稱作漸進時間復雜度

8. 2.空間復雜度

9. 演算法的空間復雜度是指演算法需要消耗的內存空間。其計算和表示方法與時間復雜度類似，一般都用復雜度的漸近性來表示。同時間復雜度相比，空間復雜度的分析要簡單得多。

11. 3.正確性

13. 演算法的正確性是評價一個演算法優劣的最重要的標准。

15. 4.可讀性

17. 演算法的可讀性是指一個演算法可供人們閱讀的容易程度。

18. 5.健壯性

19. 健壯性是指一個演算法對不合理數據輸入的反應能力和處理能力，也成為容錯性。