rei*_*ish 0 c sorting algorithm quicksort time-complexity
我在C中实现了一个quicksort实现,我试图弄清楚需要哪些输入才能导致更糟糕的案例性能.
根据维基百科:
总是以这种方式选择分区中的最后一个元素作为枢轴导致已排序列表或相同元素列表的性能(n ^ 2)不佳.
所以我试着这样做,这导致了以下代码.pivot始终是最后一个元素,输入是已排序的列表.
为了证明复杂性确实是n ^ 2,我创建了一个全局变量,我在每次迭代中递增,然后最终打印它.
我希望该程序可以打印:
Done in 64 iterations
但是,它在28次迭代中完成了它.也许我对"复杂性"一词的理解是错误的？
在每次迭代中,列表都会缩小一个元素,因为枢轴已移动且不再计算.因此,迭代总量为7 + 6 + 5 + 4 + 3 + 2 + 1 = 28.
请注意,这仍然是二次的,因为它等于n*(n-1)/2.