这个时间复杂度应该怎么算啊?看了网上很多资料也只能看的云里雾里的,真到了做题就完全不会了,有没有兄弟姐妹们来给我解答下。谢谢!
题目为:
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)
所谓时间复杂度,就是这么一个东西:
假设你有一段代码,运行一次需要的时间单位是1,或者写作O(1),具体是1个CPU执行周期,还是1分钟,不重要。
当你的输入数值增加N倍之后,时间增加多少?
-=-=-=-
那么对于一重for循环来说,它是线性增长的,循环次数增加n倍,时间也增加n倍,那么时间复杂度就是O(N)
如果是二重for循环,那么就是O(N^2),成平方关系。
-=-=-=-
具体到你的问题,
a)典型的一重for循环
要求你写个时间复杂度是O(N)的代码,你随便写个什么,哪怕什么都不写,它本来就是O(N)
b)1)要求for循环里面时间复杂度是O(1),也就是时间不与N相关,那直接break出来嘛。
2)要求当j以指数增长时时间复杂度线性增长,最简单的办法,把乘的2除回去,重新++
c)同B1
把题目发出来看看
算法基本需要循环,递归等,
时间复杂度就是说一个循环在输入n(可能是n个数据,也可能是单值n)时需要的平均循环或递归次数,即主要代码执行次数