Closed chy1984 closed 1 month ago
本书对自适应性的定义比较“宽泛”,认为只要时间复杂度受到输入数据。在这样的定义下,快速排序可以看作是自适应排序。
自适应排序的时间复杂度会受输入数据的影响,即最佳时间复杂度、最差时间复杂度、平均时间复杂度并不完全相等。 自适应性需要根据具体情况来评估。如果最差时间复杂度差于平均时间复杂度,说明排序算法在某些数据下性能可能劣化,因此被视为负面属性;而如果最佳时间复杂度优于平均时间复杂度,则被视为正面属性。
但严格来看,自适应排序特指那些利用输入数据的部分有序性达到“更高效率”的一类算排序算法。在该定义下,快速排序就不是自适应排序了。
已修正,感谢指出!