algorithm - 如果 a 是整数数组且 n 是数组的长度，则 O(sum(a)) 的总体 O(n) 时间复杂度是多少？

Question

我很难使用 O(n) 原则来概括算法的时间复杂度，其更具体的时间复杂度为 O(sum(a))，其中 a 是整数数组。

我的直觉是，这个时间复杂度应该概括为 O(n)，因为您可以将其视为出现 n 次的 ki 值的“线性”方程，其中 k 是数组中的整数值，使其成为 O( n)( 对于直接的 O(n) 情况，k=1)。

但它似乎与 O(n) 并不完全相同——k 的值可能比 n 大得多，如果所有这些 k 值都更大，那么你有可能是 O(n^2 ) 或 O(n^3) 取决于该值的大小。

这是否需要考虑 O(n) 的复杂性，其中 n 是数组的长度？我真的应该将 n 定义为数组中所有元素的总和而不是数组的长度吗？

一般来说，考虑这个问题的最佳方式是什么？

Answer 1

从根本上说，我们想要描述基于输入的算法的运行时间。 “运行时”是一个模糊的术语，经常被掩盖。例如，排序算法或哈希表操作的“运行时间”以比较次数来衡量，但使用“运行时间”来表示基本操作的次数(通常也只是模糊定义)也是可能的。

在计算运行时时，通常会做出两种选择(或简化)。第一种是忽略实际输入，而是使用输入的大小(以某种方式测量)。此大小通常表示为 n。第二种，是用大 O 表示法来描述最坏情况(或最好情况，或平均值，或摊销...)。

这些选择都不是总是必要的，有时，它们也没有意义。重复一遍，因为这是答案的症结所在:在 n 的大 O 中描述运行时并不是描述运行时的唯一方法，有时这样做没有意义。

例如，对于在 O(sum(a)) 时间内运行的算法:

func f(a) {
   t = 0
   for x in a {
      for i = 1..x {
         t += 1
      }
   }
}

使用输入数组 a 的长度来描述它的运行时间是没有用的。它没有用，因为 a 的长度没有说明最坏情况下的运行时间。

说 t 递增 sum(a) 次 是关于程序运行时间的有用声明。它不使用大 O 复杂性表示法。

如果您确实想用大 O 表示法表示，您可以说这段代码的运行时间是 O(sum(a))。这模糊了您在运行时测量的确切内容，因为您可以包括执行语句的成本，而不是递增 t。

回到这个例子，你可以(如果你正在研究复杂性类，你可能会)说n是输入数组的大小(以位为单位)。然后你可以说说运行时(在基本操作中测量):它是 O(2^n)，因为最坏的情况输入是一个数组，其中一个元素的值为 2^n-1(*注)。

*注意:这忽略了有关如何使用位对数组进行编码的一些技术细节。