如果只依赖于输入值而不是输入大小,如何确定Big-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

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

\n\n\n\n

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

\n\n

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

\n\n

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

\n\n

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

\n\n

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

\n\n

总而言之，该算法的复杂度为O(k * n)，其中k是给定数字的长度，n是列表中的最大值。

\n\n

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

\n\n

\n
• 我们的算法需要更长的时间，因为我们给它的数字越多 \xe2\x9c\x93
\n
• 当我们给它更大的数字 \xe2\x9c\x93 时，我们的算法需要更长的时间
\n

\n\n

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

\n\n\n\n

编辑：

\n\n

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

\n\n

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

\n\n

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

\n\n

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

\n