函数时间复杂度问题,在线求解(容易)
试问此函数时间复杂度是多少?
int a[]={1,2,3,4,5,6,7,8}
order (int j , int m)
{
int i ,temp ;
if (j<m)
{
for (i=j; i<=m; i++)
if (a[i]<a[j])
{
temp=a[i]; a[i]=a[j]; a[j]=temp;
j++;
order (j,m);
}
}
}
问题点数：0、回复次数：6Top
1 楼junnyfeng（风歌）回复于 2004-05-02 16:18:53 得分 0
这是冒泡法的递归实现
这里j跟m未定义，就以这两个变量说吧,设开始时m-j=n
时间复杂度是O(n(n-1)/2)Top
2 楼cngdzhang（）回复于 2004-05-02 18:22:22 得分 0
for (i=j; i<=m; i++)
if (a[i]<a[j])
{
temp=a[i]; a[i]=a[j]; a[j]=temp;
j++;
order (j,m); //这里要做m-j + m-j-1 + ... + 1次
}
令n=m-j
那么1+2+...+n = n(n-1)/2
所以时间复杂度为O(n*n)
Top
3 楼bshaozi（俺们那噶不学c！）回复于 2004-05-02 21:30:23 得分 0
对,时间复杂度是1+2+3+4+5+6+...+m=0(m*m)Top
4 楼eshowjow（Ж※★※Ж）回复于 2004-05-04 08:42:05 得分 0
我也想要点分啊^_^
1+2+3+……+n = n(n+1)/2
时间复杂度是0(n*n)Top
5 楼junnyfeng（风歌）回复于 2004-05-04 12:55:17 得分 0
哦，更正一点
n(n-1)/2是运行次数
时间复杂度是O（n^2)Top
6 楼chenqing1128（Alex）回复于 2004-05-04 13:34:12 得分 0
时间复杂度是O（n^2)Top
