程序運行的時間復雜度怎麼算

⑴ 程序中的時間復雜度是怎麼計算的

演算法復雜度的介紹，見網路：
http://ke..com/view/7527.htm

時間復雜度
時間頻度
一個演算法執行所耗費的時間，從理論上是不能算出來的，必須上機運行測試才能知道。但我們不可能也沒有必要對每個演算法都上機測試，只需知道哪個演算法花費的時間多，哪個演算法花費的時間少就可以了。並且一個演算法花費的時間與演算法中語句的執行次數成正比例，哪個演算法中語句執行次數多，它花費時間就多。一個演算法中的語句執行次數稱為語句頻度或時間頻度。記為T(n)。

計算方法
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） 註：n^3即是n的3次方。
3.在pascal中比較容易理解，容易計算的方法是：看看有幾重for循環，只有一重則時間復雜度為O（n）,二重則為O（n^2），依此類推，如果有二分則為O(logn)，二分例如快速冪、二分查找，如果一個for循環套一個二分，那麼時間復雜度則為O(nlogn)。

分類
按數量級遞增排列，常見的時間復雜度有：
常數階O(1),對數階O(log2n),線性階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都表示的問題規模。

以下來自網路知道：

對於這些演算法
(1) for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
s++;

(2) for(i=1;i<=n;i++)
for(j=i;j<=n;j++)
s++;

(3) for(i=1;i<=n;i++)
for(j=1;j<=i;j++)
s++;

(4) i=1;k=0;
while(i<=n-1){
k+=10*i;
i++;
}

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

對應的時間復雜度為：

1.時間復雜度O(n^2)
2.時間復雜度O(n^2)
3.時間復雜度O(n^2)
4.時間復雜度O(n)
5.時間復雜度O(n^3)

一般來說，時間復雜度是總運算次數表達式中受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)依此類推

那麼，總運算次數又是如何計算出的呢？
一般來說，我們經常使用for循環，就像剛才五個題，我們就以它們為例
1.循環了n*n次，當然是O(n^2)
2.循環了(n+n-1+n-2+...+1)≈(n^2)/2，因為時間復雜度是不考慮系數的，所以也是O(n^2)
3.循環了(1+2+3+...+n)≈(n^2)/2,當然也是O(n^2)
4.循環了n-1≈n次，所以是O(n)
5.循環了(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),忽略掉系數，二者當然是等價的

⑵ 究竟什麼是時間復雜度，怎麼求時間復雜度，看這一篇就夠了

時間復雜度就是用來方便開發者估算出程序的運行時間

我們該如何估計程序運行時間呢，我們通常會估計演算法的操作單元數量，來代表程序消耗的時間， 這里我們默認CPU的每個單元運行消耗的時間都是相同的。

假設演算法的問題規模為n，那麼操作單元數量便用函數f(n)來表示

隨著數據規模n的增大，演算法執行時間的增長率和f(n)的增長率相同，這稱作為演算法的漸近時間復雜度，簡稱時間復雜度，記為 O(f(n))

這里就要說一下這個大O，什麼是大O呢，很多同學說時間復雜度的時候都知道O(n)，O(n^2)，但說不清什麼是大O

演算法導論給出的解釋： 大O用來表示上界的 ，當用它作為演算法的最壞情況運行時間的上界，就是對任意數據輸入的運行時間的上界。

同樣演算法導論給出了例子：拿插入排序來說，插入排序的時間復雜度我們都說是O(n^2)

但是在數據本來有序的情況下時間復雜度是O(n)，也就對於所有輸入情況來說，最壞是O(n^2) 的時間復雜度，所以稱插入排序的時間復雜度為O(n^2)

同樣的同理我們在看一下快速排序，都知道快速排序是O(nlogn)，但是當數據已經有序情況下，快速排序的時間復雜度是O(n^2) 的，嚴格從大O的定義來講，快速排序的時間復雜度應該是O(n^2)

但是我們依然說快速排序是O(nlogn)的時間復雜度，這個就是業內的一個默認規定，我們這里說的O 代表的就是一般情況，不是嚴格的上界

所以這里大家知道這么一回事就好了

面試中面試官絕對不會針對快速排序的時間復雜度問題來討論O的定義， 大家知道討論的時間復雜度就是指一般情況下的時間復雜度就好了。

大家要對演算法的時間復雜度有這樣的一個概念

就是同一個演算法的時間復雜度不是一成不變的，和輸入的數據形式依然有關系

我們主要關心的還是一般情況下的數據形式 。

面試中說道演算法的時間復雜度是多少指的都是一般情況

