如果我说一个算法的时间复杂度是O(m*n)且m&&n,那我要不要交代m和n分别代表什么?_百度知道
如果我说一个算法的时间复杂度是O(m*n)且m&&n,那我要不要交代m和n分别代表什么?
提问者采纳
.m，那就应该是嵌套循环：for(i=0;n.n;j&lt。那m和n代表不一样。可能是for(i=0;i&i++){for(j=0.}也有可能是;i++){for(j=0.}这两种情况是完全不同的.j&j++)i&lt应该要吧.
。因为既然是O(m*n);m
来自：求助得到的回答
来自团队：
其他类似问题
为您推荐：
时间复杂度的相关知识
其他1条回答
等待您来回答
下载知道APP
随时随地咨询
出门在外也不愁某算法的时间复杂度为O(n^2),表明该算法的_______________.A 问题规模是n^2 B 执行时间等于n^2C 执行时间与n^2成正比 D问题规模与n^2成正比
n就是问题的规模,因此A答案不对,答案是C,时间复杂度就是执行时间,O代表同数量级,至于答案B,则是C中包含的特例,一般O(n^2)得算法并不一定是执行时间等于n^2
为您推荐：
其他类似问题
扫描下载二维码请问递归算法的时间复杂度如何计算呢?_百度知道
请问递归算法的时间复杂度如何计算呢?
　　1、递归　　是指对一个问题的求解，可以通过同一问题的更简单的形式的求解来表示. 并通过问题的简单形式的解求出复杂形式的解. 递归是解决一类问题的重要方法. 递归程序设计是程序设计中常用的一种方法，它可以解决所有有递归属性的问题，并且是行之有效的. 但对于递归程序运行的效率比较低，无论是时间还是空间都比非递归程序更费，若在程序中消除递归调用，则其运行时间可大为节省. 以下讨论递归的时间效率分析方法，以及与非递归设计的时间效率的比较.　　2、时间复杂度的概念及其计算方法　　算法是对特定问题求解步骤的一种描述. 对于算法的优劣有其评价准则，主要在于评价算法的时间效率，算法的时间通过该算法编写的程序在计算机中运行的时间来衡量，所花费的时间与算法的规模n有必然的联系，当问题的规模越来越大时，算法所需时间量的上升趋势就是要考虑的时间度量。　　算法的时间度量是依据算法中最大语句频度（指算法中某条语句重复执行的次数）来估算的，它是问题规模n的某一个函数f(n). 算法时间度量记作：T（n）=O（f（n）） 。它表示随问题规模n的增大，算法执行时间的增长率和f（n）的增长率相同，称作算法的时间复杂度，简称时间复杂度[2]。　　例如下列程序段：（1）x=x+1;（2）for(i=1;i&=n;i++) x=x+1;（3）for(j=1;j&=n;j++) for(k=1;k&=n;k++) x=x+1. 以上三个程序段中，语句x=x+1的频度分别为1，n，n2，则这三段程序的时间复杂度分别为O（1），O（n），O（n2）。　　求解过程为：先给出问题规模n的函数的表达式，然后给出其时间复杂度T（n）。　　但是在现实程序设计过程中，往往遇到的问题都是比较复杂的算法，就不能很容易地写出规模n的表达式，也比较难总结其时间复杂度. 递归函数就是属于这种情况. 下面举例说明递归函数的时间复杂度的分析方法。
其他类似问题
为您推荐：
提问者采纳
均为常数://blog，函数f(n)较大、迭代法
某算法的计算时间为. + 3( n/2)2 - eO(2n&#47；在第二类情况下，把这个解代入递归方程. + (3i /b)≤cf(n)。本文来自CSDN博客：T(n) = 4T(n/log4 n。
(4)差分方程法(Difference Formula Method)
可以将某些递归方程看成差分方程.net/metasearch/archive//4428865。
下面就以上方法给出一些例子说明。
设T(n) = 4T(n&#47。
这里涉及的三类情况.，有af(n/2) + n，从而
3i+1 ≤ 3log4 n+1 = 3log3 n*log4 3 +1 = 3nlog4 3
代入得，上式符合 T(n)≤cn2 的定义，比较常用的有以下四种方法，则T(n)=O(f (n))，两个函数一样大。
一，函数nlogb a 较大，其求解方法也是不一而足，都是拿f(n)与nlogb a 作比较，其中T(1) = O(1)，则T(n) = O(nlogb a )
(1)代入法(Substitution Method)
代入法的基本步骤是先推测递归方程的显式解;42 ) + 。这种递归方程是分治法的时间复杂性所满足的递归关系;b) + f(n)”的递归方程，i&lt，有f(n) = O(nlogb a-ε )、套用公式法
这个方法为估计形如;4i+1 ) ) ) )
T(n) = O(n) + 3( O(n/0：
T(n) = 3T(n&#47.若对于某常数ε&gt，根据第1种情况，转载请标明出处，这里减去O(2n).csdn，再用数学归纳法加以证明.。在第一类情况下，我们可以写出迭代i次后的方程，a≥1和b≥1：
1，则T(n)=O(nlogb a )，迭代两次可将右端展开为。
三。在第一类情况和第二类情况之间有一个间隙，这是一个递归方程，则T(n) = O(nlogb a *logn)
3.aspx" target="_blank">4i+1 =1可知，这个问题是数学上求解渐近阶的问题; 4n + 3i+1
而由n&#47，b = 2.net/metasearch/archive//4428865，即T(n) = O(n)，不会影响到n足够大时的渐近性）;4) + O(n)
= O(n) + 3( O(n/4i+1 )=1，根据符号O的定义，使之成为一个非递归的和式;b) + f(n)
其中; 4n + 3nlog4 3.若f(n) = O(nlogb a );4i+1 =1时：<a href="http，f(n)是一个确定的正函数，T(n/43 ) ) )
从上式可以看出;4) + O(n);2) + O(n)
≤ 4c(n/n0，因其是低阶项：
T(n) = aT(n/4) + 3( O(n&#47，然后通过对这a个子间题的解的综合，然后通过对和式的估计来达到对方程左端即方程的解的估计，f(n) =1和所有充分大的正整数n，我们有T(n)的渐近估计式。
二，第二类与第三类之间也存在这种情况，得到原问题的解，e取1.2)) + O(n)
= cn2 - eO(n) + O(n)
T(n) = 4T(n&#47；在第三类情况下://blog。
(2)迭代法(Iteration Method)
迭代法的基本步骤是迭代地展开递归方程的右端。
但上述三类情况并没有覆盖所有可能的f(n)，c为正常数，计算得出nlogb a = nlog2 4 = n2 ，则a = 4：T(n) = 3T(n&#47、代入法
大整数乘法计算时间的递归方程为，然后对解作出渐近阶估计，此时公式法不适用;42 )n + 。
(3)套用公式法(Master Method)
这个方法针对形如“T(n) = aT(n/b的a个子问题，对n&gt，然后用数学归纳法来验证该解是否合理，则可认为O(n2 )是T(n)的一个解。实际上，则T(n)=O(f(n))：
T(n) &lt递归算法的时间复杂度分析 收藏 在算法分析中;42 ) + 3T(n&#47，则T(n)=O(nlogb a *logn)，而f(n) = n = O(n2-ε ).若f(n) = O(nlogb a+ε )，即以n的对数作为因子乘上f(n)与T(n)的同阶.，而递归方程解的渐近阶由这两个函数中的较大者决定;4i )n + (3i+1 )T(1)
&2) + O(n)，且对于某常数c&gt，当一个算法中包含递归调用时，其时间复杂度的分析会转化为一个递归方程求解，有T(n) &4) + 3T(n/42 ) )
= O(n) + 3( O(n&#47，而递归方程的形式多种多样，通过解差分方程的方法来解递归方程，其中T(1) = O(1)，我们得到T(n) = O(n2 );4i + 3T(n&#47，我们猜测一个解T(n) = O(n2 )：f(n)小于但不是多项式地小于 cn2 - eO(2n)（注意，此时ε= 1，得到.;4) + 3( O(n&#47，则
T(n) = n + (3/4) + (32 &#47。在f(n)的三类情况下，即一个规模为n的问题被分成规模均为n&#47，递归地求解这a个子问题
递归算法的相关知识
等待您来回答
下载知道APP
随时随地咨询
出门在外也不愁时间复杂性为O (n2),是什么意思计算机中算法的时间复杂度为O (n2)，O (n),，这些是什么意思。请举例说明
錓鶻靳0018C
O（n）：for(i=0;i<100;i++)O(n^2)：for(i=0;i<100;i++)
for(j=0;j<100;j++)简介同一问题可用不同算法解决，而一个算法的质量优劣将影响到算法乃至程序的效率。算法分析的目的在于选择合适算法和改进算法。算法复杂度算法复杂度分为时间复杂度和空间复杂度。其作用： 时间复杂度是指执行算法所需要的计算工作量；而空间复杂度是指执行这个算法所需要的内存空间。（算法的复杂性体现在运行该算法时的计算机所需资源的多少上，计算机资源最重要的是时间和空间（即寄存器）资源，因此复杂度分为时间和空间复杂度。）时间复杂度一个算法花费的时间与算法中语句的执行次数成正比例，哪个算法中语句执行次数多，它花费时间就多。一个算法中的语句执行次数称为语句频度或时间频度。记为T(n)。　　一般情况下，算法中基本操作重复执行的次数是问题规模n的某个函数，用T(n)表示，若有某个辅助函数f(n),使得当n趋近于无穷大时，T（n)/f (n)的极限值为不等于零的常数，则称f(n)是T(n)的同数量级函数。记作T(n)=O(f(n)),称O(f(n)) 为算法的渐进时间复杂度，简称时间复杂度。　　在各种不同算法中，若算法中语句执行次数为一个常数，则时间复杂度为O(1),另外，在时间频度不相同时，时间复杂度有可能相同，如T(n)=n2+3n+4与T(n)=4n2+2n+1它们的频度不同，但时间复杂度相同，都为O(n2)。
为您推荐：
扫描下载二维码考研题,求时间复杂度,请说明下理由,假定问题规模为N时,某递归算法的时间复杂度记为T（N）,已知T(1)=1,T(N)=2T(N/2)+N/2,用O表示的时间复杂度为（）A O(N) B O(NlogN) C O(N&#178;) D O(N&#178;logN)
答案是B根据条件递推：
T(N) = N/2+2T(N/2) = N/2+2*(N/4+2T(N/4)) = N/2 + N/2 + 4T(N/4)
= N/2 + N/2 + N/2 + 8T(N/8) = .可见 N 每次除2,是按 log 递减的,所以在 logN 次以后减为1,又因为T(1)=1,所以一共有 logN 个 N/2也就是 N/2 * logN所以答案是 O(NlogN) .
为您推荐：
其他类似问题
扫描下载二维码