最坏情况下的时间复杂度的算法 [英] Worst Case Time Complexity for an algorithm

问题描述

什么是最坏情况下的时间复杂度T（N）： - 我在读这本书的算法和作为一个例子 如何获得T（N）的....喜欢选择排序算法

What is the Worst Case Time Complexity t(n) :- I'm reading this book about algorithms and as an example how to get the T(n) for .... like the selection Sort Algorithm

---

一样，如果我的selectionSort处理（A [0到n-1]）

Like if I'm dealing with the 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

让我写一个伪code

let me write a pseudocode

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＃中太---------------

--------I will write it in C# too---------------

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）或它的已知的最坏情况下的时间复杂度

Now how to get the t(n) or as its known the worst case time complexity

推荐答案

@ <一href="http://stackoverflow.com/questions/331295/worst-case-time-complexity-for-an-algorithm/331380#331380">sara JONS <一href="http://www.sy-stu.com/stu/PublicFiles/StdLibrary/L_15_Design_and_analysis_of_Algorithms_DA_Algorithms_04.ppt"相对=nofollow>您已经引用的幻灯片组 - 和算法其中

的复杂性被测量为在每个基本笔划/原子操作为环

The complexity is being measured for each primitive/atomic operation in the for loop

for(j=0 ; j<n ; j++)
{
    //...    
}

载玻片评论这个循环为2n + 2的原因如下：

The slides rate this loop as 2n+2 for the following reasons:

在初始设置的J = 0（+1 OP）

J＆所述的比较; N（N OPS）

的J ++的增量（N OPS）

的最后一个条件，以检查是否J＆LT; N（+1 OP）

其次，对于循环中的比较

Secondly, the comparison within the for loop

if(STudID == A[j])      
    return true;

这是额定为N欢声笑语。因此，如果添加了+1操作，正OPS，正OPS，+1运，N OPS = 3N + 2的复杂性造成的。因此，T（N）= 3N + 2

This is rated as n ops. Thus the result if you add up +1 op, n ops, n ops, +1 op, n ops = 3n+2 complexity. So T(n) = 3n+2

认识到T（n）是不一样的O（N）。

Recognize that T(n) is not the same as O(n).

这篇关于最坏情况下的时间复杂度的算法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！