c - 此代码的大 O 符号

Question

int ara(int dizi[], int ilk, int son, int deger) { 
      int indeks;    
      if ( ilk > son ) 
        return 0; 

      indeks = (ilk + son) / 2; 
      if ( dizi[indeks] < deger ) 
        return ara(dizi, indeks+1, son, deger); 
       else if ( dizi[indeks] > deger ) 
        return ara(dizi, ilk, indeks-1, deger); 
       else  
       return 1; 
} 

for (i=1; i<2*n; i++)   { 
    printf("Bir sayi giriniz: "); 
    scanf("%d", &sayi); 
    sonuc = ara(matrix, 0, n-1, sayi); 
    if ( sonuc == 1 ) 
      printf("Found!\n"); 
     else 
      printf("Not Found!\n");  
}

这段代码的大 O 符号是什么？我猜是 N*(2^(logN))

我已经分配了我的硬件!这只是我的好奇心!

Answer 1

ara 是二进制搜索的递归实现。即 O(log n)。

它被调用了 2n-1 次。将这两项相乘，整个程序的复杂度为 O(n log n)。