我刚看到有关排序的javascript代码,如图所示使用setTimeout
var list = [2,5,10,4,8,32];
var result = [];
list.forEach( n => setTimeout(() => result.push(n),n));
这很有意思,因为在js中setTimeout是异步的,所以如果你等待足够的时间,结果将被排序数组.确定性仅取决于数据的值而不取决于输入的大小,所以我不知道如何确定这种方法的Big-O(时间复杂度).
在讨论算法复杂性时,我们必须回答以下问题：
>我的意见是什么？
>我的算法运行的假想机器中的工作单元是什么？
在某些情况下,我们如何定义输入取决于算法正在做什么以及我们如何定义我们的工作单元.使用内置函数时问题很复杂,因为我们必须定义这些函数的复杂性,因此我们可以将它们考虑在内并计算算法的整体复杂性.
setTimeout()的复杂性是什么？这就是解释.我发现给setTimeout()一个复杂的O(n)很有帮助,其中n是传递给函数的毫秒数.在这种情况下,我决定由setTimeout()内部计算的每毫秒代表一个工作单元.
鉴于setTimeout()具有复杂度O(n),我们现在必须确定它如何适应我们算法的其余部分.因为我们循环遍历列表并为列表的每个成员调用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相同的复杂性,其复杂性也是列表大小和最大列表值的函数
