用分治法检查所有元素是否相同

Question

我想检查数组中的所有元素是否都相同。我是递归地做的，但我想用分而治之的方法来做。另外我希望时间复杂度为 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;
}

Answer 1

与您的递归方案相同，如果您只有一个元素的数组，答案很简单 "yes"。

如果你有两个元素，如果它们相等，那就是"yes"。

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

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

Answer 2

我试图修复我所做的事情。这是我的代码：

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

   int m = (start + end) / 2;

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

时间复杂度约为 O(n)。

大师定理：

A=2 B=2 C=0 => n^c=n^0=1

T(n)=2T(n/2) + O(1)

A>B^C => O(n^logB(A)) = O(n^log2(2)) = O(n )

用分治法检查所有元素是否相同

Check if al elements are the same with divide and conquer

c

recursion

time-complexity

divide-and-conquer

master-theorem