Wie die durchschnittliche Laufzeit dieser Funktion finden suchen $ \ theta $ sein (1)

Question

def (lst, x):

for item in lst: 

    if item == x: 

    return True 

    return False 

Wenn der zulässige Eingang eine zufällige Liste der Länge ist n gemacht up von zufälligen Elementen von {1,2, ... 10}
Wie beweise ich, dass die durchschnittliche Laufzeit ist groß-Theta (1)

Ich habe so viele Möglichkeiten ausprobiert, aber ich werde weiter groß- Theta (n)

Answer 1

Wenn die zufällige Methode einheitlich ist, bedeutet es Die erwartete Anzahl von 1 in der Liste ist n/10, die erwartete Anzahl von 2 ist n/10 und so weiter. Wiederum auf der Grundlage eines einheitlichen Zufalls erwarten Sie, dass Sie nach dem Überprüfen von 10 Elementen im schlimmsten Fall x finden. Also hat die Methode den erwarteten konstanten Zeitwert und die Komplexität ist Tetha (1).