Anzahl der Multiplikationen in verschachtelten Schleifen: Groß O

Question

if x: 
    for i in range(a): 
     for z in range(a): 
      for k in range(z): 
      for p in range(i): 
       c = (i * z) + (k * p) 
else: 
    for i in range(a): 
     for z in range(a): 
      for k in range(z): 
       c = (i * z) + (k * p) 

Wäre dies O (n^4)? Wie viele Multiplikationen würden auch auftreten?

EDIT: den Code aktualisiert. Da die Untergrenze auch die maximale Anzahl von Schritten erfasst, die eine gültige Eingabe erzwingen würde, wäre nicht auch ein großes Omega n^4?

Answer 1

Ja, die Komplexität ist immer noch O(n^4). Um die Dinge einfach, hier ist der Trick des Code

for i in range(a): 
    for p in range(i): 
     f(i, p) 

neu zu ordnen, wo f(i, p) ist

for z in range(a): 
    for k in range(z): 
     c = (i * z) + (k * p) 

Im ersten Teil, f(i, p) wurde für O(n^2/2) bis zum größten Auftrag (wegen der Hingerichteten Summierung sum_i (i^2), die Mathe selbst). Ähnlich hat die f(i, p) die Komplexität von f(i, p), die wiederum gleich O(n^2/2) ist.

Also ist die kombinierte resultierende Reihenfolge O(n^4/4). und es gibt zwei Multiplikationen für jede Operation, so ist die Nummer der Multiplikation O(n^4/2)

Answer 2

Der folgende Code wäre nur O (N 4 ), wenn alle Zahlen a, z und i O wurden (n).

for i in range(a): 
    for z in range(a): 
     for k in range(z): 
     for p in range(i): 
      c = (i * z) + (k * p) 

Wie Sie es geschrieben haben, alles, was wir wissen ist, dass der Code-Block O (a zi) ist. In ähnlicher Weise wäre die Gesamtzahl der Multiplikationen, die auftreten würden: 2a zi. Und wiederum, wenn a, z und i alle O (n) sind, wäre die Anzahl der Multiplikationen O (n).

Ich bin mir nicht sicher, was Sie über den zweiten Codeblock wissen möchten.