Magic Index

 

 

问题如下：

给定一个数组A，其中有一个位置被称为Magic Index，含义是：如果i是Magic Index，则A[i] = i。假设A中的元素递增有序、且不重复，请给出方法，找到这个Magic Index。更进一步，当A中允许有重复的元素，该怎么办呢？

看到这个问题，我第一反应遍历一遍不就可以解决了吗？算法复杂度O(n)，但是一想，这么简单的题应该还有陷阱，我们发现题目中告诉我们有一个条件A中的元素递增有序，记得曾经有个面试老师告诉我，如果你发现题目中给你的数据是有序的，且有范围，第一反应应该是使用二分法求解，那么此题就可以用二分法解决，复杂度降为O(nlogn)。

下面我们考虑，如果元素不重复的情况，如何二分查找。元素不重复，如果有A[mid] == mid，那么直接返回，当A[mid]>mid时，我们只需要查找下标小于mid的元素是否有A[mid] == mid，因为元素递增有序且不重复，那么必有i>mid时，A[i]-i>=A[mid]-mid>0，同理对于A[mid]<mid的情况只需查找右半边元素。

那么，对于有重复元素的情况怎么办呢？当A[mid] == mid，那么直接返回；但是当A[mid]>mid时，我们不仅仅需要查找下标小于mid的元素是否有A[mid] == mid，还需要查找小标大于mid的元素是否存在，因为有可能存在这种情况A={-1，-1,0,4,4,4,4}，这样的情况下我们就必须两遍同时查找，下面将代码附在后面。

 

 

2. #include<iostream>  
3. using namespace std;  
4.   
5.   
6. int magicIndex1(int A[],int low,int high){//无重复元素情况  
7.     int mid = low+(high-low)/2;  
8.     if(A[mid] == mid){  
9.         return mid;  
10.     }  
11.     else if(A[mid] > mid){//如果A[mid]>mid,则用所有所有mid的元素都不可能存在A[i]==i  
12.         //因为元素递增有序且无重复元素  
13.         return magicIndex1(A,low,mid-1);  
14.     }  
15.     else{  
16.         //原理同上  
17.         return magicIndex1(A,mid+1,high);  
18.     }  
19. }  
20.   
21. int magicIndex2(int A[],int low, int high){//有重复元素情况  
22.     if(high < low )  
23.         return -1;  
24.     int mid = low+(high-low)/2;  
25.     if(A[mid] == mid){  
26.         return mid;  
27.     }  
28.     else{  
29.         int left = magicIndex2(A,low,mid-1);  
30.         int right = magicIndex2(A,mid+1,high);  
31.         if(left != -1)  
32.             return left;  
33.         else   
34.             return right;  
35.     }  
36. }  
37.   
38.   
39. int main(){  
40.     int A[5]={-1,1,1,2,3};//{-1,0,1,2,4};  
41.     //cout<<magicIndex1(A,0,4)<<endl;  
42.     cout<<magicIndex2(A,0,4)<<endl;  
43.     return 0;  

递归树

递归算法时间复杂度的计算方程式一个递归方程：
　　

　　在引入递归树之前可以考虑一个例子：

　　T(n) = 2T(n/2) + n²

　　迭代2次可以得：

　　T(n) = n² + 2(2T(n/4) + (n/2) ²)

　　还可以继续迭代，将其完全展开可得：

　　T(n) = n² + 2((n/2) ² + 2((n/2²)² + 2((n/2³) ² + 2((n/2⁴) ² +…+2((n/2ⁱ) ² + 2T(n/2^{i + 1})))…))))　　……(1)

　　而当n/2ⁱ⁺¹ == 1时，迭代结束。

 

　　将(1)式小括号展开，可得：

　　T(n) = n² + 2(n/2)² + 2²(n/2²) ² + … + 2ⁱ(n/2ⁱ)² + 2ⁱ⁺¹T(n/2ⁱ⁺¹)

　　这恰好是一个树形结构，由此可引出递归树法。

 

　　图中的(a)(b)(c)(d)分别是递归树生成的第1,2,3,n步。每一节点中都将当前的自由项n²留在其中，而将两个递归项T(n/2) + T(n/2)分别摊给了他的两个子节点，如此循环。

　　图中所有节点之和为:

　　[1 + 1/2 + (1/2)² + (1/2)³ + … + (1/2)ⁱ] n² = 2n²

　　可知其时间复杂度为O(n²)

　　

　　可以得到递归树的规则为：

　　(1) 每层的节点为T(n) = kT(n / m) + f(n)中的f(n)在当前的n/m下的值；

　　(2) 每个节点的分支数为k；

　　(3)每层的右侧标出当前层中所有节点的和。

 

　　再举个例子：

　　T(n) = T(n/3) + T(2n/3) + n

　　其递归树如下图所示：

　　

　　可见每层的值都为n，从根到叶节点的最长路径是：

　　

　　因为最后递归的停止是在(2/3)^kn == 1.则

　　　　　　

　　于是

　　　　

　　即T(n) = O(nlogn)　

 

　　总结，利用此方法解递归算法复杂度：

　　f(n) = af(n/b) + d(n)

　　1.当d(n)为常数时：

　　

　　2.当d(n) = cn 时：

 　　

　　3.当d(n)为其他情况时可用递归树进行分析。

　　

　　由第二种情况知，若采用分治法对原算法进行改进，则着重点是采用新的计算方法缩小a值。