时间戳

首页 > 解决方案 > 如果 a 是整数数组且 n 是数组的长度，那么 O(sum(a)) 的总体 O(n) 时间复杂度是多少？

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

问题描述

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

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

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

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

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

标签： algorithmtime-complexitybig-o

解决方案

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

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

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

例如，对于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)). 这完全模糊了您在运行时测量的内容，因为您可以包括执行语句的成本，而不是 incrementing t。

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

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

推荐阅读