![]() |
|
[Tut] Python List Length – What’s the Runtime Complexity of len()? - Printable Version +- Sick Gaming (https://sickgaming.net) +-- Forum: Programming (https://sickgaming.net/forum-76.html) +--- Forum: Python (https://sickgaming.net/forum-83.html) +--- Thread: [Tut] Python List Length – What’s the Runtime Complexity of len()? (/thread-94433.html) |
[Tut] Python List Length – What’s the Runtime Complexity of len()? - xSicKxBot - 04-07-2020 Python List Length – What’s the Runtime Complexity of len()? The runtime complexity of the Code: len()Python list objects keep track of their own length. When you call the function Code: len(...)
Here’s a snippet of the C++ implementation of the list data structure: Code: static int
list_resize(PyListObject *self, Py_ssize_t newsize)
{ PyObject **items; size_t new_allocated, num_allocated_bytes; Py_ssize_t allocated = self->allocated; // some implementation details Py_SET_SIZE(self, newsize); self->allocated = new_allocated; return 0;
}Here’s the table based on the official Python wiki: Operation | Average Case | Amortized Worst Case copy() | O(n) | O(n) append() | O(1) | O(1) pop() | O(1) | O(1) pop(i) | O(k) | O(k) insert() | O(n) | O(n) list | O(1) | O(1) list[i] = x | O(1) | O(1) remove(x) | O(n) | O(n) for i in list | O(n) | O(n) list[i:j] | O(k) | O(k) del list[i:j] | O(n) | O(n) list[i:j] = y | O(k+n) | O(k+n) extend() | O(k) | O(k) sort() | O(n log n) | O(n log n) […] * 10 | O(nk) | O(nk) Code: x in lstO(n) | min(lst), max(lst) | O(n) | len(lst) | O(1) | O(1) The Python list is implemented using a C++ array. This means that it’s generally slow to modify elements at the beginning of each list because all elements have to be shifted to the right. If you add an element to the end of a list, it’s usually fast. However, resizing an array can become slow from time to time if more memory has to be allocated for the array. Where to Go From Here If you keep struggling with those basic Python commands and you feel stuck in your learning progress, I’ve got something for you: Python One-Liners (Amazon Link). In the book, I’ll give you a thorough overview of critical computer science topics such as machine learning, regular expression, data science, NumPy, and Python basics—all in a single line of Python code! Get the book from Amazon! OFFICIAL BOOK DESCRIPTION: [i]Python One-Liners will show readers how to perform useful tasks with one line of Python code. Following a brief Python refresher, the book covers essential advanced topics like slicing, list comprehension, broadcasting, lambda functions, algorithms, regular expressions, neural networks, logistic regression and more. Each of the 50 book sections introduces a problem to solve, walks the reader through the skills necessary to solve that problem, then provides a concise one-liner Python solution with a detailed explanation. |