但是如果面試官和我們深入探討一個演算法的實現以及性能的時候 我們就要時刻想著 數據用例的不一樣 時間復雜度也是不同的，這一點同學們要注意

這個圖中我們可以看出 不同演算法的時間復雜度 在不同數據輸入規模下的差異 。

我們在決定使用那些演算法的時候 ，不是時間復雜越低的越好，要考慮數據規模，如果數據規模很小 甚至可以用O(n^2)的演算法比 O(n)的更合適

就像上圖中圖中 O(5n^2) 和 O(100n) 在n為20之前 很明顯 O(5n^2)是更優的，所花費的時間也是最少的。

那我們為什麼在計算時間復雜度的時候要忽略常數項系數呢，也就說O(100n) 就是O(n)的時間復雜度，O(5n^2) 就是O(n^2)的時間復雜度

而且要默認O(n) 優於O(n^2) 呢 ？

這里就又涉及到大O的定義

因為 大O其實就是數據量級突破一個點且數據量級非常大的情況下所表現出的時間復雜度 ，這個點也就是 常數項系數已經不起決定性作用的點。

例如上圖中 20 就是那個點 ，n只要大於20 常數項系數已經不起決定性作用了。

所以我們說的時間復雜度都是省略常數項系數的，是因為一般情況下我們都是默認數據規模足夠的大，基於這樣的事實 我們給出的演算法時間復雜的的一個排行如下所示：

O(1)常數階 < O(logn)對數階 < O(n)線性階 < O(n^2)平方階 < O(n^3)(立方階) < O(2^n) (指數階)

我們平時說這個 演算法的時間復雜度是logn的，一定是log 以2為底n的對數么？

其實不然，也可以是以10為底n的對數，也可以是以20為底n的對數，但我們統一說 logn，也就是忽略底數的描述。

為什麼可以這么做呢？

如下圖所示

假如我們有兩個演算法的時間復雜度 分別是log以2為底n的對數 和 log 以10為底n的對數

那麼這里如果大家還記得我們高中數學的話， 應該不能理解 以2為底n的對數 = 以2為底10的對數 乘以 以10為底n的對數

那這里以2為底10的對數 是一個常數，而我在上面已經講述了我們計算時間復雜度是忽略常數項系數的

抽象一下 log 以i為底n的對數 等於 log 以j為底n的對數，所以我們忽略了i，直接說是logn，正式因為logij 是就一個常數

所以，這樣就應該不難理解了 我們為什麼忽略底數了

有時候，我們去計算時間復雜度的時候 發現不是一個 簡單的O(n) 或者O(n^2)， 而是一個復雜的表達式，例如：

O(2*n^2 + 10*n + 1000)

那這里我們通常如何描述這個演算法的時間復雜度呢，一種方法就是簡化法

去掉運行時間中的加法常數項 （因為常數項並不會因為n的增大而增加計算機的操作次數）

O(2*n^2 + 10*n)

去掉常數系數 （我們剛剛已經詳細講過為什麼可以去掉常數項的原因了）

O(n^2 + n)

只保留保留最高項 去掉數量級小一級的n （因為n^2 的數據規模遠大於 n），最終簡化為：

O(n^2)

如果這一步同學們理解有困難，那也可以做提取n的操作，變成 O(n(n+1)) ，省略加法常數項後 也別變成了

O(n^2)

所以最後我們說：我們這個演算法的演算法時間復雜度是 O(n^2)

也可以用另一種簡化的思路，當n大於40的時候 ， 這個復雜度 會一直小於 O(3*n^2)

O(2*n^2 + 10*n + 1000) < O(3*n^2)

所以說 最後我們省略掉常數項系數最終時間復雜度也是 O(n^2)

我們通過一道題目，來看一下具體時間復雜度應該怎麼算

題目描述：找出n個字元串中相同的兩個字元串（假設這里只有兩個相同的字元串）

一些同學可能以為解決這道題目可以採用枚舉遍歷的解法，時間復雜度是 O(n^2)

這個時間復雜度其實是不對的。

這里 一些同學忽略了字元串比較的時間消耗，這里並不像int 型數字做比較那麼簡單

除了n^2 次的遍歷次數外， 字元串比較依然要消耗m次操作（m也就是字母串的長度），所以時間復雜度是 O(m*n*n)

那麼我們再想一下其他解題思路

我們先排對n個字元串按字典序來排序，排序後n個字元串就是有序的，意味著兩個相同的字元串就是挨在一起

然後在遍歷一遍n個字元串，這樣就找到兩個相同的字元串了

那我們來看看這種演算法的時間復雜度

