时间戳

首页 > 解决方案 > 检查所有元素是否与分而治之相同

c - 检查所有元素是否与分而治之相同

问题描述

我想检查数组中的所有元素是否相同。我递归地做了，但我想用分而治之的方法来做。我也希望时间复杂度为 O(n)。我如何用主定理解释？

bool same_elements(int* array,size_t start, size_t end){
    if(start==end) return true;

    if(array[start]==array[start+1]){
        return same_elements(array,start+1,end);
    }
    return false;
}

标签： crecursiontime-complexitydivide-and-conquermaster-theorem

解决方案

与您的递归方案相同，如果您只有一个元素的数组，则答案通常是“是”。

如果您有两个元素，则如果它们相等，则为“是”。

如果有更多，请在 和 之间选择一个中点start，end递归地确保直到中点的所有元素都相同，并且从中点开始的所有元素都相同。两侧检查的中点也将确保两侧彼此相等。

我不擅长 Master Theorem，但直觉上 - 计算比较次数，N=1 时为零，N=2 时为 1；在 N=3 的情况下，我们将问题拆分为 T(2)+T(2) = 1+1 = 2 等。很容易看出，总是会有 N-1 个元素比较。

推荐阅读