Dear students, don't read the textbooks any more. Just read this one for the complexity of time

Time complexity is the cornerstone of learning algorithms , Today, let's talk about why we should introduce time complexity , What is the time complexity and how to calculate the time complexity of an algorithm

One 、 Describe the running time of the algorithm

One day , Huineng called Yichen to teach him some basic knowledge , I saw that G wrote a very simple code

Yichen sees that the teacher is a little angry , I began to ask for advice with an open mind

For the convenience of discussion , Here we regard the execution time of each statement as the same , As a Time unit

① The two statements in the blue box , Take two time units

② A statement with a black box , cost n+1 Time units

③ The two statements in the red box , cost 2*n Time units

Isn't this math , Yichen thought to himself

Among them n What we call the scale of the problem , In fact, it is the size of the problem you deal with

Huineng drew the graph of this function conveniently

This paper mainly discusses the relationship between problem size and running time , It is assumed that the different inputs are basically independent of the running time

Two 、 Time complexity

for instance ：T(n)=3n+3, When n A very large Time constant 3 and n The coefficient of 3 The effect on the result of the function is very small

such as ：

T(n)=n+1 Ignore the constant term T(n)~n

T(n)=n+n^2 Ignore lower order terms T(n)~n^2

T(n)=3n Ignore the coefficient of the highest order T(n)~n

Fortunately, I don't have to master the headache of mathematics , Yichen thought

Yichen brings the topic back

More precisely O Represents an asymptotic upper bound of the runtime function , namely T(n) Less than or equal to in order of magnitude f(n)

3、 ... and 、 Calculation of time complexity

One 、 Get the function of running time Two 、 Simplify the function

① With constant 1 To replace all addition constants in run time

② In the modified function , Only the highest order terms ③ If the highest order term exists and is not 1, The coefficient of this term is ignored

O(1) Also known as constant order

Yichen wrote a piece of code with nested loops

next , Huineng wrote another period of code with logarithmic complexity

Yichen, who is not good at mathematics, is a little confused at this time

summary

Learning algorithms , The first step is to know what time complexity is , What is spatial complexity , In fact, you understand the complexity of time , So you can understand the spatial complexity , It is suggested that you still be schoolmates , We must learn the course of data structure and algorithm well .

Whether it's an interview or improving your content , Algorithm learning is essential , I would like to recommend a certain BAT The boss summed it up Leetcode Brush notes ：BAT It's classified and summarized by the boss Leetcode Brush the topic template , Help you with 90% Interview

in addition , I have also written a series of articles on sorting algorithms in cartoons , Post a link directly here , I wish you were in charge of the collection , Hey . But here is only 7 A sort algorithm that must be mastered , Like bucket sort , Cardinality sort these , Understanding can , It will also be written in the later stage .

comic ： What is bubble sorting algorithm ？

comic ： What is a selective sorting algorithm ？

comic ： What is the insertion sort algorithm ？

comic ： What is hill sorting algorithm ？

comic ： What is a merge sort algorithm ？

comic ： What is a quick sort algorithm ？

comic ： What is a heap sorting algorithm ？

Of course , You are also welcome to play on your personal website ：https://www.iamshuaidi.com, from 0 To 1 Summed up personal learning .

The author is concise

author ： Hello everyone , I am a , From University 、 Self study all the way , Know perfectly well Algorithm , Basic computer knowledge Importance , official account 「 Play programming 」10 Million fans, author , Specialized in writing these basic knowledge , Improve our internal skills , Looking forward to your attention , Study with me , Click on I've been in College for four years The road of learning Reprint note ： Not authorized , Prohibited reproduced