快速排序時間復雜度 為O(nlogn)，依然要考慮字元串的長度是m，那麼快速排序每次的比較都要有m次的字元比較的操作，就是 O(m*n*logn)

之後我們還要遍歷一遍這n個字元串找出兩個相同的字元串，別忘了遍歷的時候依然要比較字元串，所以總共的時間復雜度是 O(m*n*logn + n*m)

我們對 O(m*n*logn + n*m) 進行簡化操作，把 m*n 提取出來變成 O(m*n*(logn + 1)) ，

在省略常數項最後的時間復雜度是 O(m*n*logn) ， 那我們比較一下時間效率 O(m*n*logn) 是不是比第一種方法 O(m*n*n) 更快一些呢

很明顯 O(m*n*logn) 要優於 O(m*n*n)

所以 先把字元串集合排序在遍歷一遍找到兩個相同字元串的方式要比直接暴力枚舉的方式更快 。

通過這個例子 希望大家對時間復雜的是怎麼算的有一個初步的理解和認識。

⑶ 時間復雜度怎麼算

簡單理解，時間復雜度就是執行語句被調用了多少次。 (1)如果只調用了一次，如： x=5; if(x<-4) {x=x+4;} else {x=x+3;} 在大括弧中的內容，只會調用一個語句，那麼O(n)=1; (2)如果調用了兩次，如： x=5; if(x<-4) {x=x+4;} else {x=x+3;} x=x+56; 在大括弧中的內容，只會調用一個語句，但是在最後，還有一個計算公式要調用語句；總共加起來就是調用2次。那麼O(n)=2; （3）用1個FOR循環調用 for(x=0;x

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

（1）時間頻度 一個演算法執行所耗費的時間，從理論上是不能算出來的，必須上機運行測試才能知道。但我們不可能也沒有必要對每個演算法都上機測試，只需知道哪個演算法花費的時間多，哪個演算法花費的時間少就可以了。並且一個演算法花費的時間與演算法中語句的執行次數成正比例，哪個演算法中語句執行次數多，它花費時間就多。一個演算法中的語句執行次數稱為語句頻度或時間頻度。記為T(n)。 （2）時間復雜度 在剛才提到的時間頻度中，n稱為問題的規模，當n不斷變化時，時間頻度T(n)也會不斷變化。但有時我們想知道它變化時呈現什麼規律。為此，我們引入時間復雜度概念。 一般情況下，演算法中基本操作重復執行的次數是問題規模n的某個函數，用T(n)表示，若有某個輔助函數f(n),使得當n趨近於無窮大時，T（n)/f(n)的極限值為不等於零的常數，則稱f(n)是T(n)的同數量級函數。記作T(n)=Ｏ(f(n)),稱Ｏ(f(n)) 為演算法的漸進時間復雜度，簡稱時間復雜度。 在各種不同演算法中，若演算法中語句執行次數為一個常數，則時間復雜度為O(1),另外，在時間頻度不相同時，時間復雜度有可能相同，如T(n)=n2+3n+4與T(n)=4n2+2n+1它們的頻度不同，但時間復雜度相同，都為O(n2)。 按數量級遞增排列，常見的時間復雜度有： 常數階O(1),對數階O(log(2)n),線性階O(n), 線性對數階O(nlog(2)n),平方階O(n^2)，立方階O(n^3),...， k次方階O(n^k),指數階O(2^n)。隨著問題規模n的不斷增大，上述時間復雜度不斷增大，演算法的執行效率越低。

⑸ 如何計算時間復雜度

如何計算時間復雜度

定義：如果一個問題的規模是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的值非常小，因為，在 這個問題中增加一個元素就導致運行時間加倍。不幸的是，確實有許多問題 (如著名 的「巡迴售貨員問題」 )，到目前為止找到的演算法都是指數的。如果我們真的遇到這種情況， 通常應該用尋找近似最佳結果的演算法替代之。

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

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

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

⑺ 時間復雜度計算公式

時間復雜度計算公式如下

