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 回答