Komplexität auf rekursivem Big-O

Question

Ich habe eine Informatik Midterm morgen und ich brauche Hilfe bei der Bestimmung der Komplexität dieser rekursiven Funktionen. Ich weiß, wie man einfache Fälle löst, aber ich versuche immer noch zu lernen, wie man diese schwereren Fälle löst. Jede Hilfe würde sehr geschätzt werden und würde sehr in meinen Studien helfen, Danke!

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 

Answer 1

Für das praktische Lernen können Sie die Funktionen in ein Programm stecken und ihre Worst-Case-Szenario-Leistung testen.

Beim Versuch O von Hand zu berechnen, sind hier einige Dinge

• Die +, sich daran zu erinnern -, * und/Offsets ignoriert werden können. Also gilt 1 bis n + 5 und 1 bis 5n als gleichwertig zu 1 bis n.
• Auch zählt nur die höchste Größenordnung, so dass für O 2^n + n^2 + n, 2^n am schnellsten wächst, also entspricht es O 2^n
• Mit rekursiven Funktionen schauen, wie oft die Funktion in der Methode aufgerufen wird (die Split-Anzahl) und wie oft sie aufgerufen werden muss (die Tiefe entspricht normalerweise der Listenlänge). Der letzte O wird also depth_count^split_count
• Mit Schleifen multipliziert jede verschachtelte Schleife mit der, in der sie ist, und sequentielle Schleifen hinzufügen, so (1-n) {(1-n) {}} (1-n) {} ist (n * n) + n) => n^2 + n = (nur das höchste Wachstum zählt)> n^2
• PRAXIS! Sie müssen üben, um den Einfluss der Gatschs der Wachstumsrate zu erhalten und wie die Kontrollflüsse interagieren. (So ​​tun Online-Praxis 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);