a演算法的時間復雜度

Ⅰ 下列演算法，指出演算法A的功能和時間復雜度，其中h、g分別為單循環鏈表中兩個節點指針。

估計你的代碼是這樣的吧：
void B(int *s, int *q)
{
int *p;
p = s;
while（p->next != q)
p = p->next;
p->next = s;
}

void A(int *h, int *g)
{
B(h, g);
B(g, h);
}
首先說下函數B的作用，函數B的作用是將單循環鏈表（也可以是單向鏈表，如果是單鏈表，那麼s節點一定要在q節點之前，題意中指的是單循環鏈表）中的q節點和s節點相連接（q->next = s），從而形成一個單循環鏈表。
函數A的作用是使單循環鏈表中的g的下一個節點為h而h的下一個節點為g（即g->next = h且h->next = g），也可以說是形成一個只有g和h節點的單循環鏈表。

如果g,h所在單循環鏈表節點數為n，則當q->next == s時，"B(h, g);"要執行最多次" p = p->next;"（n-2次），執行p->next = s;一次；B(g, h);只執行p->next = s;一次。所以時間復雜度肯定是線性階，即T(n) = O(n)。

Ⅱ 演算法的時間復雜度是指什麼具體點

演算法復雜度不是簡單的時間的度量
是用來評價演算法優劣程度的依據
比如，一個程序要掃描100 * n * n + 10000 * n + 99999遍，那麼時間復雜度是O(n^2)
也就是說，時間復雜度只取次數最高的項，並且忽略系數

所以，時間復雜度是用來描述隨著 n 的增大，演算法耗時「增大」的！不是用來描述運行所花時間的（這個我們初中老師給我們強調了半天）

還有一點，O(9999999999)（實際應寫為O(1),這里只是表達意思）和O(n)的演算法那個好？
答案是O(9999999999)，因為他的耗時不隨n的增大而變化，所以他更優
一般來說，演算法的好壞是這樣的 （>表示好於) O(1) > O(logn) > O(n) > O(n logn) > O(n^2) > O(n^3) > O(2^n) > O(n!)

Ⅲ 演算法的時間復雜度定義

在進行演算法分析時，語句總的執行次數T(n)是關於問題規模n的函數，進而分析T(n)隨n的變化情況並確定T(n)的數量級。演算法的時間復雜度，也就是演算法的時間量度。記作：T(n)=O(f(n))。它表示隨問題n的增大，演算法執行時間的增長率和f(n)的增長率相同，稱作演算法的漸進時間復雜度，簡稱為時間復雜度。其中，f(n)是問題規模n的某個函數。
這樣用大寫O()來體現演算法時間復雜度的記法，我們稱之為大0記法。

Ⅳ 【演算法筆記】演算法的平均時間復雜度A(n)的公式及示例

演算法平均時間復雜度計算公式

其中:

舉例：檢索問題，數組 有 個元素，每個元素為從1到n的整數。若待檢索元素在 中（例如1,2,3,4,5），則比較次數為其本身。若待檢索元素位於 的空隙中（例如0.5,1.5,2.5），則比較次數為 ，也就是從頭到尾比較一遍。若位於 和位於 的空隙的待檢索元素數量各佔一半，檢索的平均時間復雜度是多少？

位於 的情況：假設 在 的概率為 ，則 在每個位置的概率為 ，若 的值為 ，則需要比較 次。平均時間復雜度為

位於 的空隙的情況： 不在 的概率為 ，每種情況都要比較 次，則該情況的平均時間復雜度為

綜上，結合等差數列求和公式有：

當 ，

Ⅳ 求最短路徑的A*演算法的時間復雜度與空間復雜度是多少

從數學上定義，給定演算法A，如果存在函數F(n)，當n=k時，F(k)表示演算法A在輸入規模為k的情況下的運行時間，則稱F(n)為演算法A的時間復雜度。這里首先要明確輸入規模的概念。關於輸入規模，不是很好下定義，非嚴格的講，輸入規模是指演算法A所接受輸入的自然獨立體的大小。例如，對於排序演算法來說，輸入規模一般就是待排序元素的個數，而對於求兩個同型方陣乘積的演算法，輸入規模可以看作是單個方陣的維數。為了簡單起見，總是假設演算法的輸入規模是用大於零的整數表示的，即n=1,2,3,……,k,…… 對於同一個演算法，每次執行的時間不僅取決於輸入規模，還取決於輸入的特性和具體的硬體環境在某次執行時的狀態。所以想要得到一個統一精確的F(n)是不可能的。為了解決這個問題，做以下兩個說明： 1.忽略硬體及環境因素，假設每次執行時硬體條件和環境條件是完全一致的。 2.對於輸入特性的差異，將從數學上進行精確分析並帶入函數解析式。

Ⅵ 請問演算法的時間復雜度是怎麼計算出來的

首先假設任意一個簡單運算的時間都是1，例如a=1;a++;a=a*b;這些運算的時間都是1.

那麼例如
for(int i=0;i<n;++i)
{
for(int j=0;j<m;++j)
a++; //注意，這里計算一次的時間是1.
}
那麼上面的這個例子的時間復雜度就是 m*n

再例如冒泡排序的時間復雜度是N*N；快排的時間復雜度是log(n)。

詳細的情況，建議你看《演算法導論》，裡面有一章節，具體講這個的。

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

就是對演算法執行時所花時間的度量。一般為問題規模的函數。

計算機科學中，演算法的時間復雜度是一個函數，它定量描述了該演算法的運行時間。這是一個關於代表演算法輸入值的字元串的長度的函數。時間復雜度常用大O符號表述，不包括這個函數的低階項和首項系數。使用這種方式時，時間復雜度可被稱為是漸近的，它考察當輸入值大小趨近無窮時的情況。

演算法復雜度分為時間復雜度和空間復雜度。其作用： 時間復雜度是指執行演算法所需要的計算工作量；而空間復雜度是指執行這個演算法所需要的內存空間。演算法的復雜性體現在運行該演算法時的計算機所需資源的多少上，計算機資源最重要的是時間和空間資源，因此復雜度分為時間和空間復雜度。

相關內容解釋：

函數在數學上的定義：給定一個非空的數集A,對A施加對應法則f,記作f（A）,得到另一數集B,也就是B=f（A）。那麼這個關系式就叫函數關系式,簡稱函數。

簡單來講，對於兩個變數x和y，如果每給定x的一個值，y都有唯一一個確定的值與其對應，那麼我們就說y是x的函數。其中，x叫做自變數，y叫做因變數。

Ⅷ (11) 演算法的時間復雜度是指______。 A. 執行演算法程序所需要的時間 B. 演算法程序的長度 C. 演算法執行過程中所

（11）[答案]C
[考點]數據結構與演算法
[評析]
演算法的復雜度分時間復雜度和空間復雜度。
時間復雜度：在運行演算法時所耗費的時間為f(n)(即 n的函數)。
空間復雜度：實現演算法所佔用的空間為g(n)（也為n的函數）。
稱O(f(n))和O(g(n))為該演算法的復雜度。
簡單的例子比如常見的順序結構時間復雜度為O(1),1層循環裡面次數為n，時間復雜度就是O(n),2層循環for i=1 to n,for j=1 to n演算法時間復雜度為O(n2)（裡面為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的三次方）

Ⅹ 演算法A時間復雜度比B高，但是實驗運行時間卻比B低，試研究可能的原因

如果是同一個N，跟其關系不大。
運行時間還和計算機有關，尤其是比較耗費時間的運算。如輸入輸出運算等。