新人求助c++。。上交文件的时候测评出运行时间过长

Question

#include<iostream>
using namespace std;
int Max (int *p,int l,int r){//分左右两部分分别求最大值，最后比较。总思路递归 
    int maxl,maxr;
    if (l == r) return *(p+l);
    else {
        maxl = Max(p,l,(l+r)/2);
        maxr = Max(p,(l+r)/2+1,r);
        if (maxl > maxr) return maxl;
        else return maxr;
    }
} 

int main(){
    int n,i;
    int *pp = new int[n];
    //赋值 
    cin >> n;
    for (i = 0;i < n;i++)
        cin >> *(pp+i);
    //调用 
    cout << Max(pp,0,n-1) << endl;
    delete [] pp;
    return 0;
} 

Answer 1

影响求解时间的因素主要是算法，算法选得不好，算的很慢的，你这个算法看似简单，但效率不高，还不如for循环来的快。递归需要消耗时间，分支结构影响指令流水的连续性，又耽误些时间。首先分析一下for循环的方法，循环一次有一次加法、两次判断、最多一次赋值，而你的这个递归，首先递归本身消耗时间、再加上两次判断，两次赋值，可能三次加法，两次除法，特别是除法，耗时是加法的十几倍以上。如果你对算法没有要求，建议你换个算法，如果要求用这个算法，那么可以稍稍改一下：1、除法用移位替代；2、减少重复运算。

int temp=(l+r)>>2;
maxl = Max(p,l,temp);
maxr = Max(p,temp+1,r)