我在阅读关于快速排序时间复杂度的文章时发现，虽然快速排序的时间复杂度是 n log n ，但是对于病态输入它会降为 n^2。当我去查找病态输入在这个上下文中的含义时，我在维基百科（和其他一些博客）上读到，在计算机科学中，病态输入是指违反算法正常复杂性或正确性的任何输入！这有点循环。那么，在这个上下文中，什么是病态输入呢？
关于排序算法，什么是“病态输入”？
3
- Anoop Dixith
2
1不知道什么是“病态单位”，但当快速排序每次选择最差的枢轴时，而不是将其分成两个大小为n/2的列表，它会变成n^2，其中一个列表大小为1，另一个列表大小为n-1。 - Ankur
@Shan 根据选择的枢轴，它可能比这稍微好一些。通常情况下，快速排序的任何实现的最坏情况都涉及将列表划分为至多k个元素和至少n-k个元素的情况，其中k是一个常数，这仍然是二次的。 - moreON
3个回答
5
许多排序算法在处理以下数据时存在问题：
- 已经排序的数据
- 以相反的顺序排序的数据
- 所有数据都相同（包括＃1和＃2）
- user949300
4
可能更适合英语（或其他与词源有关的）SO网站，但pathological来自希腊语，意思是研究疾病或苦难（也包括情感，因为古希腊人以将两者联系起来而闻名...），在这个背景下 - 所有对正常秩序的干扰都属于病态范畴。
因此，算法的病态案例是可能出现的最坏输入，它是如此混乱或糟糕地安排，以至于让您尽最大努力执行任务。最坏情况下的执行复杂度由此派生，并通常用于描述未知数据的算法复杂度。在某些情况下，当最坏情况真的很模糊或不太可能时，也可以谈论常见情况的复杂性并找到优化该复杂性的算法。
对于快速排序算法，它将是一个输入，其中所有您选择的主元素（无论是随机选择还是使用其他方法）都映射到当前部分的一侧，从而使排序过程总是经过步骤最多的最坏路径。
因此，算法的病态案例是可能出现的最坏输入，它是如此混乱或糟糕地安排，以至于让您尽最大努力执行任务。最坏情况下的执行复杂度由此派生，并通常用于描述未知数据的算法复杂度。在某些情况下，当最坏情况真的很模糊或不太可能时，也可以谈论常见情况的复杂性并找到优化该复杂性的算法。
对于快速排序算法，它将是一个输入，其中所有您选择的主元素（无论是随机选择还是使用其他方法）都映射到当前部分的一侧，从而使排序过程总是经过步骤最多的最坏路径。
- Leeor
1
我认为举个例子可能会有所帮助。
假设你有一个中值选取快速排序程序。它会伪随机地选择三个元素，取其中间的那个作为枢轴。（你希望这个枢轴尽可能靠近中间的那个数字）。如果输入被选择得恰好排列得很好，每次选择三个元素时它们都是最高的三个或者最低的三个，那么每次都会选择一个糟糕的枢轴，强制算法使用两个排序通道来排序仅仅三个元素，并导致最坏情况Omega(n ^ 2)操作。
通常，如果数据在每一步选择了对于您的程序而言最差（或至少是异常糟糕）的情况，则称其为病态数据。
假设你有一个中值选取快速排序程序。它会伪随机地选择三个元素，取其中间的那个作为枢轴。（你希望这个枢轴尽可能靠近中间的那个数字）。如果输入被选择得恰好排列得很好，每次选择三个元素时它们都是最高的三个或者最低的三个，那么每次都会选择一个糟糕的枢轴，强制算法使用两个排序通道来排序仅仅三个元素，并导致最坏情况Omega(n ^ 2)操作。
通常，如果数据在每一步选择了对于您的程序而言最差（或至少是异常糟糕）的情况，则称其为病态数据。
- Charles
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接