algorithm - 计算步骤以形成算法的递推关系

Question

我是算法分析方面的新手。我刚刚写了一个分而治之的算法，它应该在 O(n) 时间内从数组中找到一个最大数，我一直坚持形成它的循环。

以下是我的算法。

int findMax(int *A, int S, int E){

    if(S == E){        //1 unit of time
        return A[S];
    }
    else if(S == (E-1)){  // 1 unit of time
        if(A[S] > A[E]){  // 1 unit of time
           return A[S];
        }
        else{
           return A[E];
        }
    }

    mid = (S+E)/2;            // 1 unit of time     
    L = findMax(A, S, mid);
    R = findMax(A, mid+1, E);   // 1 unit of time 

    if(L > R){          // 1 unit of time
       return L;
    }
    else if(R > L){     // 1 unit of time
       return R;
    }

}

如有错误请指正

我形成的循环是:

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

我将所有单位成本相加 7 是否正确？

请帮我解决这个问题。谢谢。

Answer 1

首先，并不是所有的代码路径都返回，让我们修改算法的最后一个if/else语句如下:

if(L > R){          // 1 unit of time
   return L;
}
else {     // 1 unit of time
   return R;
}

• T(1) = 1 : 这只是进行第一次比较并成功。
• T(2) = 3 :这将进行三次比较以找到两项中的最大值。
• T(N) = 2*T(N/2) + 4，对于 N > 2

最后一个如下:

+1 for first if comparison, which will fail
+1 for the else if part of the first comparison block, which will also fail
+1 for computing the middle element
+2*T(N/2) for the recursive parts
+1 for the last comparison (single if)