Big-O der Liste Slicing

Question

Angenommen, ich habe eine Python-Liste, my_list, die N-Elemente enthält. Einzelne Elemente können indiziert werden, indem my_list[i_1] verwendet wird, wobei i_1 der Index des gewünschten Elements ist. Python-Listen können jedoch auch mit my_list[i_1:i_2] indiziert werden, wenn ein "Slice" der Liste von i_1 bis i_2 erwünscht ist. Wie lautet die Big-O-Notation (Worst-Case-Notation), um eine Liste der Größe N zu schneiden?

Persönlich, wenn ich den "Slicer" codieren würde ich von i_1 bis i_2 iterieren, eine neue Liste generieren und es zurückgeben, was O (N) bedeutet, ist das, wie Python es tut?

Danke,

Answer 1

eine Scheibe zu erhalten ist O (i_2 - i_1). Dies liegt daran, dass Pythons interne Repräsentation einer Liste ein Array ist, so dass Sie bei i_1 beginnen und zu i_2 iterieren können.

Weitere Informationen finden Sie im Python time complexity wiki entry

Sie auch bei der Umsetzung in der CPython source aussehen können, wenn Sie wollen.

Answer 2

Für eine Liste der Größe N und einer Scheibe der Größe M ist die Iteration eigentlich nur O (M), nicht O (N). Da M oft < < N ist, macht dies einen großen Unterschied.

In der Tat, wenn Sie an Ihre Erklärung denken, können Sie sehen, warum. Du iterst nur von i_1 nach i_2, nicht von 0 nach i_1, dann von I_1 nach i_2.

Answer 3

nach http://wiki.python.org/moin/TimeComplexity

es O (k), wobei k die Scheibengröße