求教时间复杂度的计算： O(1)+O(2)+...+O(N-1)+O(N)=? O(1)+...+O(N/4)+O(N/2)+O(N)=?

O(1)+O(2)+...+O(N-1)+O(N)=?
O(1)+...+O(N/4)+O(N/2)+O(N)=?
最好能解释得详细点。对时间复杂度的计算一直不太清楚。

第1个回答 2012-12-29

算法复杂度，其实很好算的:)

首先因为它这里的N代表无穷大，
所以这里要用N的最大项去计算

然后别的数值相对于N来说，常数是忽略不计的

另外相关的可以进行归纳函数的，要写成对应的函数
你这里就是一个等差求和公式，和一个等比求和公式，
但是为什么最后是O(1)?

然后写成函数后，就保留最大项，同时保留最大项的常数
然后再求个导就出来了……

第2个回答 2012-12-30

第一个：1+2 + ... + N = N(N+1)/2 于是去掉常量和低阶的得到O(N^2)
第二个：1 + ... + N/4 + N/2 + N = 2N，于是为O(N)本回答被提问者和网友采纳

相似回答

数据结构时间复杂度的计算这个怎么算?答：总结操作次数：将各个基本操作的执行次数相加，得到算法在特定输入情况下的总操作次数。使用大O符号表示：将总操作次数表示为输入规模（通常用n表示）的函数，并使用大O符号表示时间复杂度。例如，O(n)表示线性时间复杂度，O(n^2)表示平方时间复杂度，O(log n)表示对数时间复杂度，等等。考虑最坏情况...

克拉默法则是什么?答：3、克莱姆法则不仅仅适用于实数域，它在任何域上面都可以成立。对于多于两个或三个方程的系统，克莱姆的规则在计算上非常低效；与具有多项式时间复杂度的消除方法相比，其渐近的复杂度为O（n·n！）。即使对于2×2系统，克拉默的规则在数值上也是不稳定的。它适用于变量和方程数目相等的线性方程组，...

时间复杂度10n²+4n+2=O(n²)还是10n²+4n+2=O(n3)?答：因为当N→无穷大时，这个式子就→n2

for(i=1;i<n;i++) for(j=1;j<=i;j++) x++答：以循环体的执行次数的数量级的求解来实现，这是双重循环，且内循环次数不是常数，可以通过分别计算出在外层循环的每次执行时的内层循环的次数来实现，i=1内层1次 i=2内层2次 i=3内层3次 ...i=n-1内层n-1次由此，最内层循环体共执行n(n-1)/2次，所以时间复杂度为O（n^2）...

求时间复杂度 p=1; for(i=n;i>0;i--) for(j=i+1;j<n;j++) p=p*j...答：j=p->Seat_No-i+1即j=（p->Seat_No-i+1），p->Seat_No是个指针指向的具体数值，即p指向的Seat_No的取值，然后减去i再加上1，得到的值赋给j作为for函数的第一参数。j<=p->Seat_No也是同一道理，即j小于或者等于p->Seat_No的值就为真继续执行循环，，，主要是要理解指针指向的表达含义...

数据结构时间复杂度怎么计算答：对数时间复杂度（O(log n)）：这是指算法中的基本操作的执行次数是输入数据大小的对数。例如，二分搜索算法的时间复杂度为O(log n)，因为每次比较都可以排除一半的搜索空间。线性时间复杂度（O(n)）：这意味着算法中的基本操作的执行次数与输入数据的大小成正比。例如，对数组或列表进行排序或复制的...

时间复杂度时间复杂度答：在编程语言如Pascal中，通过循环层数可以粗略估算，单层for循环的时间复杂度为O(n)，双层为O(n^2)，以此类推。常见的时间复杂度按规模递增排序，如O(1)、O(log2n)、O(n)等，随着n的增加，效率逐渐降低。在《数据结构（C语言版）》一书中，严蔚敏和吴伟民提到，整个算法的执行时间与基本操作重复...

下面程序段的时间复杂度为( A)。 i=s=0; while(s<n){答：i=s=0; //时间复杂度是O(1)while(s<n){ //时间复杂度是O(n)i++; //时间复杂度是O(n)s+=i; //时间复杂度是O(n)}//累计时间复杂度是O(1+n+n+n)，即O(n)如有疑问请追问，如您满意请采纳，谢谢

大家正在搜

计算算法的时间复杂度属于时间复杂度的表示与计算时间复杂度计算的例题怎么求算法的时间复杂度时间复杂度计算的例题讲解时间复杂度怎么计算方法时间复杂度计算公式时间复杂度计算技巧如何计算程序时间复杂度