病理输入对于排序算法意味着什么？
What does pathological input mean with respect to sorting algorithms?
我在阅读快速排序的时间复杂度时看到虽然它是 n log n ，但对于病态输入它会减少到 n^2 。当我去检查病理输入在这种情况下的含义时，我在维基百科（和其他几个博客）上读到，在计算机科学中，病理输入是任何违反正常复杂性或算法正确性的输入！嗯，这是一种循环。在这种情况下，病理输入到底是什么？
许多排序算法在处理
的数据时存在问题
- 已经排序
- 已经反向排序
- 都一样（也包括#1 和#2）
我通过各种视觉比较发现了这个page that looks interesting
它可能更适合英语（或其他一些与词源相关的）SO 站点，但 pathological 来自希腊语，意思是对疾病或痛苦的研究（也包括情绪，因为古希腊人以将两者相关联而闻名......），并且在这种情况下 - 对事物正常秩序的各种破坏。
因此，算法的病态案例是它可能必须处理的最糟糕的输入，一个被打乱或安排不当的输入，它让你最努力地完成你的任务。最坏情况下的执行复杂度由此而来，通常用于描述未知数据的算法复杂度。在某些情况下，当最坏的情况真的很模糊或不太可能时，也可以讨论常见情况的复杂性并找到优化它的算法。
对于快速排序算法，输入恰好具有您选择的所有枢轴（无论是随机选择还是使用其他方法），映射到当前部分的一侧，始终呈现排序过程按照步数走最差的路径。
我想举个例子可能会有帮助。
假设您有一个中位数为 3 的快速排序程序。它伪随机地选择三个元素，取中间的一个，并将其用作枢轴。 （你希望它尽可能接近中间的数字。）如果选择输入的顺序恰到好处，这样每次选择三个元素时，它们要么是最高的三个，要么是最低的三个，你会做一个每次枢轴的糟糕选择，迫使算法使用两次排序传递仅对三个元素进行排序并导致最坏情况下的 Omega(n^2) 操作。
如果在每个步骤中选择对您的程序来说最糟糕（或至少异常糟糕）的任何数据，通常数据是病态的。
我在阅读快速排序的时间复杂度时看到虽然它是 n log n ，但对于病态输入它会减少到 n^2 。当我去检查病理输入在这种情况下的含义时，我在维基百科（和其他几个博客）上读到，在计算机科学中，病理输入是任何违反正常复杂性或算法正确性的输入！嗯，这是一种循环。在这种情况下，病理输入到底是什么？
许多排序算法在处理
的数据时存在问题- 已经排序
- 已经反向排序
- 都一样（也包括#1 和#2）
我通过各种视觉比较发现了这个page that looks interesting
它可能更适合英语（或其他一些与词源相关的）SO 站点，但 pathological 来自希腊语，意思是对疾病或痛苦的研究（也包括情绪，因为古希腊人以将两者相关联而闻名......），并且在这种情况下 - 对事物正常秩序的各种破坏。
因此，算法的病态案例是它可能必须处理的最糟糕的输入，一个被打乱或安排不当的输入，它让你最努力地完成你的任务。最坏情况下的执行复杂度由此而来，通常用于描述未知数据的算法复杂度。在某些情况下，当最坏的情况真的很模糊或不太可能时，也可以讨论常见情况的复杂性并找到优化它的算法。
对于快速排序算法，输入恰好具有您选择的所有枢轴（无论是随机选择还是使用其他方法），映射到当前部分的一侧，始终呈现排序过程按照步数走最差的路径。
我想举个例子可能会有帮助。
假设您有一个中位数为 3 的快速排序程序。它伪随机地选择三个元素，取中间的一个，并将其用作枢轴。 （你希望它尽可能接近中间的数字。）如果选择输入的顺序恰到好处，这样每次选择三个元素时，它们要么是最高的三个，要么是最低的三个，你会做一个每次枢轴的糟糕选择，迫使算法使用两次排序传递仅对三个元素进行排序并导致最坏情况下的 Omega(n^2) 操作。
如果在每个步骤中选择对您的程序来说最糟糕（或至少异常糟糕）的任何数据，通常数据是病态的。