1

如果算法：如何定义计算复杂度：

  • ...产生许多结果？作为一个总数（那么产生一组的算法k不能比O(k)快）或每个元素（那么必须将估计值相乘以将其与不产生集合的算法进行比较）？
    • 存储复杂性如何——估计是否反映了整个集合是否需要一次出现在内存中，或者每个连续元素都可以产生和丢弃？
  • ...有多个参数？每个参数的单独数字或组合的数字？

适合这两种情况的示例是k从 中选择元素N。例如，根据是否需要~k或~N需要步骤，估计是否存在差异？

我希望看到一些确凿的证据：这些案例中术语的正式定义和/或如何在 CS 论文中消除这些歧义，而不仅仅是随机的想法和/或个人经验。目标是制定一个完整的、最先进的解决方案，以一劳永逸地消除我（和其他人）文本中的这些歧义。

让我对此感到困惑的问题是：O(1) 中的唯一（非重复）随机数？,你如何有效地生成一个介于 0 和上限 N 之间的 K 个非重复整数的列表，用于选择单个值的随机组合的算法？,有效地从链表中选择一组随机元素。

4

2 回答 2

1

这些问题通常通过上下文来回答。

你是对的，一个算法在返回 k 个元素时至少需要 O(k) 时间。至少如果它一次返回元素。如果多次调用该算法以一次获得一个元素的结果，则所述时间复杂度可能与每个元素的时间有关。在这些情况下，摊销复杂性可能会有所帮助。例如，union-find 数据结构的每个操作的分摊时间复杂度为 O(alpha(n))。空间复杂度通常不包括存储结果的空间。但同样，这应该从上下文中清楚。

对于多个参数（或其他自变量或因变量），复杂性通常在单个表达式中说明。例如，查询区间树需要 O(n + m) 时间，其中 n 是树中元素的数量，m 是返回元素的数量。其他变量可能包括数据分布或其他特征。

于 2016-09-09T23:24:06.243 回答
0

根据CS.SE 的回答：

  • 时间复杂度和空间复杂度应分别为每个变量分别报告：“ O(k) and O(n) time, O(1) space”。
    • 如果时间/空间不依赖于某些变量但不是全部，则可以用纯文本或类似O(n 0 )的方式来说明，为简洁起见（这里没有通用约定）
  • 到底是全部返回还是一个一个返回，体现在算法是流式（在线）（一个一个）还是批处理（都在最后）
    • 对于流式算法，它的延迟也可以描述为：

      例如，O(log n)延迟算法一次返回一个结果，最多需要O(log n)步（运行时间）来输出每个结果。

于 2017-01-20T12:09:58.967 回答