3

什么是最坏情况时间复杂度 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) 或众所周知的最坏情况时间复杂度

4

6 回答 6

13

那将是O（n ^ 2）。

原因是您有一个 for 循环嵌套在另一个 for 循环中。内部 for 循环的运行时间 O(n) 发生在外部 for 循环的每次迭代中，这也是 O(n)。每一个都是 O(n) 的原因是因为在给定输入的大小的情况下它们花费的时间是线性的。输入越大，线性比例 n 所需的时间就越长。

要计算出数学，在这种情况下是微不足道的，只需将内循环的复杂性乘以外循环的复杂性。n * n = n^2。因为请记住，对于外部循环中的每个 n，您必须再次为内部循环执行 n。澄清：每个 n 次。

O(n * n)。

O(n^2)

于 2008-12-01T16:22:10.320 回答
3

顺便说一句，您不应该混淆复杂性（用 big-O 表示）和 T 函数。T 函数是算法对于给定输入必须经过的步数。

因此，T(n) 的值是实际的步数，而 O(something) 表示复杂度。通过传统的符号滥用，T(n) = O( f(n) ) 意味着函数 T(n) 至多与另一个函数 f(n) 具有相同的复杂性，这通常是最简单的函数其复杂度等级。

这很有用，因为它使我们能够专注于全局：我们现在可以通过查看它们“从长远来看”的表现如何轻松比较两种可能具有非常不同的 T(n) 函数的算法。

于 2008-12-01T17:11:43.170 回答
1

@sara jons 您引用的幻灯片集 - 以及其中的算法

正在测量 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 ops。因此，如果您将 +1 op、n ops、n ops、+1 op、n ops = 3n+2 复杂度相加，则结果。所以 T(n) = 3n+2

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

    于 2008-12-01T17:02:02.800 回答
    1

    另一个博士复习在这里。

    首先，T 函数只是算法执行一项任务所需的时间量（通常在一些步骤中，下面会详细介绍）。什么是“步骤”，在某种程度上是由用途定义的；例如，通常计算排序算法中的比较次数，但计算搜索算法中搜索的元素数量。

    当我们谈论算法的最坏情况时间时，我们通常用“大 O 表示法”来表达。因此，例如，您听说冒泡排序需要 O(n²) 时间。当我们使用大 O 表示法时，我们真正想说的是某个函数的增长——在这种情况下是 T——并不比其他一些函数乘以常数的增长快。那是

    T(n) = O(n²)

    意味着对于任何n，无论多大，都有一个常数k，其中T(n) ≤ kn²。这里有一点令人困惑的是，我们以重载方式使用“=”符号：这并不意味着两者在数字意义上相等，只是我们说T(n)以 kn²为界.

    在您扩展问题的示例中，看起来他们正在计算 for 循环和测试中的比较次数；能够看到上下文和他们正在回答的问题会有所帮助。不过，无论如何，它说明了为什么我们喜欢大 O 表示法：这里的W(n)是O(n)。（证明：存在一个常数 k，即 5，其中W(n) ≤ k(3n)+2。由O(n)的定义得出。）

    如果您想了解更多相关信息，请查阅任何好的算法文本，例如Cormen等人的Introduction to Algorithms 。

    于 2008-12-01T18:31:15.723 回答
    0

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

    于 2009-10-02T08:36:50.240 回答
    0

    就循环而言，3n + 2 是正确的答案。在循环的每一步，都会完成 3 个原子操作。j++ 实际上是两个操作，而不是一个。和 j

    于 2010-09-12T18:21:31.930 回答