Was ist die asymptotische Komplexität dieses speziellen (schlechten) Algorithmus zur Berechnung der Quadratwurzel einer Zahl?

Question

Gestolpert über einen (schrecklichen) Algorithmus zur Berechnung der Quadratwurzel einer Zahl. Bin in ein kleines Streitgespräch über die zeitliche Komplexität geraten. Ich behaupte, dass die Zeitkomplexität O (n^2) ist, weil für n Eingang es n mal multipliziert wird. Mein Freund behauptet, dass die Zeitkomplexität tatsächlich O (n) ist. Wer hat Recht und warum?

def squareRoot(x): 
if x<0: 
    return "undefined" 
elif x==0: 
    return 0 
for i in range(0,x): 
    if(i*i)==x: 
     return i 

Answer 1

Es ist O (n), da im schlimmsten Fall, Sie x Multiplikationen und Tests durchführen, so dass Ihre Rechenzeit wächst linear mit Ihrer Eingabe.

Answer 2

Zuerst müssen wir wissen, was die Komplexität der Integer-Multiplikation ist.

Der Einfachheit halber verwenden wir die Schönhage–Strassen algorithm. Die Komplexität ist O(n log n log log n) für Zahlen mit n Ziffern.

Natürlich kann die Anzahl n hat tatsächlich O(log n) Ziffern, so zu multiplizieren Zahlen Wert n, die Zeitkomplexität ist O(log n log log n log log log n)

Es gibt n Zahlen von bis zu n Größe zu multiplizieren, also insgesamt ist es O(n log n log log n log log log n)

Also O(n^2) war richtiger, in der gleichen Weise wie O(n!) korrekt war. Richtig, aber nicht hilfreich. Und O(n) ist einfach falsch, ohne mehrere Annahmen, die nicht gemacht wurden.

Beachten Sie, dass Sie bessere Multiplikationsalgorithmen verwenden können.

Answer 3

Lässt uns zuerst sehen, wie dieser Algo funktioniert.

Im schlimmsten Fall, das heißt, x ist kein perfektes Quadrat und x ist prim, die Zeitkomplexität ist O (n).
Im besten Fall. das ist die Nr. ist perfektes Quadrat, dann wird es in der Reihenfolge von SQRT (n) sein.