AA 競程 Level 1 試聽課 02：計算程式碼時間複雜度的常見方法 --- 數迴圈
Learn how to calculate the time complexity of program code efficiently by understanding common methods like counting loops and operations. Discover the importance of properly defining operations for accurate time complexity calculations.
Install Tubelator On Chrome
Video Summary & Chapters
No chapters for this video generated yet.
Video Transcript
From this video, we will demonstrate how to calculate the complexity of a program in three videos in a row.
The complexity of a program is actually a mathematical problem.
The mathematical problem is the relationship between the number of operations and the value of the program input.
The operation here refers to the addition and subtraction of basic data forms,
or the input and output of basic data forms, etc.
The definition of operation is very important.
Some people will mistake the call and the call sign for more complicated things as only one operation,
which causes a calculation error of time complexity.
We will make another video to remind you guys.
Now, I will introduce the most common way to control the mouse.
the calculation method of the number of times.
Counting each operation,
including how many times it takes to go back,
and multiplying the number of times to go back.
Now we take a real program code as an example.
In this program code,
we see that two variables, a and b, are input.
These two variables are the
the value of the city input.
The mathematical problem we need to solve is
the number of times the city code is executed
and the value of the input.
There are many forward and backward circles.
When we compute,
we usually compare the forward and backward circles
比較運算和後面的i++++++等
because the calculation frequency is usually not more than the lowest calculation in the loop.
So we only need to calculate how many times all the CNT++ executed.
按照我們剛才的說法,就是我們只需要數每個CNT++它在多少層迴圈裡面。
像第九行的CNT++,它是在六、七、八這三行的迴圈裡面。
The number of times the circle will execute is a, b, b.
So we multiply all the numbers by a.
I'll write down the number.
It will be a...
x, y, z.
Next, we see that there is a CNT++ in the 13th row.
This CNT++ is in the 6th and 12th rows of the loop.
The sequence is A and A.
So I wrote it as A x A.
Lastly, there is a CNT++.
This time it's in the 16th and 17th rows of the loop.
So multiply the number of operations of each of them by V times A.
When calculating the complexity of time,
there is a concept that we can eliminate those items that have a relatively low growth rate.
delete those items
For example, here is an A x B x B
and here is a B x A
The growth rate of BxA is definitely smaller than that of AxBxB.
So we can ignore the AxA.
So the next time complexity is
