current position:Home>How to calculate the time complexity

How to calculate the time complexity

2022-02-04 16:41:39 CSDN Q & A

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)




Take the answer :

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 .
-=-=-=-
Specific to your problem ,
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



Other answers 2:

Send out the topic and have a look


Other answers 3:

The algorithm basically needs a loop , Recursion, etc ,
Time complexity means that a loop is entering n( May be n Data , It can also be a single value n) The average number of cycles or recursions required for , That is, the number of times the main code is executed

copyright notice
author[CSDN Q & A],Please bring the original link to reprint, thank you.
https://en.cdmana.com/2022/02/202202041641364671.html

Random recommended