Quicksort是否存在潜在的安全风险？

Question

我只是想知道(在一些严重的偏执和某些情况下)使用QuickSort算法是否会被视为应用程序中的安全风险.

它的基本实现和改进版本(如3-median-quicksort)都具有特定输入数据行为异常的特性,这意味着它们的运行时间在这些情况下可能会极大地增加(具有O(n^2)复杂性),更不用说堆栈溢出的可能性.

因此,我认为通过向程序提供预先排序的数据可能会造成伤害,导致算法表现得像这样,这可能会对例如多客户端Web应用程序产生不可预测的后果.

这个奇怪的案例是否值得任何安全考虑(因此会迫使我们使用Intro-或Mergesort)？

编辑:我知道有很多方法可以阻止Quicksort的最坏情况,但是语言集成排序(如.NET的3中位数)呢.他们会成为禁忌吗？

Answer 1

是的,这是一个安全风险 - DoS,具体而言 - 通过在快速排序中添加对递归深度的检查,以及在达到某个深度时切换到其他内容,可以轻松减轻这种风险.如果切换到heapsort,那么你将获得introsort,这是许多STL实现实际使用的内容.

或者,您只需随机选择pivot元素.

Answer 2

许多快速排序的实现都是使用算法的随机版本完成的.这意味着无法使用特制输入进行DoS攻击.

而且,即使没有这个,大多数数据集都很简单,太小而不具有O(nlog)与O(n ^ 2)的关系.要进行排序的集合的大小必须非常大才能产生影响.即使有几百万个元素,时差也可能不会很大.

总的来说,使用quicksort的任何给定的Web应用程序更有可能存在其他安全 漏洞.

Answer 3

看一下这个问题(和标记答案),讨论减少QuickSort最坏情况的方法:

为什么quicksort比mergesort更好？