quintic's recent timeline updates quintic's recent timeline updates |
quinticV2EX member #219564, joined on 2017-03-08 05:59:12 +08:00 |
quintic's recent replies
May 12, 2018 Replied to a topic by cairnechen › JavaScript › 阮一峰老师又被人怼了，这次是关于 JavaScript 的快速排序实现 |
@20015jjw 不是，朋友，阮写的是对的，复杂度是 n log n 不是 n 方，是你搞错了。
实测的支持你可以看我的回复 145 楼（如果是 n 方，n 每乘 2，时间应该乘 4，但实际是 2 ）
分析的话是这样：splice 是要过一遍数组，但是是传到那个函数调用的 arr，不是大的 arr，所以他只是多过了一遍当前区域的 arr 而已，而快排本来就要过一遍当前区域来筛出小的和大的，所以这里损耗的是一个常数（一遍和两遍的区别，你看原文给出的数据也是 5 秒 vs 10 秒，就是差一个常数 2 ）
很奇怪怎么会吵了一百多楼还没搞清楚……
实测的支持你可以看我的回复 145 楼（如果是 n 方，n 每乘 2，时间应该乘 4，但实际是 2 ）
分析的话是这样：splice 是要过一遍数组，但是是传到那个函数调用的 arr，不是大的 arr，所以他只是多过了一遍当前区域的 arr 而已，而快排本来就要过一遍当前区域来筛出小的和大的，所以这里损耗的是一个常数（一遍和两遍的区别，你看原文给出的数据也是 5 秒 vs 10 秒，就是差一个常数 2 ）
很奇怪怎么会吵了一百多楼还没搞清楚……
May 12, 2018 Replied to a topic by cairnechen › JavaScript › 阮一峰老师又被人怼了，这次是关于 JavaScript 的快速排序实现 |
我觉得作者可能没弄清楚*渐进*复杂度的意思：只测一个点的速度没有任何意义，要看 N 趋近无穷时的渐进行为。
删掉文中 const arr = []一行代码，我们生成若干长为二的幂次的数组并测试，
for (var i = 12; i <= 24; ++i) {
arr = [];
generateArr( Math.pow(2, i) );
console.time('N = 2^' + i);
quickSort(arr);
console.timeEnd('N = 2^' + i);
}
我得到的运行时间如下：
N = 2^12: 8.030029296875ms
N = 2^13: 5.56005859375ms
N = 2^14: 9.332763671875ms
N = 2^15: 20.909912109375ms
N = 2^16: 38.673828125ms
N = 2^17: 89.992919921875ms
N = 2^18: 187.841064453125ms
N = 2^19: 321.177001953125ms
N = 2^20: 683.663818359375ms
N = 2^21: 1461.80908203125ms
N = 2^22: 3129.0927734375ms
N = 2^23: 6694.160888671875ms
N = 2^24: 14762.876953125ms
可以看到，从 2 的 14、15 次方开始（约一万），数据规模每乘 2，运行时间也乘 2 左右，符合 N log N 在 N 趋近无穷时的增长速度（ lim n->inf (2N log 2N) / (N log N) = 2 * lim (log 2 + log N) / log N = 2 * 1 = 2 )
因此，阮一峰的实现达到了快排的渐进时间复杂度，没有问题。（其实我个人偏好这种损失一定常数，但保证简洁正确的写法）
删掉文中 const arr = []一行代码，我们生成若干长为二的幂次的数组并测试，
for (var i = 12; i <= 24; ++i) {
arr = [];
generateArr( Math.pow(2, i) );
console.time('N = 2^' + i);
quickSort(arr);
console.timeEnd('N = 2^' + i);
}
我得到的运行时间如下：
N = 2^12: 8.030029296875ms
N = 2^13: 5.56005859375ms
N = 2^14: 9.332763671875ms
N = 2^15: 20.909912109375ms
N = 2^16: 38.673828125ms
N = 2^17: 89.992919921875ms
N = 2^18: 187.841064453125ms
N = 2^19: 321.177001953125ms
N = 2^20: 683.663818359375ms
N = 2^21: 1461.80908203125ms
N = 2^22: 3129.0927734375ms
N = 2^23: 6694.160888671875ms
N = 2^24: 14762.876953125ms
可以看到，从 2 的 14、15 次方开始（约一万），数据规模每乘 2，运行时间也乘 2 左右，符合 N log N 在 N 趋近无穷时的增长速度（ lim n->inf (2N log 2N) / (N log N) = 2 * lim (log 2 + log N) / log N = 2 * 1 = 2 )
因此，阮一峰的实现达到了快排的渐进时间复杂度，没有问题。（其实我个人偏好这种损失一定常数，但保证简洁正确的写法）
Select Language