复杂的递归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

回答

相关问题