# How to calculate the time complexity

2022-02-04 16:41:39

How to calculate the time complexity ？ After reading a lot of information on the Internet, I can only see the misty , When it comes to questions, you won't be able to do them at all , Do you have any brothers and sisters to answer for me . thank you ！
titled ：
a）
for (int i = 0; i < 20; i++)
{
for(int j=0;j<N;j++)
code with O(N)
}
b)
(10 points)
for (int j = 0; j < n; j++)
code with O(1)
for (int j = 1; j < n; j = 2* j)
code with O(N)
C)
for (int j=1;j<N;j=2*j)
code with 0(1)

The so-called time complexity , It's such a thing ：
Suppose you have a piece of code , The unit of time required to run once is 1, Or writing O（1）, The concrete is 1 individual CPU Execution cycle , still 1 minute , Is not important .
When your input value increases N After times , How much more time ？
-=-=-=-
So for a heavy for In a circle , It grows linearly , The number of cycles increases n times , Time also increases n times , So time complexity is O(N)
If it's double for loop , So that is O(N^2), Square relationship .
-=-=-=-
a） A typical heavy for loop
Ask you to write a time complexity is O(N) Code for , Write anything you like , Even if you don't write anything , It is O(N)
b）1) requirement for The time complexity in the loop is O(1), That is, time is not related to N relevant , That directly break Come out .
2） Ask to be j The time complexity increases linearly with exponential growth , The easiest way , Take the ride 2 Except back , again ++
c) Same as B1

Send out the topic and have a look