演算法執行長短

⑴ 演算法的執行效率和數據內存有關系嗎

嚴格的說演算法的執行效率跟演算法本身的效率和計算機的效率有關。

計算機的效率包括cpu和內存的速度。這是你執行演算法時候實實在在花費的時間長短。

撇開計算機的效率，演算法本身的效率跟演算法本身和數據有關。比如冒泡排序，如果數據本身已經接近要求的順序和是逆序差別極大。

⑵ 一個演算法的執行步驟可以是無限的

這句話不對，所包含的步驟是無限的演算法是無法完成的，所以是錯的。一個演算法應該具有以下五個重要的特徵：

1、有窮性
演算法的有窮性是指演算法必須能在執行有限個步驟之後終止；

2、確切性
演算法的每一步驟必須有確切的定義；

3、輸入項
一個演算法有0個或多個輸入，以刻畫運算對象的初始情況，所謂0個輸入是指演算法本身定出了初始條件；

4、輸出項
一個演算法有一個或多個輸出，以反映對輸入數據加工後的結果。沒有輸出的演算法是毫無意義的；

5、可行性
演算法中執行的任何計算步驟都是可以被分解為基本的可執行的操作步，即每個計算步都可以在有限時間內完成（也稱之為有效性）。

⑶ 如何評價一個演算法的好壞

首先，這個演算法必須是正確的
其次，好的演算法應該是友好的，便於人們理解和交流，並且是機器可執行的。
這個演算法還需要足夠健壯，即當輸入的數據非法或不合理時，也能適當的做出正確的反應或進行相應的處理
最後它還必須擁有高效率和低存儲量要求。
也就是所謂的時間復雜度和空間復雜度

1.時間復雜度

定義:在計算機科學中,演算法的時間復雜度是一個函數,他定量描述了該演算法的運行時間.一個演算法執行所耗費的時間,從理論上講,只有你把你的程序放機器上跑起來,才能知道.然而我們有一套時間復雜度的分析方式.一個演算法所花費的時間與其中語句的執行次數成正比例.演算法中的基本操作的執行次數,為演算法的時間復雜度.

2.時間復雜度為什麼不使用時間來衡量而使用基本語句的運行次數來衡量?

演算法的執行時間依賴於具體的軟硬體環境，所以，不能用執行時間的長短來衡量演算法的時間復雜度，而要通過基本語句執行次數的數量級來衡量。

3.時間復雜度的O漸進表示法(Big O notation)

是用於描述函數漸進行為的數學符號.

大O階方法推導:
計算基本語句的執行次數的數量級;
只需計算基本語句執行次數的數量級，這就意味著只要保證基本語句執行次數的函數中的最高次冪正確即可，可以忽略所有低次冪和最高次冪的系數。這樣能夠簡化演算法分析，並且使注意力集中在最重要的一點上:增長率。
如果演算法中包含嵌套的循環，則基本語句通常是最內層的循環體，如果演算法中包含並列的循環，則將並列循環的時間復雜度相加。例如:

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

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

4.時間復雜度的:最優、平均、最差情況，為什麼時間復雜度看的是最差情況?

最差情況下的復雜度是所有可能的輸入數據所消耗的最大資源，如果最差情況下的復雜度符合我們的要求，我們就可以保證所有的情況下都不會有問題。

某些演算法經常遇到最差情況。比如一個查找演算法，經常需要查找一個不存在的值。
也許你覺得平均情況下的復雜度更吸引你，可是平均情況也有幾點問題。第一，難計算，多數演算法的最差情況下的復雜度要比平均情況下的容易計算的多，第二，有很多演算法的平均情況和最差情況的復雜度是一樣的. 第三，什麼才是真正的平均情況?如果你假設所有可能的輸入數據出現的概率是一樣的話，也是不合理的。其實多數情況是不一樣的。而且輸入數據的分布函數很可能是你沒法知道。
考慮最好情況的復雜度更是沒有意義。

