Wondershare EdrawMind
EdrawMindPython data structure 1 introduces concepts
MindMap Gallery Python data structure 1 introduces concepts
- 27
Python data structure 1 introduces concepts
The content of Chapter 1 using Python data structures introduces the concepts of data structures and algorithms and the calculation methods and rules of time complexity.
Edited at 2020-02-25 13:27:59- One Hundred Years of Solitude Character Relationship Chart
One Hundred Years of Solitude is the masterpiece of Gabriel Garcia Marquez. Reading this book begins with making sense of the characters' relationships, which are centered on the Buendía family and tells the story of the family's prosperity and decline, internal relationships and political struggles, self-mixing and rebirth over the course of a hundred years.
- One Hundred Years of Solitude Character Relationship Chart
One Hundred Years of Solitude is the masterpiece of Gabriel Garcia Marquez. Reading this book begins with making sense of the characters' relationships, which are centered on the Buendía family and tells the story of the family's prosperity and decline, internal relationships and political struggles, self-mixing and rebirth over the course of a hundred years.
- Project Management Process Template
Project management is the process of applying specialized knowledge, skills, tools, and methods to project activities so that the project can achieve or exceed the set needs and expectations within the constraints of limited resources. This diagram provides a comprehensive overview of the 8 components of the project management process and can be used as a generic template for direct application.
Python data structure 1 introduces concepts
- One Hundred Years of Solitude Character Relationship Chart
One Hundred Years of Solitude is the masterpiece of Gabriel Garcia Marquez. Reading this book begins with making sense of the characters' relationships, which are centered on the Buendía family and tells the story of the family's prosperity and decline, internal relationships and political struggles, self-mixing and rebirth over the course of a hundred years.
- One Hundred Years of Solitude Character Relationship Chart
One Hundred Years of Solitude is the masterpiece of Gabriel Garcia Marquez. Reading this book begins with making sense of the characters' relationships, which are centered on the Buendía family and tells the story of the family's prosperity and decline, internal relationships and political struggles, self-mixing and rebirth over the course of a hundred years.
- Project Management Process Template
Project management is the process of applying specialized knowledge, skills, tools, and methods to project activities so that the project can achieve or exceed the set needs and expectations within the constraints of limited resources. This diagram provides a comprehensive overview of the 8 components of the project management process and can be used as a generic template for direct application.
- Recommended to you
- Outline
No relevant template
Introduce concepts
Algorithm introduction
Algorithm is the essence of computer processing of information
Algorithms are independent methods and ideas for solving problems
Five characteristics of algorithms
enter
The algorithm has 0 or more inputs
output
The algorithm has at least one or more outputs
Finiteness
The algorithm will automatically end after a limited number of steps instead of infinite loop, and each step steps can be completed within an acceptable time
certainty
Each step in the algorithm has a definite meaning and there is no ambiguity.
feasibility
Each step of the algorithm is feasible, which means that each step can be executed a limited number of times.
The execution time of the algorithm program can reflect the efficiency of the algorithm, that is, the quality of the algorithm.
time complexity
Big O plan
For a monotonic integer function f, if there exists an integer function g and a real constant c>0 such that f(n)<=c*g(n) always exists for a sufficiently large n, then the function g is said to be an asymptotic of f Function (ignoring constants), recorded as f(n)=O(g(n)), that is to say, in the limit sense of infinity, the growth rate of function f is constrained by function g, that is, function f and function g characteristics are similar.
Assume that there is a function g such that the time taken by algorithm A to process a problem example of size n is T(n)=O(g(n)). Then O(g(n)) is called the asymptotic time complexity of algorithm A, recorded as T(n)
optimal time complexity
How many basic operations are required to complete the algorithm?
Worst time complexity
How many basic operations does the algorithm require at most?
average time complexity
How much basic work does an algorithm take on average to complete?
Basic calculation rules
Basic operations: There are only constant terms, and its time complexity is considered to be O(1)
Sequential structure: time complexity is based on addition.
Loop structure: time complexity is calculated as multiplication
Branch structure: take the maximum time complexity
When judging the efficiency of an algorithm, it is often necessary to pay attention to the highest order term in the number of operations. Other minor terms and constant terms can be ignored.
Unless otherwise stated, the time complexity of the algorithms we analyze refers to the worst time complexity.
O(1)<O(logn)<O(n)<O(nlogn)<O(n^2)<O(n^3)<O(2^n)<O(n!)<O(n ^n)
Note: We mainly focus on the worst case scenario of the algorithm, also the worst time complexity
Python built-in type performance analysis
timeit module
Can be used to test the execution speed of a small piece of Python code
class timeit.Time(stmt='pass', setup='pass', timer=<timer function>)
Timer is a class that measures a small piece of code
The stmt parameter is the code statement to be tested
The setup parameters are the settings required when running the code
The timer parameter is a timer function, which is platform-related
timeit.Timer.timeit(number=10000)
Time complexity of different operations on list types
index[]
O(1)
index assignment
O(1)
append
O(1)
pop()
O(1)
pop(i)
O(n)
insert(i, item)
O(n)
del operator
O(n)
iteration
O(n)
contains(in)
O(n)
get slice[x:y]
O(k)
del slice
O(n)
set slice
O(n k)
reverse
O(n)
concatenate
O(k)
sort
O(nlogn)
multiply
O(nk)
Time complexity of different operations on dictionary types
copy
O(n)
get item
O(1)
delete item
O(1)
contains(in)
O(1)
iteration
O(n)
Data structure introduction
ADT (Abstract Data Type)
Refers to a data model and a set of operations on this mathematical model
Encapsulate data types and operations on data types by trapping them together
The purpose of introduction is to combine the representation of data types with operations on data types. Implementation is isolated from references to these data types and operations in the program
The most commonly used data operations
insert
delete
Revise
Find
sort