method1(){
System.out.println("祝你看了這篇文章"); //執行1次 System.out.println("諸事順利"); //執行1次 System.out.println("萬事如意"); //執行1次}// 1+1+1 = 3
method2()

for(int i=0;i<5;i++){ //i=0 執行1次；i<5 判斷5+1次,等於5時判斷後退出；i++ 執行5次 System.out.println("點贊發財!"); //執行5次 }} //1+(5+1)+5+5 = 17
method3(int n)

for(int i=0;i<n;i++){ //i=0 執行1次；i<n 執行n+1次；i++ 執行n次 System.out.println("點贊好運!"); //執行n次，你會有n次好運哦 }} //1+(n+1)+n+n = 3n+2

大O表示法

上面的時間復雜度的表示還是較復雜，我們一般都使用大O表示法來簡化表示時間復雜度。

1、復雜度為常數，如23，9999，等等 都表示為O(1)

2、復雜度包含n時，省略系數與常數項，只取n的最高階項

如：2n+45 為 O(n) ； 4n^3+6n^2+n 為O(n^3)

3、復雜度為對數時：如log5(n)、log2(n) 等等 都表示為 O(logn)

4、省略低階，只取高階 (即取最大的)

如：logn+nlogn 表示為O(nlogn)

⑻ 時間復雜度計算

演算法中基本操作重復執行的次數是問題規模n的某個函數，用T(n)表示，若有某個輔助函數f(n)，使得當n趨近於無窮大時，T(n)/f(n)的極限值為不等於零的常數，則稱f(n)是T(n)的同數量級函數。記作T(n)=O(f(n))，稱O(f(n))為演算法的漸進時間復雜度(O是數量級的符號 )，簡稱時間復雜度。
計算步驟可以分解為：

只有可運行的語句才會增加時間復雜度，因此，上面方法里的內容除了循環之外，其餘的可運行語句的復雜度都是O(1)。
時間復雜度 = for的O(n)+O(1) = 忽略常量 = O(n)。

設while循環裡面的頻度為t，2^t(2的t次方)<=n; 兩邊去對數t<=log2n，考慮最壞情況，取最大值t=log2n。
T(n) = O(log2n)。
排序演算法的復雜度可以參見 排序演算法 。

⑼ 在一個具體的程序中，程序的復雜度是如何計算的

演算法的復雜性

演算法的復雜性是演算法效率的度量，是評價演算法優劣的重要依據。一個演算法的復雜性的高低體現在運行該演算法所需要的計算機資源的多少上面，所需的資源越多，我們就說該演算法的復雜性越高；反之，所需的資源越低，則該演算法的復雜性越低。

計算機的資源，最重要的是時間和空間（即存儲器）資源。因而，演算法的復雜性有時間復雜性和空間復雜性之分。

不言而喻，對於任意給定的問題，設計出復雜性盡可能低的演算法是我們在設計演算法時追求的一個重要目標；另一方面，當給定的問題已有多種演算法時，選擇其中復雜性最低者，是我們在選用演算法適應遵循的一個重要准則。因此，演算法的復雜性分析對演算法的設計或選用有著重要的指導意義和實用價值。

簡言之，在演算法學習過程中，我們必須首先學會對演算法的分析，以確定或判斷演算法的優劣。

1.時間復雜性：
例1：設一程序段如下（為討論方便，每行前加一行號）
(1) for i:=1 to n do
(2) for j:=1 to n do
(3) x:=x+1
......
試問在程序運行中各步執行的次數各為多少？
解答：
行號 次數(頻度)
(1) n+1
(2) n*(n+1)
(3) n*n
可見，這段程序總的執行次數是：f(n)=2n2+2n+1。在這里，n可以表示問題的規模，當n趨向無窮大時，如果 f(n)的值很小，則演算法優。作為初學者，我們可以用f(n)的數量級O來粗略地判斷演算法的時間復雜性，如上例中的時間復雜性可粗略地表示為T(n)=O(n2)。

2.空間復雜性:

例2:將一一維數組的數據(n個)逆序存放到原數組中,下面是實現該問題的兩種演算法:

演算法1:for i:=1 to n do

b[i]:=a[n-i+1];

for i:=1 to n do

a[i]:=b[i];

演算法2:for i:=1 to n div 2 do

begin

t:=a[i];a[i]:=a[n-i-1];a[n-i-1]:=t

end;

演算法1的時間復雜度為2n,空間復雜度為2n

演算法2的時間復雜度為3*n/2,空間復雜度為n+1

顯然演算法2比演算法1優，這兩種演算法的空間復雜度可粗略地表示為S(n)=O(n)

信息學比賽中，經常是：只要不超過內存，盡可能用空間換時間。

⑽ 演算法的時間復雜度如何計算

關於時間復雜度的計算是按照運算次數來進行的，比如1題：
Sum1(
int
n
)
{
int
p=1,
sum=0,
m
;
//1次
for
(m=1;
m<=n;
m++)
//n+1次
{
p*=m
;
//n次
sum+=p
;
}
//n次
return
(sum)
;
//1次
}
最後總的次數為
1+（n+1）+n+n+1+1=3n+3
所以時間復雜度f（o）=n；（時間復雜度只管n的最高次方，不管他的系數和表達式中的常量）
其餘的一樣，不明白的可以來問我