c - 这段代码的时间复杂度是否正确？

Question

如果函数“process”的复杂度为O(logn)，则计算这段代码的时间复杂度

void funct (int a[], int n)
{
    int i=0
      while (i < n){
         process (a, n);
         if (a[i]%2 == 0)
           i = i*2+1;
         else
           i = i+1;
  }

我尝试计算时间复杂度的最佳和最坏情况；

最坏的情况是调用“else”语句时，它应该是:

最坏情况:T(n) = O(nlogn)

我在最好的情况下遇到了一些问题。我试过这种方式，但我不知道这是否正确

因为在“if”语句中“i”增加了“2i+1”所以应该是

i=2^k-1
2^k < n+1 

so k < log_2(n+1) 

说 while 循环执行 (log_2(n+1)-2)/2 次是正确的，因为这是 i < n 的最后可能值？

如果是的话，时间复杂度在最好的情况下是 O(lognlogn)？

Answer 1

最好的情况是 a 中的采样值都是偶数。在这种情况下，复杂度为 O(log(n)*log(n)) , 因为循环次数是 O(log(n)) .

最坏的情况是 a 中的采样值都是奇怪的。在这种情况下，复杂度为 O(n*log(n)) , 因为循环次数是 O(n) .