分析程序段的时间复杂度

我们假设执行每一基本步骤所需要的时间为一常量，第i步的执行时间可以用ci来表示，这样一来，如果知道每一行会被执行多少次就能知道每一行的执行时间
根据你的函数，可以设n=m-j，这就是输入规模，每一行执行时间按照c1，c2，c3，……来表示，下面的代码执行的基本时间和每行语句执行的次数可以表示如下：（值得注意的是，循环中for和while行的语句会多执行一次，因为要判断不能进入循环的那一个量）
用T（n）表示某个函数彻底完成的执行时间，意味着递归调用知道最后结果出来才算是彻底完成
                                    基本时间               次数
int a[]={10,2,9,7,3,6,4,1}            c1                    1
order(int j,int m)                    T（n)        
{
    int i,temp;                       c2                    1
    if(j<m)                           c3                   1
    {
        for(i=j+1;i<=m;i++)           c4                    n+1
            if(a[i]<a[j])             c5                    n
            {
               temp=a[i];             c6                    n
               a[i]=a[j];             c7                    n
               a[j]=temp;             c8                    n
             }
        j++;                          c9                    1
        order(j,m);                   T(n-1)
     }
}

这样，函数order的执行时间就可以表示为
T(n)=T(n-1)+(c2+c3+c4+c9)+(c4+c5+c6+c7+c8)n
用渐近式表示为T(n)=T(n-1)+O(n)的时间，其中O(n)表示为an+b的时间关系
递推T(n)式可以得到
T(n-1)=T(n-2)+O(n-1）
T(n-2)=T(n-3)+O(n-2)
可以看出，如果n的值非常大的话，O(n-1)和O(n)没多大区别，所以T(n)的时间复杂度可以表示为O(n^n)，n的n次方的时间复杂度，在大数据量的情况下实在是不可取