找到代码的时间复杂度

Question

给定是一个无限排序的数组,只包含数字0和1.有效地找到转换点.

例如:00000000000111111111111111

输出:11是转换发生的索引

我为此编写了一个解决方案,忽略了一些边缘情况.

int findTransition(int start)
{
  int i;
  if(a[start]==1)return start;
  for(i=1;;i*=2)
  {  
    //assume that this condition will be true for some index
    if(a[start+i]==1)break;
  }
  if(i==1)return start+1;
  return findTransition(start+(i/2));
}

我不太确定这个解决方案的时间复杂性.有人可以帮我解决这个问题吗？

是O(log(N))吗？

Answer 1

设n为转变点的位置

这个块

for(i=1;;i*=2)
  {  
    //assume that this condition will be true for some index
    if(a[start+i]==1)break;
  }

适用于log2(n)

所以我们有

T(n) = log2(n) + T(n/2)
T(n) = log2(n) + log2(n/2) + T(n/4) = log2(n) + (log2(n) - 1) + (log2(n) - 2)... 
T(n) = log2(n) * (log2(n) + 1) / 2

所以有O(log(n)^ 2)复杂度(对于最坏的情况)

注意:您可以使用通常的二进制搜索而不是递归调用,然后您将获得log2(n)+ log2(n/2),仅授予O(log(n)).