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

Question

如果算法:

如何定义计算复杂度:

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

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

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

_{让我对此感到困惑的问题是: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) 的时间。至少如果它立即返回元素。如果多次调用该算法以一次获得一个元素的结果，则规定的时间复杂度可能与每个元素的时间有关。 Amortized Complexity在这些情况下可能会有所帮助。例如，union-find data structure每个操作的摊销时间复杂度为 O(alpha(n))。空间复杂度通常不包括存储结果的空间。但同样，这应该从上下文中清楚。

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