我刚刚看到了关于排序的javascript代码，它使用setTimeout，如所示
var list = [2, 5, 10, 4, 8, 32];
var result = [];
list.forEach( n => setTimeout(() => result.push(n), n));
这很有趣，因为在js中，setTimeout是异步的，所以如果您等待足够的时间，result将被排序为数组。它是确定性的，只取决于数据的值，而不取决于输入的大小，所以我不知道如何确定这种方法的Big-O(时间复杂性)。
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), and setTimeout(100)调用它，它将运行100个工作单位(而在最初的帖子中是180个工作单位)。
给定setTimeout()的这种新的"缓存"解释，复杂性为O(k+n)，其中k是列表的长度，n是列表中的最大值。
有趣的事实：这恰好与计数排序具有相同的复杂性，其复杂性也是列表大小和最大列表值的函数