算法的最坏情况时间复杂度

Question

什么是最坏情况时间复杂度t(n): - 我正在读这本关于算法的书,作为一个例子,如何得到T(n)......就像选择排序算法一样

---

就像我正在处理selectionSort(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)或已知的最坏情况时间复杂度

Answer 1

那将是O(n ^ 2).

原因是你有一个for循环嵌套在另一个for循环中.内部for循环的运行时间O(n)发生在外部for循环的每次迭代中,也是O(n).这些中的每一个单独为O(n)的原因是因为它们在给定输入的大小的情况下花费线性时间量.输入越大,线性刻度所需的时间越长,n.

为了计算数学,在这种情况下是微不足道的,只需要通过外部循环的复杂性来复制内部循环的复杂性.n*n = n ^ 2.因为记住,对于外循环中的每个n,你必须再次为内部做n.澄清:每n个n次.

O(n*n).

为O(n ^ 2)