большая буква O этого кода - PullRequest
Новая
       9

большая буква O этого кода

0 голосов
/ 14 января 2010 
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");  
}

что может быть бинарной нотацией этого кода? мое предположение N * (2 ^ (logN))

Я уже назначил свой hw! это всего лишь мое предварительное любопытство!

Ответы [ 2 ]

6 голосов
/ 14 января 2010

ara - рекурсивная реализация бинарного поиска. Это O (log n).

Это называется 2n-1 раз. Умножая два термина, программа в целом получается O (n log n).

0 голосов
/ 14 января 2010

выглядит линейно для меня. Но твоё форматирование довольно испорчено, так что трудно сказать.

РЕДАКТИРОВАТЬ: Хорошо, рекурсия включена. Тогда не линейно. Было бы проще, если бы у нас были значимые имена переменных.

...