时间戳

首页 > 解决方案 > 如果它仅取决于输入值而不是输入大小，如何确定 Big-o 复杂度？

javascript - 如果它仅取决于输入值而不是输入大小，如何确定 Big-o 复杂度？

问题描述

我刚刚看到了关于排序的javascript代码setTimeout，如图所示

var list = [2,  5, 10, 4, 8, 32]; 
var result = [];
list.forEach( n => setTimeout(() => result.push(n), n));

这很有趣，因为在 jssetTimeout中是异步的，所以如果你等待足够的时间，result就会对数组进行排序。它是确定性的，仅取决于数据的值，而不取决于输入的大小，所以我不知道如何确定这种方法的 Big-O（时间复杂度）。

标签： javascripttime-complexitybig-ocomplexity-theory

解决方案

TLDR；这取决于你如何定义复杂性setTimeout()

在讨论算法复杂性时，我们必须回答以下问题：

  • 我的输入是什么？
  • 我的算法运行的假设机器中的工作单元是什么？

在某些情况下，我们如何定义输入取决于算法在做什么以及我们如何定义我们的工作单元。使用内置函数时问题很复杂，因为我们必须定义这些函数的复杂度，以便我们可以将它们考虑在内并计算算法的整体复杂度。

的复杂度是setTimeout()多少？这有待解释。我发现给出setTimeout()的复杂度很有帮助O(n)，其中n是传递给函数的毫秒数。在这种情况下，我决定内部计算的每一毫秒setTimeout()代表一个工作单位。

鉴于它setTimeout()具有复杂性O(n)，我们现在必须确定它如何适应我们算法的其余部分。因为我们正在循环list调用setTimeout()列表的每个成员，所以我们乘以n另一个变量，让我们调用它k来表示列表的大小。

综上所述，该算法具有复杂性O(k * n)，其中k是给定数字的长度，并且n是列表中的最大值。

这种复杂性有意义吗？让我们通过解释我们的分析结果来进行健全性检查：

  • 我们的算法需要更长的时间，因为我们给它更多的数字✓</li>
  • 我们的算法需要更长的时间，因为我们给它更大的数字 ✓</li>

请注意，这个结论的关键是确定 的复杂性setTimeout()。如果我们给它一个恒定的O(1)复杂性，我们的最终结果将是O(k)，IMO 具有误导性。

编辑：

也许对所有输入setTimeout()的贡献更正确的解释是给定列表的最大值，无论它被调用多少次。O(n)n

在原始帖子中，我假设列表中的每个项目setTimeout()都会运行时间，但是这个逻辑在概念上“缓存”以前的值有一点缺陷，所以如果用 调用它，它将运行 100 个工作单元（如反对 180 个工作单元，这是原始帖子中的情况）。nsetTimeout()setTimeout(30), setTimeout(50), and setTimeout(100)

鉴于对 的这种新的“缓存”解释setTimeout()，复杂度为O(k + n)，其中k是列表的长度，并且n是列表中的最大值。

有趣的事实：这恰好与Counting Sort 具有相同的复杂性，其复杂性也是列表大小和最大列表值的函数

推荐阅读