5.如何求解:二分查找、遞歸求階乘、遞歸斐波那契的時間復雜度?

二分查找:通過折紙查找求解時間復雜度為O(logN);
遞歸求階乘:數基本操作遞歸N次得到時間復雜度為O(N);
遞歸斐波那契:分析得出基本操作遞歸了2N次,時間復雜度為O(2N);

6.什麼是空間復雜度?

空間復雜度是對一個演算法在運行過程中臨時佔用存儲空間大小的度量.空間復雜度不是程序佔用了多少bytes的空間,因為這個也沒太大意義,所以空間復雜度算的是變數的個數.空間復雜度計算規則基本跟時間復雜度類似,也使用大O漸進法表示.

7.如何求空間復雜度? 普通函數&遞歸函數

一個演算法的空間復雜度只考慮在運行過程中為局部變數分配的存儲空間的大小，它包括為參數表中形參變數分配的存儲空間和為在函數體中定義的局部變數分配的存儲空間兩個部分。若一個演算法為 遞歸演算法，其空間復雜度為遞歸所使用的堆棧空間的大小，它等於一次調用所分配的臨時存儲空間的大小乘以被調用的次數(即為遞歸調用的次數加1，這個1表示開始進行的一次非遞歸調用)。演算法的空間復雜度一般也以數量級的形式給出。如當一個演算法的空間復雜度為一個常量，即不隨被處理數據量n的大小而改變時，可表示為O(1);當一個演算法的空間復雜度與以2為底的n的對數成正比時，可表示為O(log2n);當一個演算法的空間復雜度與n成線性比例關系時，可表示為O(n).若形參為數組，則只需要為它分配一個存儲由實參傳送來的一個地址指針的空間，即一個機器字長空間;若形參為引用方式，則也只需要為其分配存儲一個地址的空間，用它來存儲對應實參變數的地址，以便由系統自動引用實參變數。
8. 分析遞歸斐波那契數列的:時間、空間復雜度，並對其進行優化，偽遞歸優化->循環優化

long long Fib(int N) {
if (N < 3)
return 1;
return Fib(N - 1) + Fib(N - 2);
}

普通遞歸實現的斐波那契數列:
時間復雜度:O(2^n)

計算並根據O漸進表示法得出時間復雜度.

空間復雜度:O(N);遞歸深度乘以(每一次遞歸的空間佔用{有輔助空間或常量})

偽遞歸優化:

long long fib (long long first, longlong second, int N) {
if(N <3)
return 1;
if(N == 3)
return first + second;
return fib(second, first+second,N-1);
}

時間復雜度:
O(N);
遞歸深度乘以每次遞歸的循環次數
空間復雜度:
O(1)或O(N)
關鍵看編譯器是否優化,優化則為O(1)否則O(N);

循環優化:

long long Fib(int N) {
long long first = 1;
long long second = 1;
long long ret = 0;
for (int i = 3; i <= N ; ++i) {
ret = first + second;
first = second;
second = ret;
}
return second;
}

時間復雜度:O(N);

空間復雜度:O(1);

9.常見時間復雜度

常見的演算法時間復雜度由小到大依次為: Ο(1)＜Ο(log2n)＜Ο(n)＜Ο(nlog2n)＜Ο(n2)＜Ο(n3)＜…＜Ο(2n)＜Ο(n!) Ο(1)表示基本語句的執行次數是一個常數，一般來說，只要演算法中不存在循環語句，其時間復雜度就是Ο(1)。Ο(log2n)、Ο(n)、Ο(nlog2n)、Ο(n2)和Ο(n3)稱為多項式時間，而Ο(2n)和Ο(n!)稱為指數時間。

⑷ 度量一個演算法的執行時間通常能有幾種方法

C 演算法效率是指演算法執行的時間，演算法執行時間需通過依據該演算法編制的程序在計算機上運行時所消耗的時間來度量。而度量一個程序的執行時間通常有兩種方法*（一）事後統計的方法（二）事前分析估算的方法。