enter

output

Finiteness

certainty

feasibility

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)

How many basic operations are required to complete the algorithm?

How many basic operations does the algorithm require at most?

How much basic work does an algorithm take on average to complete?

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.

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>)

O(1)

O(1)

O(1)

O(1)

O(n)

O(n)

O(n)

O(n)

O(n)

O(k)

O(n)

O(n k)

O(n)

O(k)

O(nlogn)

O(nk)

O(n)

O(1)

O(1)

O(1)

O(n)

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