Berechnen Sie die Komplexität in rekursiven Algorithmus mit tiefen Grenzwert

Guten Morgen, ich studiere Algorithmen und die Möglichkeit, Komplexität zu berechnen, wenn rekursive Aufrufe, aber ich kann keinen Verweis darauf finden, wie eine Ebenenbegrenzung in rekursiven Aufrufe die Berechnung der Komplexität beeinflussen kann. Zum Beispiel dieses Code:Berechnen Sie die Komplexität in rekursiven Algorithmus mit tiefen Grenzwert

countFamilyMembers(int level,....,int count){ 
     if(noOperationCondition) { // for example no need to process this item because business rules like member already counted 
      return count; 
     } else if(level >= MAX_LEVEL) { // Level validation, we want just to look up to certain level 
      return ++count //last level to see then no more recurrence. 
     } else { 
      for (...each memberRelatives...) { //can be a database lookup for relatives to explore 
       count = countFamilyMembers(++level,...,++count); 
      } 
      return count; 
     } 
    }

ich denke, das O (2^n), da der rekursive Aufruf in der Schleife ist. Ich habe jedoch zwei Hauptfragen: 1. Was passiert, wenn die Loop-Werte überhaupt nicht auf den ursprünglichen Eingang bezogen ist? kann das auch "n" sein? 2. Die Level-Validierung dient zum sicheren Schneiden der rekursiven Aufrufe. Wie wirkt sich dies auf die Komplexitätsberechnung aus?

Quelle

2016-10-21 Luis Felipe

Ein Ansatz besteht darin, die Rekursion in eine Schleife zu zerlegen (sieht in diesem Fall ziemlich einfach aus). Dann können Sie die Komplexität des nicht-rekursiven Algorithmus auswerten, was oft einfacher ist. – PaulF

Was ist ** n ** in Bezug auf Ihre ursprünglichen Eingabeparameter? Ist MAX_LEVEL eine Konstante? Ist der Fan-out (Anzahl der Verwandten von einem bestimmten Knoten) begrenzt oder eine andere Variable oder etwas anderes? Diese beeinflussen die Komplexität erheblich. – Prune

n bezieht sich auf die Anzahl der Verwandten jeder Person. MAX_LEVEL ist eine Konstante, ich denke, das sollte die Komplexität verringern oder zumindest Komplexität in Bezug auf sie schreiben, ich bin mir nicht sicher, wie es noch geht. Die Anzahl der Verwandten für einen bestimmten Knoten ist nicht begrenzt, es kann ein beliebiger Wert wie im wirklichen Leben sein. –

Danke für die Klarstellungen. Also nehmen wir n als einige "beste Metrik" auf die Anzahl der Verwandten; Dies wird in einigen Paradigmen auch als "Fan-out" bezeichnet.

So haben Sie 1 Person auf Stufe 0, n auf der Ebene 1, n^2 auf Stufe 2, und so weiter. Eine grobe Schätzung des Rückgabewerts ... und der Anzahl der Operationen (Knotenbesuche, Inkremente usw.) ist die Summe von n^Ebene für den Pegelbereich 0 bis MAX_LEVEL. Der dominierende Term ist der höchste Exponent, n^MAX_LEVEL.

Mit den gegebenen Informationen glaube ich, dass das Ihre Antwort ist: O (n ^^ MAX_LEVEL), a.k.a. polynomiale Zeit.

Beachten Sie, dass, wenn Sie zufällig einen Wert für n gegeben werden, auch eine Obergrenze für n, dann ist dies eine konstant wird, und die Komplexität ist O (1).

Quelle

2016-10-21 23:28:09 Prune

vielen dank! Ich schätze die Einfachheit der Antwort in Bezug auf die Ebenen, sehr gut erklärt und klar! Könntest du bitte die letzte Zeile über die konstante Zeit erläutern? Wenn n eine obere Schranke hat, würde es dann n-mal für jedes Level und dann wieder n für jeden der Verwandten iterieren? –

Angenommen, MAX_LEVEL ist 5 und n ist auf 10 begrenzt. Sie haben jetzt eine strenge Obergrenze von 10^5 + 10^4 + ... + 10^0 Inspektionen. Das sind 111.111 Inspektionen. * Jede * konstante Grenze ergibt eine ** O (1) ** -Komplexität. Zugegeben, es kann in kürzerer Zeit fertig sein, aber Sie haben die Parameter als unbeschränkten Faktor der Laufzeit eliminiert. Ja, Sie können etwas kürzere Laufzeit vorhersagen, durch Skalierung mit einem tatsächlichen Wert von ** n **, aber in der Komplexitätstheorie, das ist einfach "sub-konstante Zeit" Details. – Prune

Sehr klar. Vielen Dank! –

Berechnen Sie die Komplexität in rekursiven Algorithmus mit tiefen Grenzwert

Antwort

Verwandte Themen