Shulou(Shulou.com)06/02 Report--

This article mainly explains "what is the time complexity of Python data structure". Interested friends may wish to take a look at it. The method introduced in this paper is simple, fast and practical. Let's let the editor take you to learn what the time complexity of Python data structures means.

Purpose of the article

This paper introduces the Big-O representation of key operations of data structures in CPython. Big-O representation is a method to measure the time complexity of operation.

1. Let's understand what the big O symbol means.

Many operations are performed in the algorithm. These actions may include traversing the collection, copying the project or the entire collection, appending items to the collection, inserting items at the beginning or end of the collection, deleting items, or updating items in the collection.

Big-O measures the time complexity of the algorithm. It measures the time required by the algorithm to calculate the required operation. Although we can also measure space complexity (how much space the algorithm takes), this article will focus on time complexity.

In the simplest terms, the Big O notation is a way to measure operational performance based on the input size (called n).

2. What is the difference in Big O notation?

We need to be familiar with many common Big O symbols.

Let's consider n as the size of the input set. In terms of time complexity:

O (1): no matter how large your collection is, the time it takes to perform an operation is constant. This is a constant symbol of time complexity. These operations are as fast as possible. For example, the operation to check whether there are any items within the collection is an O (1) operation.

O (log n): as the size of the collection increases, the logarithm of time spent performing the operation increases. This is the logarithmic time complexity representation. The search algorithm for potential optimization is O (log n).

O (n): the time it takes to perform an operation is linearly proportional to the number of items in the collection. This is a linear time complexity symbol. In terms of performance, this is somewhere in between or medium. As an example, if we want to sum all the items in a collection, we will have to traverse the collection. Therefore, the iteration of the collection is an O (n) operation.

(n log n): the performance of performing an operation is a quasilinear function of the number of items in the collection. This is called quasi-linear time complexity representation. The time complexity of optimized sorting algorithm is usually n (log n).

O (n squared): the time it takes to perform an operation is proportional to the square of the items in the collection. This is called quadratic time complexity representation.

(n!): when each individual arrangement of the collection is calculated in the operation, the time it takes to perform the operation depends on the size of the items in the collection. This is called factorial time complexity representation. Very slow.

This image outlines the Big-O symbols.

O (1) is very fast. O (n squared) is slow. O (n!) Very slow.

The big O symbol is relative. The big O representation has nothing to do with machines, ignores constants, and is understood by a wide range of readers, including mathematicians, technicians, data scientists, and so on.

Best, average, worst case

When we calculate the time complexity of the operation, we can generate complexity according to the best, average, or worst case.

Best-case scenario: as the name implies, this is when the data structure and the items and parameters in the collection are at their best. For example, suppose we want to find an item in the collection. If the item happens to be the first item in the collection, this is the best case for the operation.

On average, complexity is defined based on the distribution of input values.

In a worst-case scenario, an operation may be required to find the project in the last project in a large collection, such as a list, and the algorithm iterates over the collection from the first project.

Python set and time complexity

In this part of this article, I'll document common collections in CPython and then outline their time complexity.

I will pay special attention to the average situation.

1.List

List is one of the most important data structures in Python so far. We can use the list as a stack (the last item added is the first item) or a queue (the first item added is the first item). Lists are ordered and mutable collections because we can update items at will.

Let's review common list operations and their Big-O representations

Insert: Big-O representation is O (n)

Get project: Big-O notation is O (1)

Delete items: the Big-O representation is O (n)

Iteration: Big-O representation is O (n)

Get length: Big-O representation is O (1)

2.Set

Collection is also one of the most widely used data collections in Python. A set is essentially an unordered set. The collection does not allow repetition, so each item in the collection is unique. Sets support many mathematical operations, such as union, difference, intersection of sets, and so on.

Let's review the general Set operation

Check the items in the collection: the Big-O representation is O (1)

The difference between set An and set B: the big O representation is O (the length of A)

The intersection of sets An and B: the large O representation is O (the minimum length of An or B).

The union of sets An and B: relative to length (A) + length (B), its Big-O representation is O (N).

3.Dict dictionary

Finally, I would like to provide an overview of dictionary data collection. A dictionary is a collection of key-value pairs. The key is unique in the dictionary to prevent project conflicts. This is a very useful data collection.

Dictionaries are indexed by keys, where keys can be strings, numbers, or even tuples with strings, numbers, or tuples.

We can perform many operations on the dictionary, such as storing the value of the key, or retrieving items based on the key, or traversing items, and so on.

Let's review the common dictionary time complexity:

Here, we think the key is used to get, set or delete items.

Get project: Big-O notation is O (1)

Set item: Big-O representation is O (1)

Delete item: Big-O representation is O (1)

Ergodic dictionary: the Big-O notation is O (n)

At this point, I believe you have a deeper understanding of "what the time complexity of Python data structure means". You might as well do it in practice. Here is the website, more related content can enter the relevant channels to inquire, follow us, continue to learn!

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.