2 h1012566992 H1012566992 于 2014.12.06 21:28 提问

给出如下算法,请分析时间复杂度。求教

给出如下算法,请分析时间复杂度。
1. Type game(Type group[],int n)
2. {
3. int j,i = n;
4. while (i>1) {
5. i = i / 2;
6. for (j=0;j<i;j++)
7. if (comp(group[j+i],group[j]);
8. group[j] = group[j+i];
9. }
10. return group[0];
11. }

2个回答

devmiao
devmiao   Ds   Rxr 2014.12.06 22:24

复杂度 n^2*logn

qq_29173419
qq_29173419 怎么算的呀
2 年多之前 回复
H1012566992
H1012566992 怎么得来的?可以帮我讲解一下吗?
3 年多之前 回复
eagleyan
eagleyan   Rxr 2014.12.07 13:43

n + n/2 + n/4 +... = 2n所以是O(n)

Csdn user default icon
上传中...
上传图片
插入图片
准确详细的回答,更有利于被提问者采纳,从而获得C币。复制、灌水、广告等回答会被删除,是时候展现真正的技术了!
其他相关推荐
O(logn)时间复杂度求Fibonacci数列
转载: http://blog.csdn.net/dadoneo/article/details/6776272   谢谢分享! O(logn)时间复杂度求Fibonacci数列 题目:定义Fibonacci数列如下:         /  0                      n=0 f(n)=      1                   
笔试时常用排序算法时间复杂度和空间复杂度
摘自维基百科: http://zh.wikipedia.org/wiki/%E6%8E%92%E5%BA%8F%E7%AE%97%E6%B3%95#.E7.A8.B3.E5.AE.9A.E6.80.A7 在计算机科学所使用的排序算法通常被分类为:计算的时间复杂度(最差、平均、和最好性能),依据列表(list)的大小(n)。一般而言,好的性能是O(n log n),且坏的性能是O(n2)。
各种排序算法时间复杂度及空间复杂度
一、排序算法的时间复杂度及空间复杂度 冒泡: 平均O(N2) ,最坏O(N2) ,最好O(N) ,辅助内存O(1),稳定排序 最好情况是加了改进方法的最好:即冒泡的过程中检查是否发生了交换,如果没有发生交换,说明都排好序了,就break 插入: 平均O(N2) ,最坏O(N2) ,最好O(N) ,辅助内存O(1),稳定排序 直接选择排序:平均O(N2) ,最坏O(N2) ,最好
算法导论-最大子数组问题-线性时间复杂度算法分析与实现
之前写了最大子数组问题的分治法,今天把这个问题的线性时间复杂度的算法写出来。 这个方法在算法导论最大子数组问题的课后思考题里面提出来了,只是说的不够详细。 思考题如下:使用如下思想为最大子数组问题设计一个非递归的,线性时间复杂度的算法。从数组左边界开始,由左至右处理,纪录到目前为止已经处理过的最大子数组。若已知A[1...j]的最大子数组,基于如下性质将解扩展为A[1...j+1]的最大子数组
插入排序、归并排序和递归算法的复杂性分析
算法的复杂性分析,说白了也就是关于计算机程序的性能和算法所用计算机资源的理论分析。通常包括时间复杂性T(n)和空间复杂性S(n),其中n是问题的输入规模。一般来说算法需要的时间与输入的规模同步增长,所以通常把一个程序的运行时间描述成输入规模的函数。 对许多问题,比如排序或计算离散傅里叶变换最自然的量度是输入中的项数,例如带排序数组的规模n。对许多其他问题,比如两个整数相乘,输入规模的最佳量度是用通常的二进制记号表示输入所需的总位数。
一文搞懂算法的时间复杂度与空间复杂度
时间复杂度分析 空间复杂度
图像的四叉树深度优先存储
#include #include "QuadTree.h" #include #include #include #include #include #include #include using namespace std; typedef struct structQTree QTree; struct structQTree { unsigned char pixel;
算法的时间复杂度和空间复杂度
一、常用的算法的时间复杂度和空间复杂度 二、算法的时间复杂度和空间复杂度合称为算法的复杂度。 1.时间复杂度 (1)时间频度 一个算法执行所耗费的时间,从理论上是不能算出来的,必须上机运行测试才能知道。但我们不可能也没有必要对每个算法都上机测试,只需知道哪个算法花费的时间多,哪个算法花费的时间少就可以了。并且一个算法花费的时间与算法中语句的执行次数成正比例,哪个算法中语句
排序算法之 快速排序 及其时间复杂度和空间复杂度
基本思想是:通过一趟排序将要排序的数据分割成独立的两部分,其中一部分的所有数据都比另外一部分的所有数据都要小,然后再按此方法对这两部分数据分别进行快速排序,整个排序过程可以递归进行,以此达到整个数据变成有序序列。 我看了下网上有些bolg写排序算法,有的是理解错误了;有的呢是太过于复杂;还有的呢就干脆是用临时数组,而不是就地排序。当然我的也并没有多好,只是提够一种思路;
算法的时间复杂度和空间复杂度计算
一、算法的时间复杂度定义 在进行算法分析时,语句总的执行次数T(n)是关于问题规模n的函数,进而分析T(n)随n的变化情况并确定T(n)的数量级。算法的时间复杂度,也就是算法的时间量度。记作:T(n)=O(f(n))。它表示随问题n的增大,算法执行时间的增长率和f(n)的增长率相同,称作算法的渐进时间复杂度,简称为时间复杂度。其中,f(n)是问题规模n的某个函数。 这样用大写O()来体现算法时