RT,在啊B上看到一个可视化排序的视频,有一个慢速排序算法
上网查了一下,发现它的递归式是:
T(n)=2T(n/2)+T(n−1)+O(1)T(n)=2T(n/2)+T(n-1)+O(1)T(n)=2T(n/2)+T(n−1)+O(1)
显然不能使用主方法,并且显然渐近大于 O(nlgn)O(n\lg n)O(nlgn)。
Akra-Bazzi貌似也不行……