演算法執行度

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

（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。

B. 求語句執行的頻度及此演算法的時間復雜度

LZ，當然不是喲！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)=n2 3n 4與T(n)=4n2 2n 1它們的頻度不同，但時間復雜度相同，都為O(n2)。按數量級遞增排列，常見的時間復雜度有：常數階O(1),對數階O(log2n),線性階O(n),線性對數階O(nlog2n),平方階O(n2)，立方階O(n3),...，k次方階O(nk),指數階O(2n)。隨著問題規模n的不斷增大，上述時間復雜度不斷增大，演算法的執行效率越低。 24846希望對你有幫助！

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

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

D. 一個演算法的執行頻度為(3n2+2nlog2n+4n-7)/(10n),其時間復雜度多少

演算法的執行頻度為(3n2+2nlog2n+4n-7)/(10n),因為當n增大時，最大項為3n/10，所以，其時間復雜度為O(n)。

E. 演算法的什麼復雜度用來度量演算法執行的時間長短

你好，這位朋友其實我覺得你可以根據計時的方法來計算一下時間的長短。祝您生活愉快，身體健康如果有問題隨時聯系我們，謝謝！

F. 一個演算法的基本操作執行次數為(3n2+2nlog2n+4n-7)/(5n)，則其時間復雜度表示為

演算法的時間復雜度是看基本操作的次數，但是基本操作在具體的程序分析時可能不一樣，有的在意元素之間比較的次數，有的在意元素插入或移位的次數，答案為O（n^1/2）可能是因為指定了某種特定的操作作為基本操作。
但是如果給定的基本操作次數為(3n2+2nlog2n+4n-7)/(5n)，則時間復雜度應該為O（n）
個人理解，如有不對，請批評指正

G. 數據結構中評價演算法的兩個重要指標是什麼

數據結構中評價演算法的兩個重要指標是時間復雜度和空間復雜度。

同一問題可用不同演算法解決，而一個演算法的質量優劣將影響到演算法乃至程序的效率。演算法分析的目的在於選擇合適演算法和改進演算法。一個演算法的評價主要從時間復雜度和空間復雜度來考慮。

1、時間復雜度：

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

2、空間復雜度：

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

(7)演算法執行度擴展閱讀：

評估演算法效率的方法：

1、事後統計方法

這種方法主要是通過設計好的測試程序和數據，利用計算機計時器對不同演算法編制的程序的運行時間進行比較，從而確定演算法效率的高低。

2、事前分析估算方法

在計算機程序編寫前，依據統計方法對演算法進行估算。經過總結，可以發現一個高級語言編寫的程序在計算機上運行時所消耗的時間取決於下列因素：演算法採用的策略、編譯產生的代碼質量、問題的輸入規模、機器執行指令的速度。

參考資料來源：網路-演算法

H. 請問下列演算法的語句執行頻度是多少 x=91;y=100; while(y>0) if(x>100) {x=x-10;y--) else x++；

#include<iostream>
using namespace std;
int main()
{
int y, x, a,b, c;
x=91;
y=100;
a = b = c = 0;
while(y>0)
{
if(x>100)
{
a++;
x=x-10;
y--;
}
else
{
x++;
b++;
}
c++;
}
cout <<"if(x>100)語句執行"<<a<<"次"<<endl;
cout <<"else語句執行"<<b<<"次"<<endl;
cout <<"共執行"<<c<<"次"<<endl;
return 0;
}

I. 什麼是演算法效率的度量

這題毫無疑問選b。程序所「占」空間指的僅僅是代碼長度，也就是你理解的占存儲器空間；空間復雜度指的就是程序執行過程中由於需要所申請的內存空間，即所「需」空間。所以答案的解析沒問題但答案給錯了。