1樓：聽不清啊
這時間複雜來度就是o(n)。自
這只是用來初學遞迴時用來幫
bai助理解用的。一du般使用時，zhi能用迴圈解決的dao就不用遞迴。
只要用一個迴圈就可以了的。
long fun(int n)
給出下面幾個c語言程式段的時間複雜度。要求寫出計算過程 ，謝謝了，**等。
2樓：匿名使用者
1、主要操作是i = i * 5和i<=n，設迴圈次數為x，則5^x <= n，因此x <= log5(n)，其中5是底數，因此時間複雜度為o(log5(n))。
2、主要操作在while迴圈中，設迴圈執行次數為x，則x^2<= n，x <= sqrt(n)，因此時間複雜度為o(sqrt(n))。
3、主要是看內迴圈執行的次數，當i=1時，內迴圈執行n-3次i=2時，內迴圈執行n-6次，所以總的執行次數是(n-3*1)+(n-3*2)+(n-3*3)+...+(n-3*n/3)。總的項數為n/3，因此總次數為n*(n/3)-3*(1+2+...
+n/3)=(n^2 - 3n)/6。因此時間複雜度為o(n^2)
3樓：匿名使用者
求時間複雜度只需找出執行次數最多的那條語句。
對於第一個，設執行次數為k,則i最終等於k^5=n; 解出k即可；
對於第二個，設執行次數為k，則最終有k^2=n;解出k；
對於第三個，if語句執行n/3次，單獨看裡面的for執行（n-n/3）次，結合if語句，則最終有
（n-n/3）*n/3 ，時間複雜度一眼便知
下面程式段的時間複雜度是 ？ i=1； while（i<=n） i=i*2
4樓：仁昌居士
i=1； while（i<=n） i=i*2的時間複雜度copyo(log2n)。
整段**語句，中迴圈體只有一個while（i<=n），執行的次數是：
i = 1，i = 1*2=2，判斷2是否小於等於n，是則繼續迴圈，否則跳出迴圈。
i =2，i = 2*2=4，判斷4是否小於等於n，是則繼續迴圈，否則跳出迴圈。
i =4 ，i = 4*2=8，判斷8是否小於等於n，是則繼續迴圈，否則跳出迴圈。
根據規律發現，迴圈次數由log2n決定，所以複雜度是o(log2n)。
5樓：匿名使用者
假設迴圈次數是x。
i = 1, 2, 4, 8, 16 ，i = 2^x條件是i <= n
2^x <= n
所以x <= log2n 一共執行迴圈體log2n次，所以複雜度是o(log2n)
6樓：匿名使用者
迴圈退出的條件為i > n
設第k次迴圈後退出迴圈
於是2^k > n
因此k > log2n 以2為底的對數，k的實際值為log2n上取整
因此時間複雜度為o(log2n)
下面一段程式的時間複雜度的過程： fact(int n) { if(n<=1) return(1); else return(n*fact(n-1)); }
7樓：匿名使用者
對於複函式fib，時間複雜度制 t(n)=1+t(n-1)，故為 θ(n)。
對於函bai數**m，你這裡n>m，呼叫了dufib(n),fib(m),fib(n-m)，外加一次除法zhi和一次乘法
dao運算，故其時間複雜度為 o(n)。
階乘的英文是factorial。
8樓：匿名使用者
應該是用遞迴寫的求數的階乘
分析下面程式段執行的時間複雜度o（n）
9樓：折柳成萌
常見的 查詢演算法的時間複雜度：
線性結構的查詢的時間複雜度，如 二分查詢（用於已經排好序的資料，如已序的陣列）；o(n)
非線性結構的查詢的時間複雜度，如 二叉查詢樹 ；o（log n）
排序類別 時間複雜度 空間複雜度 穩定
1 插入排序 o(n2) o(1) √
2 希爾排序 o(n2) o(1) × //shell（希爾）排序是基於插入排序的，時間效率比插入、選擇、冒泡高，但又比快速排序低點；
3 氣泡排序 o(n2) o(1) √
4 選擇排序 o(n2) o(1) ×
5 快速排序 o(nlogn) o(logn) ×
6 堆排序 o(nlogn) o(1) ×
7 歸併排序 o(nlogn) o(n) √
氣泡排序、插入排序、歸併排序是穩定的，演算法時間複雜度是o(n ^2)；
選擇排序、快速排序、堆排序、希爾排序都是 不穩定的；
演算法的時間複雜度
一、 時間複雜度定義
定義：如果一個問題的規模是n，解這一問題的某一演算法所需要的時間為t(n)，它是n的某一函式t(n)稱為這一演算法的「時間複雜性」。
當輸入量n逐漸加大時，時間複雜性的極限情形稱為演算法的「漸近時間複雜性」。
二、大o表示法
我們常用大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)
程式中的時間複雜度是怎麼計算的？
10樓：匿名使用者
演算法複雜度的介紹，見百科：
演算法的時間複雜度為n3n2log2n14n
結果為 o n 解題過程如下 結果第一項是n，第2項是log2n，第3項是1 n，當n趨於無窮大時，第二項比第一項小，第3項為0 所以 n3 n2log2n 14n n2，其數量級表示為o n 時間複雜度計算方法 一般情況下，演算法中基本操作重複執行的次數是問題規模n的某個函式，用t n 表示，若有...
求解關於DFS,BFS的演算法時間複雜度分析
記住就行了,dfs bfs時間複雜度對於採用臨接矩陣儲存時是o n 對於採用臨接表時是o n e 如何分析回溯 dfs時間複雜度 因為是選擇其中一個方向不斷前進,直接遇到某條件後才返回到上一次的起點重新嘗試另一條路徑。如果是廣度優先,那麼應該是同時向多個方向進發。圖採用鄰接矩陣和鄰接連結串列表示時,...
快速排序的時間複雜度，快速排序法的平均時間複雜度是多少？
1.快速排序 時空複雜度 快速排序每次將待排序陣列分為兩個部分，在理想狀況下，每一次都將待排序陣列劃分成等長兩個部分，則需要logn次劃分。而在最壞情況下，即陣列已經有序或大致有序的情況下，每次劃分只能減少一個元素，快速排序將不幸退化為氣泡排序，所以快速排序時間複雜度下界為o nlogn 最壞情況為...