1樓：
|#include
using namespace std;
int c(int n,int m)
int main()
{int n,m;
cin>>n>>m;
cout<間復
zhi雜度dao
應該就是o(c(n,m))，空間複雜度應該為o(n);
請問遞迴演算法的時間複雜度如何計算呢?
2樓：木子青耶
遞迴演算法的時間複雜度在演算法中，當一個演算法中包含遞迴呼叫時，其時間複雜度的分析會轉化為一個遞迴方程求解，常用以下四種方法：
代入法的基本步驟是先推測遞迴方程的顯式解，然後用數學歸納法來驗證該解是否合理。
迭代法的基本步驟是迭代地遞迴方程的右端，使之成為一個非遞迴的和式，然後通過對和式的估計來達到對方程左端即方程的解的估計。
這個方法針對形如「t(n) = at(n/b) + f(n)」的遞迴方程。這種遞迴方程是分治法的時間複雜性所滿足的遞迴關係。
即一個規模為n的問題被分成規模均為n/b的a個子問題，遞迴地求解這a個子問題，然後通過對這a個子間題的解的綜合，得到原問題的解。
可以將某些遞迴方程看成差分方程，通過解差分方程的方法來解遞迴方程，然後對解作出漸近階估計。
3樓：泡影果果
1、遞迴
是指對一個問題的求解，可以通過
同一問題的更簡單的形式的求解來表示. 並通過問題的簡單形式的解求出複雜形式的解. 遞迴是解決一類問題的重要方法.
遞迴程式設計是程式設計中常用的一種方法，它可以解決所有有遞迴屬性的問題，並且是行之有效的. 但對於遞迴程式執行的效率比較低，無論是時間還是空間都比非遞迴程式更費，若在程式中消除遞迴呼叫，則其執行時間可大為節省. 以下討論遞迴的時間效率分析方法，以及與非遞迴設計的時間效率的比較.
2、時間複雜度的概念及其計算方法
演算法是對特定問題求解步驟的一種描述. 對於演算法的優劣有其評價準則，主要在於評價演算法的時間效率，演算法的時間通過該演算法編寫的程式在計算機中執行的時間來衡量，所花費的時間與演算法的規模n有必然的聯絡，當問題的規模越來越大時，演算法所需時間量的上升趨勢就是要考慮的時間度量。
演算法的時間度量是依據演算法中最大語句頻度（指演算法中某條語句重複執行的次數）來估算的，它是問題規模n的某一個函式f(n). 演算法時間度量記作：t（n）=o（f（n）） 。
它表示隨問題規模n的增大，演算法執行時間的增長率和f（n）的增長率相同，稱作演算法的時間複雜度，簡稱時間複雜度[2]。
例如下列程式段：
（1）x=x+1;（2）for(i=1;i<=n;i++) x=x+1;（3）for(j=1;j<=n;j++) for(k=1;k<=n;k++) x=x+1. 以上三個程式段中，語句x=x+1的頻度分別為1，n，n2，則這三段程式的時間複雜度分別為o（1），o（n），o（n2）。
求解過程為：先給出問題規模n的函式的表示式，然後給出其時間複雜度t（n）。
但是在現實程式設計過程中，往往遇到的問題都是比較複雜的演算法，就不能很容易地寫出規模n的表示式，也比較難總結其時間複雜度. 遞迴函式就是屬於這種情況. 下面舉例說明遞迴函式的時間複雜度的分析方法。
c語言程式題：寫出遞迴與非遞迴兩種折半查詢程式，並分析其時間空間複雜度。
4樓：匿名使用者
折半查詢需要先對資料進行排序。
#include
using namespace std;
int bsearch(int data, const int x, int beg, int last)
while(beg <= last)
else if (data[mid] < x)
else if (data[mid] > x)
}return -1;
}int rbsearch(int data, const int x, int beg, int last)
else if (x < data[mid])
else if (x > data[mid])
}int main(void)
;//int num = 3;
int num=30;
cout << "the array is : " << endl;
int n = sizeof(data)/sizeof(int);
for (int i = 0; i < n; i++)
cout << endl;
int index = -1;
//index = bsearch(data,num,0,n);
index = rbsearch(data, num, 0,n);
cout << "index of " << num << " is " << index << endl;
system("pause");
return 0;
}以上是氣泡排序演算法的實現。
折半查詢演算法描述如下：
在有序表中，把待查詢資料值與查詢範圍的中間元素值進行比較，會有三種情況出現：
1） 待查詢資料值與中間元素值正好相等，則放回中間元素值的索引。
2） 待查詢資料值比中間元素值小，則以整個查詢範圍的前半部分作為新的查詢範圍，執行1），直到找到相等的值。
3） 待查詢資料值比中間元素值大，則以整個查詢範圍的後半部分作為新的查詢範圍，執行1），直到找到相等的值
4） 如果最後找不到相等的值，則返回錯誤提示資訊。
實現如下：
#include
using namespace std;
int bsearch(int data, const int x, int beg, int last)
while(beg <= last)
else if (data[mid] < x)
else if (data[mid] > x)
}return -1;
}int rbsearch(int data, const int x, int beg, int last)
else if (x < data[mid])
else if (x > data[mid])
return -1;
}int main(void)
;int num = 3;
cout << "the array is : " << endl;
int n = sizeof(data)/sizeof(int);
for (int i = 0; i < n; i++)
cout << endl;
int index = -1;
//inedx=bsearch(data,num,0,n);
index = rbsearch(data, num, 0,n);
cout << "index of " << num << " is " << index << endl;
system("pause");
return 0;
}複雜度分析：
折半查詢就像搜素二叉樹：中間值為二叉樹的根，前半部分為左子樹，後半部分為右子樹。折半查詢法的查詢次數正好為該值所在的層數。
等概率情況下，約為log2(n+1)-1，其演算法複雜度為o(log(n))。
遞迴演算法時間複雜度怎麼分析
5樓：斟酒自酌
直接在裡面加一個變數 比如說int a 再 每遞迴一次就 a++ 時間複雜度就可以用a的值表示 就是遞迴的次數
6樓：我的宿舍
1、遞迴
的求解，可以通過同一問題的更簡單的形式的求解來表示. 並通過問題的簡單形式的解求出複雜形式的解. 遞迴是解決一類問題的重要方法.
遞迴程式設計是程式設計中常用的一種方法，它可以解決所有有遞迴屬性的問題，並且是行之有效的. 但對於遞迴程式執行的效率比較低，無論是時間還是空間都比非遞迴程式更費，若在程式中消除遞迴呼叫，則其執行時間可大為節省. 以下討論遞迴的時間效率分析方法，以及與非遞迴設計的時間效率的比較.
2 時間複雜度的概念及其計算方法
演算法是對特定問題求解步驟的一種描述. 對於演算法的優劣有其評價準則，主要在於評價演算法的時間效率，演算法的時間通過該演算法編寫的程式在計算機中執行的時間來衡量，所花費的時間與演算法的規模n有必然的聯絡，當問題的規模越來越大時，演算法所需時間量的上升趨勢就是要考慮的時間度量.
演算法的時間度量是依據演算法中最大語句頻度（指演算法中某條語句重複執行的次數）來估算的，它是問題規模n的某一個函式f(n). 演算法時間度量記作：t（n）=o（f（n））
它表示隨問題規模n的增大，演算法執行時間的增長率和f（n）的增長率相同，稱作演算法的時間複雜度，簡稱時間複雜度[2].
例如下列程式段：
（1）x=x+1;（2）for(i=1;i<=n;i++) x=x+1;（3）for(j=1;j<=n;j++) for(k=1;k<=n;k++) x=x+1. 以上三個程式段中，語句x=x+1的頻度分別為1，n，n2，則這三段程式的時間複雜度分別為o（1），o（n），o（n2）.
求解過程為：先給出問題規模n的函式的表示式，然後給出其時間複雜度t（n）.
但是在現實程式設計過程中，往往遇到的問題都是比較複雜的演算法，就不能很容易地寫出規模n的表示式，也比較難總結其時間複雜度. 遞迴函式就是屬於這種情況. 下面舉例說明遞迴函式的時間複雜度的分析方法.
7樓：
《演算法導論》一書花了很大的篇幅去討論遞迴演算法時間複雜度的分析，在《演算法導論》裡叫做不變式的主定理。這個比較難，不是一兩天能學會的，多投入時間和精力去啃吧。
遞迴演算法和非遞迴演算法在分析時間複雜度和空間複雜度上為什麼不同
8樓：奔跑的窩牛的家
在演算法分析中，當一個演算法中包含遞迴呼叫時，其時間複雜度的分析會轉化為一個遞迴方程求解。實際上，這個問題是數學上求解漸近階的問題，而遞迴方程的形式多種多樣，其求解方法也是不一而足，比較常用的有以下四種方法：
(1)代入法(substitution method)
代入法的基本步驟是先推測遞迴方程的顯式解，然後用數學歸納法來驗證該解是否合理。
(2)迭代法(iteration method)
迭代法的基本步驟是迭代地遞迴方程的右端，使之成為一個非遞迴的和式，然後通過對和式的估計來達到對方程左端即方程的解的估計。
(3)套用公式法(master method)
這個方法針對形如「t(n) = at(n/b) + f(n)」的遞迴方程。這種遞迴方程是分治法的時間複雜性所滿足的遞迴關係，即一個規模為n的問題被分成規模均為n/b的a個子問題，遞迴地求解這a個子問題，然後通過對這a個子間題的解的綜合，得到原問題的解。
(4)差分方程法(difference formula method)
可以將某些遞迴方程看成差分方程，通過解差分方程的方法來解遞迴方程，然後對解作出漸近階估計。
下面就以上方法給出一些例子說明。
一、代入法
大整數乘法計算時間的遞迴方程為：t(n) = 4t(n/2) + o(n)，其中t(1) = o(1)，我們猜測一個解t(n) = o(n2 )，根據符號o的定義，對n>n0，有t(n) < **2 - eo(2n)（注意，這裡減去o(2n)，因其是低階項，不會影響到n足夠大時的漸近性），把這個解代入遞迴方程，得到：
t(n) = 4t(n/2) + o(n)
≤ 4c(n/2)2 - eo(2n/2)) + o(n)
= **2 - eo(n) + o(n)
≤ **2
其中，c為正常數，e取1，上式符合 t(n)≤**2 的定義，則可認為o(n2 )是t(n)的一個解，再用數學歸納法加以證明。
二、迭代法
某演算法的計算時間為：t(n) = 3t(n/4) + o(n)，其中t(1) = o(1)，迭代兩次可將右端為：
t(n) = 3t(n/4) + o(n)
= o(n) + 3( o(n/4) + 3t(n/42 ) )
= o(n) + 3( o(n/4) + 3( o(n/42 ) + 3t(n/43 ) ) )
從上式可以看出，這是一個遞迴方程，我們可以寫出迭代i次後的方程：
t(n) = o(n) + 3( o(n/4) + 3( o(n/42 ) + ... + 3( n/4i + 3t(n/4i+1 ) ) ) )
當n/4i+1 =1時，t(n/4i+1 )=1，則
t(n) = n + (3/4) + (32 /42 )n + ... + (3i /4i )n + (3i+1 )t(1)
< 4n + 3i+1
而由n/4i+1 =1可知，i0，有f(n) = o(nlogb a-ε )，則t(n) = o(nlogb a )
2.若f(n) = o(nlogb a )，則t(n) = o(nlogb a *logn)
3.若f(n) = o(nlogb a+ε )，且對於某常數c>1和所有充分大的正整數n，有af(n/b)≤cf(n)，則t(n)=o(f(n))。
設t(n) = 4t(n/2) + n，則a = 4，b = 2，f(n) = n，計算得出nlogb a = nlog2 4 = n2 ，而f(n) = n = o(n2-ε )，此時ε= 1，根據第1種情況，我們得到t(n) = o(n2 )。
這裡涉及的三類情況，都是拿f(n)與nlogb a 作比較，而遞迴方程解的漸近階由這兩個函式中的較大者決定。在第一類情況下，函式nlogb a 較大，則t(n)=o(nlogb a )；在第三類情況下，函式f(n)較大，則t(n)=o(f (n))；在第二類情況下，兩個函式一樣大，則t(n)=o(nlogb a *logn)，即以n的對數作為因子乘上f(n)與t(n)的同階。
但上述三類情況並沒有覆蓋所有可能的f(n)。在第一類情況和第二類情況之間有一個間隙：f(n)小於但不是多項式地小於nlogb a ，第二類與第三類之間也存在這種情況，此時公式法不適用。
在先序 中序非遞迴演算法中為什麼使用棧？能不能借助其它資料結構來實現？vc
因為先序和中序遍歷需要多次經過結點,但不會訪問,用非遞迴演算法需要記錄所經過的路徑,這樣便於返回.用什麼結構倒不是關鍵的，主要的是你要保證儲存它的資料結構的存取順序，先進的後出。include using namespace std include include include define ma...
pascal遞迴函式計算ackerman函式值
兩個問題 1 integer太小了，資料早就爆了 2 棧的呼叫過頭了，exitcode 201 的意思就是棧溢位。事實上，阿克曼函式的值是極大的。ackermann 0,n n 1 ackermann 1,n n 2 ackermann 2,n 2 n 3 ackermann 3,n 2 n 3 3...
整數乘法的計演算法則整數乘法的計演算法
整數乘法法則是整數的運演算法則之一，整數的乘法法則分三種情形表述 1 一位數的乘法法則 兩個一位數相乘，可根據乘法定義用加法計算，通常可利用乘法表直接得出任意兩個一位數的積。2 多位數的乘法法則 依次用乘數的各個數位上的數，分別去乘被乘數的每一數位上的數，然後將乘得的積加起來。擴充套件資料 一 單項...