Zum Beispiel habe ich eine Liste l n Zahlen haben, was ist die Zeitkomplexität für die Suchoperation:Was ist die zeitliche Komplexität von Pythons Suchoperation "some_element in some_list"?
if 35 in l:
# ......
Ist es O (1) oder O (n)?
In CPython, O (n). https://wiki.python.org/moin/TimeComplexity siehe den dritten Eintrag von unten in der Tabelle "Liste".
Die x in y Syntax funktioniert für viele Dinge, also hängt es vom Typ y ab. Wenn y zum Beispiel ein dict oder set ist, dann ist der durchschnittliche Fall O (1). Wo ist als y eine Liste, dann ist die Zeit Komplexität O (n).
Wie bereits erwähnt, ist die Tabelle mit Komplexitäten hier: https://wiki.python.org/moin/TimeComplexity
Erstes Sucher für „Komplexität Python time“, die erste Tabelle sehen: https://wiki.python.org/moin/TimeComplexity. "X in s" zu prüfen ist "O (n)". – alexwlchan