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

StackOverflow https://stackoverflow.com/questions/331295

题

最糟糕的情况时间复杂性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) 或已知的最坏情况时间复杂度

有帮助吗？

解决方案

@萨拉·琼斯 您引用的幻灯片集以及其中的算法

正在测量 for 循环中每个原语/原子操作的复杂性

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

幻灯片将此循环评为 2n+2，原因如下：

  • 初始集合j=0(+1 op)
  • j < n (n ops) 的比较
  • j++ 的增量（n 次操作）
  • 检查 j < n (+1 op) 的最终条件

    • 其次，for循环内的比较 

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

    这被评为 n 次操作。因此，如果将 +1 op、n ops、n ops、+1 op、n ops = 3n+2 复杂度加起来，结果就是这样。所以 T(n) = 3n+2

    认识到 T(n) 与 O(n) 不同。

    其他提示

    这将是为O（n ^ 2）。

    的原因是你有循环嵌套在另一个for循环的单个。的运行时间内for循环中，为O（n），发生用于外部for循环，而这又是O（n）的每一次迭代。之所以每个这些独立地是O（n）是因为它们采取给定了输入的大小的时间的线性量。较大输入的时间越长，以线性标度中，n

    要由外部循环的复杂性制定出数学，在这种情况下是微不足道的，只是多个内部环路的复杂性。 N * N = N ^ 2。因为记得，在外环每个n，则必须再次做了内n-。为了澄清：n次的每个n。

    O（N * N）。

    为O（n ^ 2）

    顺便说一句，你不应该混淆的复杂性（由大O表示）和T功能。 T功能是步数的算法要经过一个给定的输入。

    因此，T（n）的值是实际步数，而O（东西）表示的复杂性。由符号的常规滥用，T（N）= O（F（N））表示函数T（n）是至多相同的复杂作为另一函数f（n），其通常将是最简单的可能的功能其复杂性类。

    这是有用的，因为它使我们能够专注于大局：现在，我们可以轻松地比较，可能有两种算法非常不同的前瞻性通过观察他们的表现如何T（n）的功能，“从长远来看，” <。 / p>

    另一个博士-COMP倒叙这里。

    首先，将T功能只是时间的量（通常是在一些数量的步骤，对此下文）的算法花费执行任务。什么是“步骤”，在一定程度上通过使用定义;例如，这是常规的计数在排序算法比较的次数，但在搜索的搜索算法的元素数。

    当我们谈论一个算法的最坏情况的时候，我们通常表示，随着“大O符号”。因此，例如，你听到冒泡排序需要O（N²）时间。当我们用大O表示法，我们真正想说的是，一些功能的增长 - 在这种情况下，笔 - 没有快于其他一些功能一直以一定的增长。也就是说

    T（N）= O（N²）

    装置，用于任何名词的，无论是大，有一个恒定的ķ为其 T（n）的≤kn²。这里有些confustion的一点是，我们正在使用的“=”号在重载时尚：这并不意味着两者的等的在数值意义，只是我们是在说< EM> T（n）的是通过kn²

    在你的延伸问题的例子，它看起来像他们在for循环和在测试计数的比较的数量;这将有助于能够看到的背景和他们回答这个问题。在任何情况下，虽然，它说明了为什么我们喜欢大O符号： W（N）的这里的 O（N）的。 （证明：存在一个常数k，即如图5所示，其 W（n）的≤K（3N）2它遵循由定义的 O（n）的。 。）

    如果您想了解更多关于这一点，请教有什么好的算法的文字，例如，的算法导论时，由Cormen 等人

    写入伪码进行搜索，插入和删除从哈希表中的学生信息。计算出最佳和最坏情况下的时间复杂度

    3N + 2是正确的答案只要环路而言。在循环的每一步，3个原子操作完成。 J ++实际上是两个操作，没有之一。和j     

    许可以下： CC-BY-SA 和 归因
    不隶属于 StackOverflow
    scroll top