Asymptotische Komplexität python

Question

Ich habe eine Aufgabe, asymptotische Komplexität dieses Python-Codes zu finden.

for i in range(x): 
    if i == 0: 
     for j in range(x): 
      for k in range(500): 
       print("A ") 

Durch was ich weiß sollte es 500 * x sein. Weil der erste Zyklus nur einmal geht (i == 0), der zweite geht x mal und der dritte 500 mal, also sollte es 500 * x sein, oder? Dies ist jedoch nicht die richtige Antwort. Könntest du mir helfen?

Answer 1

Asymptotische Komplexität beschreibt das Wachstum der Ausführungszeit, da die variablen Faktoren beliebig groß werden. Kurz gesagt, addierte oder multiplizierte Konstanten zählen nicht bei alle, da sie sich nicht mit der Variablen ändern.

Ja, es sind 500 * x Zeilen gedruckt. Sie haben auch x-1 nicht-funktionale Schleife Iterationen. Ihre Gesamtzeit würde als so etwas wie

(x-1) [loop Kopf] + x [loop Kopf] + 500 * x [Schleife Overhead + print Zeit]

berechnet werden Der Schleifenoverhead, der eine Konstante ist, ist jedoch unbedeutend und fällt aus dem Komplexitätsausdruck heraus. In ähnlicher Weise ist das 500 lediglich ein Skalierungsfaktor und wird auch von dem Ausdruck weggelassen. Die Komplexität ist O (x).

Answer 2

Es ist 501 * x, da Sie auch x mal die Linie überprüfen müssen.

Wie die andere Antwort sagt, enthalten wir normalerweise nicht den Faktor. Aber manchmal tun wir es.