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

Question

我刚刚看到关于使用 setTimeout 进行排序的 javascript 代码，如图所示

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

这很有趣，因为在 js 中 setTimeout 是异步的，所以如果您等待足够的时间，result 将是排序数组。它是确定性的，仅取决于数据值而不是输入的大小，所以我不知道如何确定这种方法的 Big-O(时间复杂度)。

Answer 1

TLDR； 这取决于您如何定义 setTimeout()

的复杂性

---

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

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

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

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

鉴于 setTimeout() 的复杂度为 O(n)，我们现在必须确定它如何适合我们算法的其余部分。因为我们正在遍历 list 并为列表的每个成员调用 setTimeout()，所以我们将 n 与另一个变量相乘，我们称它为 k 表示列表的大小。

综合起来，该算法的复杂度为 O(k * n)，其中 k 是给定数字的长度， n 是列表中的最大值。

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

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

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

---

编辑:

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

在原来的帖子中，我假设 setTimeout() 会为列表中的每个项目运行 n 次，但是这个逻辑有一点缺陷，因为 setTimeout() 在概念上“缓存”以前的值，因此如果使用 setTimeout(30)、setTimeout(50) 和 setTimeout(100) 调用它，它将运行 100 个单位工作(与原始帖子中的 180 个工作单位相反)。

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

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