问题描述

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

给出如下算法，请分析时间复杂度。
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. }

解决方案

复杂度 n^2*logn

解决方案二：

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