java - 我如何知道算法是在 O(n) 时间内运行还是在 O(nlogn) 内运行？

Question

<分区>

Answer 1

好吧，这是我的第一个答案......

算法的 O() 表示法(尽管它可以应用于任何函数)有点像算法增长率的上限。您可能关心的情况是与您的算法针对给定输入大小执行的操作次数相关的函数。你似乎在要求一个循序渐进的方法，所以我会尝试一个:

1. 编写一个函数，描述您的算法对 n 个输入大小(或 n 个元素的现有数据结构等)执行的最坏情况下的操作数。

2. 使用大 O 符号的定义简化该函数。大多数时候这是非常简单的；然而，有些情况需要理解数学形式和大 O 的真正含义。我不会在这里深入讨论，因为教科书或您的 CS 教授来解释会更好。忽略细节，您将项(如果它是项的总和)保留在增长最大的函数中并摆脱其他所有内容。如果该项有任何常数系数，也将它们去掉。例如:f(n) = 4n^2 + 10000n + 500 将以前面描述的方式修改为 n^2，因为 4n^2 项比其他两项增长得更快，并且 4 的系数被丢弃；留下 n^2。

举个例子: 假设 List 是一个数字数组，lSize 是数组中的项目数。

for (int i=0; i < lSize; ++i){
  for (int j = i+1; j<=lSize; ++j){
    if (List[i] > List[j]){ //swap the elements
      int temp = List[i];
      List[i] = List[j];
      List[j] = temp;
    }
   }
}

让我们计算一下使用上面显示的选择排序算法对 n 个项目的列表进行排序所需的操作数。

第一步

对于大小为 n 的列表，此算法需要进行多少次排序操作(以 n 表示)？这里 lSize 取 n 的值。我们有两个 for 循环，一个嵌套在另一个循环中。外层循环很简单，它对 List 中的每个元素执行一次；或n次。在该循环内是另一个 for 循环，其操作次数并不立即那么明显。此循环的迭代次数取决于外部 for 循环中 i 的当前值。如果您坐下来接受一些测试值并写出出现的系列，您会看到内部循环首先运行 n 次，然后运行 ​​(n-1) 次，然后运行 ​​(n-2) 次，依此类推，描述的总计数: n + (n-1) + (n-2) ... 2 + 1。您会注意到这是从 1 到 n 的所有数字的总和。如果 n = 100，则内循环的总迭代次数将为 100 + 99 + 98 + 97 ... 2 + 1。这是一个算术级数，可以将 n 项简化为:n*(n- 1)/2。那是对内部循环内的操作进行评估的次数。由于内部循环中有 3 个操作，这意味着 n 项的操作总数为 3 * n*(n-1)/2。以下一部分更容易的形式重写，(3/2)n^2-(3/2)n。

第二步

我们现在有我们的功能。其中 f() 是我们的算法 f(n) = (3/2)n^2-(3/2)n 执行的操作数。显然，增长最快的项是 (3/2)n^2，所以我们去掉 (3/2)n。这留下 (3/2)n^2 我们摆脱了 (3/2) 系数。这留下 n^2。因此，我们可以说 f(n) 是 O(n^2)。

这基本上是用 O() 表示法描述算法的秘诀。这忽略了重要的原因，并描述了产生答案的无脑秘诀。为什么要这样总结算法？为什么可以忘记一个项或系数？这些问题的答案可以在更严格的教科书描述中找到。

我希望我没有犯任何可怕的错误，现在有点晚了。