如何确定大O的复杂性，如果仅依赖于输入，而不是输入大小的值？

Question

我刚刚看到有关排序的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（时间复杂度）。

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), and setTimeout(100)，它将运行100台工作的（相对于180个单位的工作，这是在原来的职位的情况下）。

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

有趣的事实：出现这种情况有相同的复杂性Counting Sort，它的复杂性也是列表的大小和最大单值的函数