许多答案或多个参数情况下的计算复杂度

Question

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

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

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

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

_{让我疑惑的问题是：Unique (non-repeating) random numbers in O(1)?, How do you efficiently generate a list of K non-repeating integers between 0 and an upper bound N, Algorithm to select a single, random combination of values?, Efficiently selecting a set of random elements from a linked list.}

Answer 1

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

你说得对，一个算法在返回 k 个元素时至少需要 O(k) 的时间。至少如果它 returns 元素一次。如果多次调用该算法以一次获得一个元素的结果，则规定的时间复杂度可能与每个元素的时间有关。 Amortized Complexity may help in these cases. For example, the union-find data structure 每个操作的分摊时间复杂度为 O(alpha(n))。 Space 复杂度通常不包括 space 来存储结果。但同样，这应该从上下文中清楚。

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

Answer 2

根据the answer at CS.SE：

• 时间复杂度和space复杂度应分别报告每个变量：“O(k)和O(n) 次，O(1) space”。
  • 如果 time/space 不依赖于某些变量但不是全部，这可以用纯文本或类似 O(n⁰ ) 为简洁起见（这里没有通用约定）
• 结果是最后返回还是一个一个返回，通过算法的引用体现为流式（在线）（一个一个）还是batch（全部在最后）
  • 对于流式算法，其延迟也可以描述为：

    For instance, a O(log n) delay algorithm returns results one at a time, taking at most O(log n) steps (running time) to output each result.