演算法執行所需操作時間

1. 演算法的時間復雜度是指什麼

演算法的時間復雜度是指：執行程序所需的時間。

一般情況下，演算法中基本操作重復執行的次數是問題規模n的某個函數，用T(n)表示，若有某個輔助函數f(n)，使得當n趨近無窮大時。

T(n)/f(n)的極限值為不等於零的常數，則稱為f(n)是T(n)的同數量級函數。記作T(n)=O(f(n))，稱O(f(n))為演算法的漸進時間復雜度，簡稱時間復雜度。比如：

在 T(n)=4nn-2n+2 中，就有f(n)=nn，使得T(n)/f(n)的極限值為4，那麼O(f(n))，也就是時間復雜度為O(n*n)。

時間復雜度中大O階推導是：

推導大O階就是將演算法的所有步驟轉換為代數項，然後排除不會對問題的整體復雜度產生較大影響的較低階常數和系數。

有條理的說，推導大O階，按照下面的三個規則來推導，得到的結果就是大O表示法：運行時間中所有的加減法常數用常數1代替。只保留最高階項去除最高項常數。

其他常見復雜度是：

f(n)=nlogn時，時間復雜度為O(nlogn)，可以稱為nlogn階。

f(n)=n³時，時間復雜度為O(n³)，可以稱為立方階。

f(n)=2ⁿ時，時間復雜度為O(2ⁿ)，可以稱為指數階。

f(n)=n!時，時間復雜度為O(n!)，可以稱為階乘階。

