算法的最坏时间复杂度

Question

最坏时间复杂度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)，也就是最坏时间复杂度。

- sara jons

Answer 1

这将是O(n^2)。

原因是您有一个嵌套在另一个for循环中的单个for循环。内部for循环的运行时间为O（n），每次迭代外部for循环时都会发生，而外部for循环本身也是O（n）。每个循环的复杂度单独为O(n)，因为它们根据输入的大小需要线性的时间。输入越大，所需的时间也线性增长，即n。

为了计算这个问题，这种情况下非常简单，只需将内部循环的复杂度乘以外部循环的复杂度。 n * n = n^2。因为请记住，对于外部循环中的每个n，您必须再次使用内部循环n次。澄清一下：每个n循环n次。

O(n * n)。

O(n^2)

- Nicholas Mancuso

---

是的。原子数据的赋值和交换是常数时间，因此它们不会增加任何复杂性+1。 - Johannes Schaub - litb

Answer 2

顺便提一句，你不应该混淆复杂度（用大O表示）和T函数。T函数是算法在给定输入时必须经过的步骤数。

因此，T(n)的值是实际步骤数，而O(某个值)表示复杂度。根据惯例，T(n) = O(f(n))意味着函数T(n)至多与另一个函数f(n)具有相同的复杂度，通常这将是其复杂度类的最简函数。

这很有用，因为它允许我们关注大局：我们现在可以通过比较两个可能具有非常不同的T(n)函数的算法来看它们“从长远来看”表现如何。

- harms

Answer 3

这里又出现了一个博士复读机回顾。

首先，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等人所著的《算法导论》。

- Charlie Martin

Answer 4

@莎拉·琼斯 您所引用的幻灯片集和其中的算法

在for循环中，正在为每个基本/原子操作测量复杂度。

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

这个循环的幻灯片评级为2n+2，原因如下：

初始设置j=0（+1操作）

j < n的比较（n次操作）

j++的增量（n次操作）

检查j < n的最终条件（+1操作）

其次，是for循环内部的比较。

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

这被评为n个操作。因此，如果您将+1操作、n个操作、n个操作、+1操作和n个操作相加，则结果为3n+2的复杂度。因此T(n)=3n+2。

请注意，T(n)与O(n)不同。

- LFSR Consulting

---

那么，如果我想解决第一个问题——选择排序，答案会是(2n+1)+(2n+1)+n = 5n+2吗？我是对的吗？ - Kevin Dente

@Sara，你说得不对。for循环是相乘而不是相加的。所以(2n+1)+(2n+1)应该写成(2n+1) * (2n+1)...如果你在寻找T(n)符号表示法，那么条件j = i+1会对T(n)符号表示法造成困扰。否则，你对O(n)符号表示法的理解接近了。请参考harm的答案。 - Gavin Miller

Answer 5

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

- vathany

Answer 6

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

- Parth Mehta