首頁 > 產(chǎn)品 > 經(jīng)驗 > 遞歸的時間復(fù)雜度，二分法的遞歸算法的時間復(fù)雜度是On2么

遞歸的時間復(fù)雜度，二分法的遞歸算法的時間復(fù)雜度是On2么

來源：整理時間：2023-08-19 10:40:32 編輯：智能門戶手機版

本文目錄一覽

1，二分法的遞歸算法的時間復(fù)雜度是On2么
2，如何用遞歸樹求快速排序時間復(fù)雜度
3，全排列遞歸算法的時間復(fù)雜度怎么算
4，請問遞歸算法的時間復(fù)雜度如何計算呢

1，二分法的遞歸算法的時間復(fù)雜度是On2么

二分法無論是否遞歸，都是O(log2 N)每比較一次，查找范圍被縮短為原來1/2。

log2 N （對數(shù)復(fù)雜度）再看看別人怎么說的。

二分法的遞歸算法的時間復(fù)雜度是On2么

2，如何用遞歸樹求快速排序時間復(fù)雜度

快速排序法的時間復(fù)雜度是nlogn（n×log以2為底n的對數(shù)）拓展：快速排序（Quicksort）是對冒泡排序的一種改進?？焖倥判蛴蒀. A. R. Hoare在1962年提出。它的基本思想是：通過一趟排序?qū)⒁判虻臄?shù)據(jù)分割成獨立的兩部分，其中一部分的所有數(shù)據(jù)都比另外一部分的所有數(shù)據(jù)都要小，然后再按此方法對這兩部分數(shù)據(jù)分別進行快速排序，整個排序過程可以遞歸進行，以此達到整個數(shù)據(jù)變成有序序列。

如何用遞歸樹求快速排序時間復(fù)雜度

3，全排列遞歸算法的時間復(fù)雜度怎么算