f(n)=(√n時，時間復雜度為O(√n)，可以稱為平方根階。

2. C語言演算法的時間復雜度如何計算啊

看看這個
每個循環都和上一層循環的參數有關。
所以要用地推公式：
設i(n)表示第一層循環的i為n時的循環次數，注意到他的下一層循環次數剛好就是n，分別是0,1,2...n-1
所以，把每一層循環設一個函數分別為：j(n),k(n),t(n)
則有
i(n)=j(0)+...+j(n-1)
j(n)=k(0)+...+k(n-1)
k(n)=t(0)+...+t(n-1)
i(0)=j(0)=k(0)=0
t(n)=1
而總循環數是i(0)+i(1)...+i(n-1)
可以根據遞推條件得出准確值
所以演算法復雜度是O(i(0)+i(1)...+i(n-1))
記得採納啊

3. 影響演算法執行時間的因素主要有哪些

影響演算法執行時間的因素包括：

1、演算法本身選用的策略；

2、問題的規模；

3、書寫程序的語言；

4、編譯產生的機器代碼質量；

5、機器執行指令的速度等。

為便於比較演算法本身的優劣，應排除其它影響演算法效率的因素。從演算法中選取一種對於所研究的問題來說是基本操作的原操作，以該基本操作重復執行的次數作為演算法的時間量。

(3)演算法執行所需操作時間擴展閱讀：

縮短演算法時間的方法：

1、選擇合理的存儲結構。

數據的存儲結構，分為順序存儲結構和鏈式存儲結構。順序存儲結構的特點是藉助元素在存儲器中的相對位置來表示數據元素之間的邏輯關系；鏈式存儲結構則是藉助指示元素存儲地址的指針表示數據元素之間的邏輯關系。

2、使用直接初始化。

與直接初始化對應的是復制初始化。

3、減少除法運算的使用。

無論是整數還是浮點數運算，除法都是一件運算速度很慢的指令，在計算機中實現除法是比較復雜的。所以要減少除法運算的次數。

4. 演算法執行時間是指執行一次基本操作所需的時間嗎

演算法的執行時間僅僅指程序在進行該演算法相關計算時所用的時間之和，一般不用演算法執行時間描述演算法的好壞，因為演算法的執行時間取決於數據的大小和數量，一般要用時間復雜度來描述一個演算法。

5. 一個演算法的運行時所消耗的時間是如何測出來的

在忽略機器性能的基礎上我們用演算法時間復雜度來計算演算法執行的時間
1.時間頻度
一個演算法執行所耗費的時間，從理論上是不能算出來的，必須上機運行測試才能知道。但我們不可能也沒有必要對每個演算法都上機測試，只需知道哪個演算法花費的時間多，哪個演算法花費的時間少就可以了。並且一個演算法花費的時間與演算法中語句的執行次數成正比例，哪個演算法中語句執行次數多，它花費時間就多。一個演算法中的語句執行次數稱為語句頻度或時間頻度。記為T(n)。
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.分類
按數量級遞增排列，常見的時間復雜度有： 常數階O(1),對數階O(log2n),線性階O(n), 線性對數階O(nlog2n),平方階O(n2)，立方階O(n3),...， k次方階O(nk), 指數階O(2n) 。隨著問題規模n的不斷增大，上述時間復雜度不斷增大，演算法的執行效率越低。

6. C語言怎樣統計一個演算法執行的CPU時間

C/C++中的計時函數是clock()，而與其相關的數據類型是clock_t。在MSDN中，查得對clock函數定義如下：

clock_t clock( void );

這個函數返回從「開啟這個程序進程」到「程序中調用clock()函數」時之間的CPU時鍾計時單元（clock tick）數，在MSDN中稱之為掛鍾時間（wal-clock）。其中clock_t是用來保存時間的數據類型，在time.h文件中，我們可以找到對它的定義：

#ifndef _CLOCK_T_DEFINED
typedef long clock_t;
#define _CLOCK_T_DEFINED
#endif

很明顯，clock_t是一個長整形數。在time.h文件中，還定義了一個常量CLOCKS_PER_SEC，它用來表示一秒鍾會有多少個時鍾計時單元，其定義如下：

#define CLOCKS_PER_SEC ((clock_t)1000)

可以看到每過千分之一秒（1毫秒），調用clock（）函數返回的值就加1。下面舉個例子，你可以使用公式clock()/CLOCKS_PER_SEC來計算一個進程自身的運行時間：

void elapsed_time()
{
printf("Elapsed time:%u secs.\n",clock()/CLOCKS_PER_SEC);
}

當然，你也可以用clock函數來計算你的機器運行一個循環或者處理其它事件到底花了多少時間：

#include 「stdio.h」
#include 「stdlib.h」
#include 「time.h」

int main( void )
{
long i = 10000000L;
clock_t start, finish;
double ration;
/* 測量一個事件持續的時間*/
printf( "Time to do %ld empty loops is ", i );
start = clock();
while( i-- ) ;
finish = clock();
ration = (double)(finish - start) / CLOCKS_PER_SEC;
printf( "%f seconds\n", ration );
system("pause");
}

在筆者的機器上，運行結果如下：

Time to do 10000000 empty loops is 0.03000 seconds

上面我們看到時鍾計時單元的長度為1毫秒，那麼計時的精度也為1毫秒，那麼我們可不可以通過改變CLOCKS_PER_SEC的定義，通過把它定義的大一些，從而使計時精度更高呢？通過嘗試，你會發現這樣是不行的。在標准C/C++中，最小的計時單位是一毫秒。

7. 計算機執行一條指令需要多長時間如何計算

計算機中時鍾周期是（主頻的倒數），一個時鍾周期cpu僅完成一個最基本的動作，完成一個基本操作的時間為機器周期，一般由幾個時鍾周期組成；完成一條指令為指令周期。一般由幾個機器周期組成，指令不同機器周期數也不同。
以我的本本1.6G 為例 ，機器周期由兩個時鍾周期組成，平均三個機器周期完成一條指令（這要假設，我看不到）
時鍾周期為1/(1.6*1024m)=0.61ns 機器周期為0.61*2=1.22ns
平均指令周期3*1.22ns=3.66ns
平均指令執行速度為1/(3.66ns)=273.22MIPS(百萬條指令每秒）
這只是計算方法，條件也是假設的，晶振我不知。
大致演算法就這樣，我數學不好。如有算錯請多指教！