grande notation O de ce code

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"); 
}

quelle peut être la notation big-O de ce code? ma conjecture est N * (2^(logN))grande notation O de ce code

J'ai déjà attribué mon hw! c'est juste ma pré-curiosité!

Source

2010-01-13 edib

Vous pouvez simplifier votre réponse plus loin (je ne suis pas sûr que ce soit correct ou non). En supposant que log est la base 2, 2^(log N) = N, votre réponse serait O (N^2). – Mike

Votre estimation est fausse. :-) –

Pourquoi est-ce fermé comme pas une vraie question? Il y a une question ici, avec une réponse précise (pas celle que l'interlocuteur pensait), donnée par éphémient. –

ara est une implémentation récursive de la recherche binaire. C'est O (log n).

Elle est appelée 2n-1 fois. En multipliant les deux termes, le programme dans son ensemble est O (n log n).

Source

2010-01-13 22:54:47 ephemient

Vous me battez en quelques secondes! –

merci, je pense que votre réponse est correcte. – edib

Cela me semble linéaire. Mais votre formatage est assez foutu, donc c'est difficile à dire.

EDIT: Très bien, récursivité impliquée. Pas linéaire, alors. Ce serait plus facile si nous avions des noms de variables significatifs.

Source

2010-01-13 22:51:33

Juste parce que vous ne parlez pas turc ne rend pas le nom de la variable non significatif :-) – paxdiablo

merci paxdiablo! les vars sont des vars que vous connaissez (x, y, z, bla bla.) Je suis nouveau ici et je ne peux pas insérer la méthode int main() dans la zone de texte en tant que code. donc j'ai omis. – edib

grande notation O de ce code

Répondre

Questions connexes