1、遞歸是指對一個問題的求解，可以通過同一問題的更簡單的形式的求解來表示. 并通過問題的簡單形式的解求出復(fù)雜形式的解. 遞歸是解決一類問題的重要方法. 遞歸程序設(shè)計是程序設(shè)計中常用的一種方法，它可以解決所有有遞歸屬性的問題，并且是行之有效的. 但對于遞歸程序運行的效率比較低，無論是時間還是空間都比非遞歸程序更費，若在程序中消除遞歸調(diào)用，則其運行時間可大為節(jié)省. 以下討論遞歸的時間效率分析方法，以及與非遞歸設(shè)計的時間效率的比較. 2 時間復(fù)雜度的概念及其計算方法算法是對特定問題求解步驟的一種描述. 對于算法的優(yōu)劣有其評價準則，主要在于評價算法的時間效率，算法的時間通過該算法編寫的程序在計算機中運行的時間來衡量，所花費的時間與算法的規(guī)模n有必然的聯(lián)系，當問題的規(guī)模越來越大時，算法所需時間量的上升趨勢就是要考慮的時間度量. 算法的時間度量是依據(jù)算法中最大語句頻度（指算法中某條語句重復(fù)執(zhí)行的次數(shù)）來估算的，它是問題規(guī)模n的某一個函數(shù)f(n). 算法時間度量記作：t（n）=o（f（n））它表示隨問題規(guī)模n的增大，算法執(zhí)行時間的增長率和f（n）的增長率相同，稱作算法的時間復(fù)雜度，簡稱時間復(fù)雜度[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，則這三段程序的時間復(fù)雜度分別為o（1），o（n），o（n2）. 求解過程為：先給出問題規(guī)模n的函數(shù)的表達式，然后給出其時間復(fù)雜度t（n）. 但是在現(xiàn)實程序設(shè)計過程中，往往遇到的問題都是比較復(fù)雜的算法，就不能很容易地寫出規(guī)模n的表達式，也比較難總結(jié)其時間復(fù)雜度. 遞歸函數(shù)就是屬于這種情況. 下面舉例說明遞歸函數(shù)的時間復(fù)雜度的分析方法.

復(fù)雜度就是排列組合總數(shù)：n!

全排列遞歸算法的時間復(fù)雜度怎么算

4，請問遞歸算法的時間復(fù)雜度如何計算呢

遞歸算法的時間復(fù)雜度分析收藏在算法分析中，當一個算法中包含遞歸調(diào)用時，其時間復(fù)雜度的分析會轉(zhuǎn)化為一個遞歸方程求解。實際上，這個問題是數(shù)學(xué)上求解漸近階的問題，而遞歸方程的形式多種多樣，其求解方法也是不一而足，比較常用的有以下四種方法： (1)代入法(Substitution Method) 代入法的基本步驟是先推測遞歸方程的顯式解，然后用數(shù)學(xué)歸納法來驗證該解是否合理。 (2)迭代法(Iteration Method) 迭代法的基本步驟是迭代地展開遞歸方程的右端，使之成為一個非遞歸的和式，然后通過對和式的估計來達到對方程左端即方程的解的估計。 (3)套用公式法(Master Method) 這個方法針對形如“T(n) = aT(n/b) + f(n)”的遞歸方程。這種遞歸方程是分治法的時間復(fù)雜性所滿足的遞歸關(guān)系，即一個規(guī)模為n的問題被分成規(guī)模均為n/b的a個子問題，遞歸地求解這a個子問題，然后通過對這a個子間題的解的綜合，得到原問題的解。 (4)差分方程法(Difference Formula Method) 可以將某些遞歸方程看成差分方程，通過解差分方程的方法來解遞歸方程，然后對解作出漸近階估計。下面就以上方法給出一些例子說明。一、代入法大整數(shù)乘法計算時間的遞歸方程為：T(n) = 4T(n/2) + O(n)，其中T(1) = O(1)，我們猜測一個解T(n) = O(n2 )，根據(jù)符號O的定義，對n>n0，有T(n) < cn2 - eO(2n)（注意，這里減去O(2n)，因其是低階項，不會影響到n足夠大時的漸近性），把這個解代入遞歸方程，得到： T(n) = 4T(n/2) + O(n) ≤ 4c(n/2)2 - eO(2n/2)) + O(n) = cn2 - eO(n) + O(n) ≤ cn2 其中，c為正常數(shù)，e取1，上式符合 T(n)≤cn2 的定義，則可認為O(n2 )是T(n)的一個解，再用數(shù)學(xué)歸納法加以證明。二、迭代法某算法的計算時間為：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可知，i<log4 n，從而 3i+1 ≤ 3log4 n+1 = 3log3 n*log4 3 +1 = 3nlog4 3 代入得： T(n) < 4n + 3nlog4 3，即T(n) = O(n)。三、套用公式法這個方法為估計形如： T(n) = aT(n/b) + f(n) 其中，a≥1和b≥1，均為常數(shù)，f(n)是一個確定的正函數(shù)。在f(n)的三類情況下，我們有T(n)的漸近估計式： 1.若對于某常數(shù)ε>0，有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+ε )，且對于某常數(shù)c>1和所有充分大的正整數(shù)n，有af(n/b)≤cf(n)，則T(n)=O(f(n))。設(shè)T(n) = 4T(n/2) + n，則a = 4，b = 2，f(n) = n，計算得出nlogb a = nlog2 4 = n2 ，而f(n) = n = O(n2-ε )，此時ε= 1，根據(jù)第1種情況，我們得到T(n) = O(n2 )。這里涉及的三類情況，都是拿f(n)與nlogb a 作比較，而遞歸方程解的漸近階由這兩個函數(shù)中的較大者決定。在第一類情況下，函數(shù)nlogb a 較大，則T(n)=O(nlogb a )；在第三類情況下，函數(shù)f(n)較大，則T(n)=O(f (n))；在第二類情況下，兩個函數(shù)一樣大，則T(n)=O(nlogb a *logn)，即以n的對數(shù)作為因子乘上f(n)與T(n)的同階。但上述三類情況并沒有覆蓋所有可能的f(n)。在第一類情況和第二類情況之間有一個間隙：f(n)小于但不是多項式地小于nlogb a ，第二類與第三類之間也存在這種情況，此時公式法不適用。本文來自CSDN博客，轉(zhuǎn)載請標明出處：http://blog.csdn.net/metasearch/archive/2009/08/09/4428865.aspx

文章TAG：遞歸的時間復(fù)雜度二分法的遞歸算法的時間復(fù)雜度是On2么