关于#算法#的问题，如何解决？

Question

试分析以下程序的时间复杂度O(), 即当输入个数不是7而是很大时的时间代价，给出具体分析的依据和过程，并指出最差的情况.

#include "stdafx.h"

#include <stdio.h>

void qst(int s[], int l, int r) {   

int i, j, x;   

if (l < r)    {       

i = l;        j = r;        x = s[i];       

while (i < j)        {

          while(i < j && s[j] > x)     j--; /* 从右向左找第一个小于x的数 */           

if(i < j)   s[i++] = s[j];                   

while(i < j && s[i] < x)     i++; /* 从左向右找第一个大于x的数 */           

if(i < j)   s[j--] = s[i];        

}       

s[i] = x;       

qst(s, l, i-1); /* 递归调用 */       

qst(s, i+1, r);   

}

} 

int _tmain(int argc, _TCHAR* argv[]) {

          int a[]={49,38,65,97,76,13,27};  

int l = 0;

int r = 6;              

qst(a, l, r);      

for (int i=0; i<=r; i++)       printf ("%4d", a[i]);         

return 0;

}

Answer 1

这段程序实现了快速排序算法，它的时间复杂度为O(nlogn)，其中n为输入元素的数量。下面是具体分析过程：

在最优情况下，即每次划分都刚好分为两半，快排算法的时间复杂度为O(nlogn)。在最差情况下，即待排序数组已经有序或接近有序，每次划分只能将序列分成一个元素和n-1个元素，此时算法的时间复杂度退化为O(n^2)。

快排算法的时间复杂度分析主要基于划分操作的次数，因为每次划分操作能够将一个元素放到其最终位置上，而这个位置的索引可以被看作是一个基准元素的索引，因此每次划分后都可以将待排序数组分成两个子数组，递归处理子数组的过程可以看作是树形结构，其高度取决于树的深度，而树的深度又决定了划分操作的次数。

在这个程序中，每次划分的过程都需要遍历整个数组，所以其时间复杂度为O(n)，而该算法最多需要划分logn次，因此总时间复杂度为O(nlogn)。但是如果待排序的数组已经有序或接近有序，每次划分只能将序列分成一个元素和n-1个元素，此时算法的时间复杂度退化为O(n^2)。

需要注意的是，这段程序中的快排算法是用递归实现的，如果待排序数组的长度很大，递归的过程可能会导致栈溢出，因此可以使用非递归实现的快排算法来避免这个问题。