锐客网

  1. 首页 > 生活百科 > >

代码的时间复杂度，这个程序的时间复杂度怎么计算

经验分享生活百科

1，这个程序的时间复杂度怎么计算时间复杂度是指运行时间与输入规模的关系，你这个没有输入，因此无从谈及时间复杂度如若硬要说，那就是O(1)，表示运行时间与输入规模无关 。【代码的时间复杂度，这个程序的时间复杂度怎么计算】
2，程序的时间复杂度和空间复杂度怎么算时间复杂度是程序运行的时间，也可以说是次数；空间复杂度是程序占用的空间；如下程序：int a[1000000];int cnt = 0;for(int i = 0; i < 1000; i++) for(int j = 0; j < 1000; j++) a[cnt++] = 0;其中空间主要是开了一个数组a,大小为1000000；时间复杂的是2个for循环，第一个循环做一次，第二个就要做1000次，而第一个要做1000 ， 则总共要做1000×1000次……如果2个循环分别对应是M,N次 ， 那么要做的次数就是M*N；可以理解前面的2句话了么？
3 ， 程序的时间复杂度和空间复杂度怎么算空间复杂度一般不用算的 。时间复杂度的计算一般就是简单的数学公式 ， 比如说二分查找就是logn的，因为它要找这么多次嘛，没有什么特别难算的 。时间复杂度是程序运行的时间，也可以说是次数； 空间复杂度是程序占用的空间； 如下程序： int a[1000000]; int cnt = 0; for(int i = 0; i < 1000; i++)for(int j = 0; j < 1000; j++)a[cnt++] = 0; 其中空间主要是开了一个数组a,大小为1000000；时间复杂的是2个for循环，第一个循环做一次，第二个就要做1000次，而第一个要做1000 ， 则总共要做1000×1000次…… 如果2个循环分别对应是m,n次，那么要做的次数就是m*n； 可以理解前面的2句话了么？
4，时间复杂度求解1.2*n*n 。一个复杂的程序在执行时65%的资源耗在循环上，所以在计算程序的复杂度以循环的次数计算，一个循环算是复杂度为1，就这个程序代码来说，这是一个嵌套型循环 ， 外层循环n次，内层循环每次循环2*n次，所以每个外层循环1次，时间复杂度为2n ， 外层循环n次，所以为2*n*n 。2.n第一题中，程序执行了(n-1)2次，因为外循环次数i=n时不满足i<n的要求，所以尽管j<=2^n是满足要求的，但是程序会直接跳出循环体 。从而执行次数取决于外层循环，时间复杂度是o(n2)第二题中，我们设程序执行了s次 。执行了第一次时 ， i=2^1=2，执行了第二次时，i=2^2=4，所以执行了第s次时i=2^s，因为只执行了s次 ， 所以i=2^s>n ， 从而s>logn ， 这样该程序的时间复杂度是o(logn) 。注意logn是以2为底的对数5，C语言算法的时间复杂度如何计算啊主要看你的循环语句的循环次数和嵌套度 。看看这个每个循环都和上一层循环的参数有关 。所以要用地推公式：设i(n)表示第一层循环的i为n时的循环次数 ， 注意到他的下一层循环次数刚好就是n，分别是0,1,2...n-1所以，把每一层循环设一个函数分别为：j(n),k(n),t(n)则有i(n)=j(0)+...+j(n-1)j(n)=k(0)+...+k(n-1)k(n)=t(0)+...+t(n-1)i(0)=j(0)=k(0)=0t(n)=1而总循环数是i(0)+i(1)...+i(n-1)可以根据递推条件得出准确值所以算法复杂度是O(i(0)+i(1)...+i(n-1)) （1）时间频度一个算法执行所耗费的时间 ， 从理论上是不能算出来的，必须上机运行测试才能知道 。但我们不可能也没有必要对每个算法都上机测试，只需知道哪个算法花费的时间多，哪个算法花费的时间少就可以了 。并且一个算法花费的时间与算法中语句的执行次数成正比例，哪个算法中语句执行次数多，它花费时间就多 。一个算法中的语句执行次数称为语句频度或时间频度 。记为T(n) 。（2）时间复杂度在刚才提到的时间频度中，n称为问题的规模，当n不断变化时 ， 时间频度T(n)也会不断变化 。但有时我们想知道它变化时呈现什么规律 。为此 ， 我们引入时间复杂度概念 。一般情况下 ， 算法中基本操作重复执行的次数是问题规模n的某个函数，用T(n)表示 ， 若有某个辅助函数f(n),使得当n趋近于无穷大时，T（n)/f(n)的极限值为不等于零的常数，则称f(n)是T(n)的同数量级函数 。记作T(n)=Ｏ(f(n)),称Ｏ(f(n)) 为算法的渐进时间复杂度，简称时间复杂度 。在各种不同算法中，若算法中语句执行次数为一个常数 ， 则时间复杂度为O(1),另外，在时间频度不相同时，时间复杂度有可能相同 ， 如T(n)=n2+3n+4与T(n)=4n2+2n+1它们的频度不同，但时间复杂度相同，都为O(n2) 。按数量级递增排列，常见的时间复杂度有：常数阶O(1),对数阶O(log(2)n),线性阶O(n),线性对数阶O(nlog(2)n),平方阶O(n^2)，立方阶O(n^3),...，k次方阶O(n^k),指数阶O(2^n) 。随着问题规模n的不断增大，上述时间复杂度不断增大，算法的执行效率越低 。这个是数据结构的问题?。?关系到大O函数，一般不是太复杂的估算一下 ， 复杂的就要像楼上所说的套用公式了，找些数据结构的东西看看吧在计算之前取得系统的滴答数int TBegin = GetTickCount();计算完成过后再次调用减去滴答数就行了，单位msint TEnd = GetTickCount() - TBegin;还有其他更精确的函数，搞忘了，你最好查下MSDN纯C下不要用C自带的计算滴答数的函数 ， 不精确，应该使用系统的这个靠说是说不清也是说不全的，最好去找一下专门的书籍看下，比如《数据结构与算法分析》Micosoft C++我不知道，dev C++里面运行完一遍以后选择 运行》Profile分析 就可以清楚地看到每个函数被调用多少次，耗费了多长时间，占总时间的百分比等等 。

    推荐阅读


    上一篇：4tb

    下一篇：so?n逆向分析修改,Android逆向修改so文件