Großer o-Wert des Beispielprogramms

Question

Ich versuche zu großen o Worst-Case-Szenario für eine Programmierlogik und brauche einige Erläuterungen.

Hier ist ein sehr einfaches Programm, es dauert eine Zahl - 2938023 und jedes Zeichen wird mit einer Zufallszahl multipliziert und in einer Liste aufgefüllt.

Sobald die Liste ausgefüllt ist, bekomme ich den maximalen Wert als mein Ergebnis.

from random import randint 
def test(A): 
    result = [] 
    for each in str(A): 
     result.append(int(each)*randint(0,9)) 
    return max(result) 


print test(2938023)  

Was ist der schlimmste Fall dieser Operation? Da die Liste - str (A) nur einmal durchlaufen wird, sollte ich es als log (n) oder

betrachten. Sollte ich es als n * n betrachten, wird die Liste erneut iteriert, um den maximalen Wert zu erhalten. Es gibt 2 Pass auf der Liste basierend auf n.

Answer 1

Ok, so die Kommentare eine ziemlich klare Antwort gegeben haben - aber nur zu klären (und auch richtig, die Frage beantworten):

Die beiden Operationen, die das Big-O hier definieren ist:

• for each in str(A): - Dies ist eine O(n) Operation, es sieht jedes Zeichen in der Zeichenfolge (A).
• max(result) - Dies ist auch ein O(n), wie wir die gesamte Liste durchlaufen müssen, um das Maximum zu beheben (result).

Seit len(A) == len(result) können wir dieses 2n nennen (im Gegensatz zu nm), und da es Big-O ist, ziehen wir den konstanten Faktor, was zu: O(n).

Wenn Sie den konstanten Faktor ganz entfernen wollte man die Funktion als umschreiben könnte:

from random import randint 
def test(A): 
    max_item = 0 
    for each in str(A): 
     new_item = int(each)*randint(0,9) 
     if new_item > max_item: 
      max_item = new_item 
    return max_item 

Welche auch O(n), aber iteriert nur die Zeichenfolge.