arrays - 查找代码的时间复杂度

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为过渡点的位置

这个 block

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))。