16

假设我们有一个包含 1.000.000 个元素的数组，我们遍历所有元素以检查一些简单的内容，例如第一个字符是否为“A”。根据我（很少）的理解，复杂性将是O(n)并且需要一些 X 时间。如果我添加另一个 IF（不是 else if）来检查，假设最后一个字符是“G”，它将如何改变复杂性？它会使复杂性和时间加倍吗？喜欢O(2n)和2X？

我想避免考虑不同命令必须进行的计算数量。例如，我知道 Len() 比简单的 char 比较需要更多的计算才能给我们结果，但是假设 IF 中使用的命令将具有（几乎）相同的复杂性。

4

4 回答 4

19

O(2n) = O(n). 概括, O(kn) = O(n),k是一个常数。当然，使用两个 IF 可能需要两倍的时间，但执行时间仍然是输入大小的线性函数。

编辑：这里和这里是不太面向数学的大 O 符号的解释和示例

于 2013-06-04T12:37:42.960 回答
6

渐近复杂度（这是 big-O 使用的）不依赖于常数因子，更具体地说，您可以在函数中添加/删除任何常数因子，并且它将保持等效（即 O(2n) = O(n) ）。

假设一个 if 语句花费的时间是固定的，它只会给复杂性增加一个固定的因素。

“恒定的时间”是指：

  • 给定元素的 if 语句所花费的时间不取决于数组中有多少其他元素
  • 因此，基本上，如果它不调用以某种方式或类似方式查看数组中其他元素的函数
  • 任何非函数调用 if 语句都可能没问题（除非它包含通过数组的语句，某些语言允许这样做）

因此，为每个元素调用的 2 个（恒定时间）if 语句将是 O(2n)，但这等于 O(n)（嗯，它可能实际上不是 2n，更多内容在附加说明中）。

有关更多详细信息和更正式的定义，请参阅Wikipedia 。

注意：除了不依赖于常数因子之外，它也不依赖于渐近较小的项（无论 n 有多大，这些项都保持较小），例如 O(n) = O(n + sqrt(n))。而且 big-O 只是一个上限，所以说它是 O(n 9999 ) 也是正确的（尽管说在测试/考试中可能会给你 0 分）。

附加说明：不忽略常数因素时的问题是 - 什么归类为工作单元？这里没有标准定义。一种方法是使用耗时最长的操作，但确定这一点可能并不总是直截了当，也不会总是特别准确，您也无法笼统地比较不同算法的复杂性。

于 2013-06-04T12:40:47.570 回答
0

关于时间复杂度的一些关键点：

  1. Theta 表示法- 精确界限，因此如果我们正在分析的一段代码包含条件 if/else 并且任一部分有更多的代码根据输入大小增长，则无法获得精确界限，因为可能采用任一分支并且对于这种情况，不建议使用 Theta 表示法。另一方面，如果两个分支都解析为恒定时间码，那么在这种情况下可以应用 Theta 表示法。
  2. 大 O 表示法- 上限，因此如果代码具有条件，其中任何一个条件分支都可能随着输入大小 n 增长，那么我们假设最大值或上限来计算代码的时间消耗，因此我们对此类条件使用大 O假设我们走的是时间消耗最大的路径。因此，在摊销分析中可以假设具有较短时间的路径为 O(1)（包括我们假设该路径没有可能随输入大小增长的递归这一事实）并计算最长路径的时间复杂度 Big O .
  3. Big Omega notation - 下限，这是一段代码可以花费的最小保证时间，而与输入无关。对于代码所花费的时间不会根据输入大小 n 增长但会消耗大量时间 k 的情况很有用。在这些情况下，我们可以使用下限分析。

注意：所有这些符号都不取决于输入是最好/平均/最差，所有这些都可以应用于任何一段代码。

因此，如上所述，Big O 不关心诸如 k 之类的常数因素，而只看到时间如何随着 n 的增长而增加，在这种情况下，它是 O(kn) = O(n) 线性的。

PS：这篇文章是关于大O和条件评估标准的关系摊销分析。

于 2021-06-14T18:31:43.393 回答
-2

这与我今天发布的一个问题有关。

在您的示例中，这取决于您是否可以从第一个元素跳转到最后一个元素，如果不能，则还取决于每个条目的平均长度。

如果您在遍历数组时必须阅读每个完整条目以评估您的两个 if 语句，那么您的订单将是 O(1,000,000xN)，其中 N 是每个条目的平均长度。如果 N 是可变的，那么它将影响顺序。一个例子是标准乘法，我们对一个长度为 Log(N) 的条目执行 Log(N) 加法，因此顺序为 O(Log^2(N)) 或者如果您更喜欢 O((Log(N) )^2)。

另一方面，如果您可以只检查第一个和最后一个字符，则 N = 2 并且是常数，因此可以忽略。

这是一个重要的点，你必须小心，因为你如何决定你的倍数是否可以被忽略。例如，假设我们正在对 Log(N/100) 数进行 Log(N) 加法。现在仅仅因为 Log(N/100) 是较小的术语并不意味着我们可以忽略它。如果乘数是可变的，则不能忽略它。

于 2013-06-04T12:55:59.123 回答