複雜的遞歸Big-O

-1

明天我有一個計算機科學中期，我需要幫助來確定這些遞歸函數的複雜性。我知道如何解決簡單的案例，但我仍在努力學習如何解決這些困難的案例。任何幫助將不勝感激，並會對我的學習有很大幫助，謝謝！複雜的遞歸Big-O

fonction F(n) 
    if n == 0 
     return 1 
    else 
     return F(n-1) * n 

fonction UniqueElements(A[0..n-1]) 
    for i=0 to i <= n-2 do 
     for j=i+1 to j <= n-1 do 
      if A[i] == A[j] 
       return false 
     return true 

fonction BinRec(n) 
    if n == 1 
     return 1 
    else 
     return BinRec(floor(n/2)) + 1

來源

2017-05-18 M. Joe

對於手的學習，您可以將函數插入到程序中，並測試其最差情況下的性能。

當試圖通過手工計算O，這裏有一些事情要記住

的+， - ，*，和/偏移可以忽略不計。所以1到n + 5和1到5n被認爲等同於1到n。
此外，只有幅度計數的最高位，所以對於O 2^N + N^2 + N，2^N的增長速度最快，因此它等同於O 2^N
遞歸函數，你正在研究函數在方法中調用的次數（分割計數）以及需要調用多少次（深度，通常等於列表長度）。因此，最後的O將是depth_count^split_count
使用循環，每個嵌套循環乘以它所在的循環，並且順序循環添加，所以（1-n）{（1-n）{}}（1-n） {}是（n * n）+ n）=> n^2 + n =（只有最高增長數）> n^2
實踐！你將需要練習來掌握增長率的增長以及控制流程如何相互作用。（這樣做的在線練習quiz S）

function F(n){ 
 
    count++ 
 
    if (n == 0) 
 
     return 1 
 
    else 
 
     return F(n-1) * n 
 
} 
 

 
function UniqueElements(A){ 
 
    for (var i=0 ; i <= A.length-2; i++){ 
 
     for (var j=i+1;j <= A.length-1; j++){ 
 
      if (A[i] == A[j]){ 
 
       return false 
 
      } 
 
     } 
 
    } 
 
       
 
return true 
 
} 
 

 
function BinRec(n) { 
 
    count++ 
 
    if (n == 1) 
 
     return 1 
 
    else 
 
     return BinRec(Math.floor(n/2)) + 1 
 
} 
 

 
count = 0; 
 
console.log(F(10)); 
 
console.log(count); 
 
count = 0; 
 
console.log(UniqueElements([1,2,3,5])); 
 
console.log(count); 
 
count = 0; 
 
console.log(BinRec(40)); 
 
console.log(count);

來源

2017-05-18 17:10:17 Tezra

複雜的遞歸Big-O

回答

相關問題