问题:
用二分法求数组A[n]最大的两个数,A[n]是无序的
请问怎么理解 T(n) = 2 * T(n / 2) + 2 <= 5n / 3 - 2 这句话...
表示困扰了很久,不是很理解那些操作要计入空间复杂度
这里面有4次比较,还有声明了4个变量x1L,x2L,x1R,x2R
还有一些赋值交换的操作,到底哪些操作是要计入时间复杂度的呢?
二分法不是用来查找两个最大的数,二分法是用来查找一个指定的数。二分法的前提是数组已经排序了,排序的数组找最大两个不就很容易了,要么前两个,要么最后两个
能用二分法查找的数组肯定是有序的啊,这样的话就不用用二分法找最大的两个数了
二分法也可以查找无序的数组吧,你看看图片的代码,确实可以查找;
把找A(n)最大两个数,归结为这样两个子问题:
先把A(n)按mi为中点,平分为A(n/2)L 和 A(n/2)R //L表示左,R表示右
然后问题转化为:
求A(n/2)L中最大的2个数 和 A(n/2)R 中最大的2个数, 然后比较这4个数,就可以返回A(n)中最大的两个数了
这个算法确实是分而治之
我的问题是最后的复杂度是怎么计算出来的,表示很难理解... ...