如果仅取决于输入值而不是输入大小，如何确定 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

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 是给定列表的最大值，无论如何多次被调用。

在原来的 post 中，我假设 setTimeout() 会对列表中的每个项目运行 n 次，但是这个逻辑有点缺陷，因为setTimeout() 概念上 "caches" 以前的值，所以如果用 setTimeout(30), setTimeout(50), and setTimeout(100) 调用它，它将运行 100 个工作单位（而不是 180 个工作单位，情况是在原来的 post).

给定 setTimeout() 的新 "cached" 解释，复杂度为 O(k + n)，其中 k 是长度列表中的最大值，n 是列表中的最大值。

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

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

How to determine Big-o complexity if it only depends on values of input rather than input size?

javascript

complexity-theory

big-o

time-complexity