最坏时间复杂度t(n)是什么意思:
我正在阅读一本关于算法的书,以选择排序算法为例说明如何获取T(n)。
例如,如果我要处理选择排序(A[0..n-1]),
//sorts a given array by selection sort
//input: An array A[0..n - 1] of orderable elements.
//output: Array A[0..n-1] sorted in ascending order
让我写一个伪代码
for i <----0 to n-2 do
min<--i
for j<--i+1 to n-1 do
ifA[j]<A[min] min <--j
swap A[i] and A[min]
--------我也会用C#来编写---------------
private int[] a = new int[100];
// number of elements in array
private int x;
// Selection Sort Algorithm
public void sortArray()
{
int i, j;
int min, temp;
for( i = 0; i < x-1; i++ )
{
min = i;
for( j = i+1; j < x; j++ )
{
if( a[j] < a[min] )
{
min = j;
}
}
temp = a[i];
a[i] = a[min];
a[min] = temp;
}
}
现在我们来讲一下如何得到t(n),也就是最坏时间复杂度。