Quelle est la complexité temporelle du code?

La complexité temporelle du code suivant O (NV^2)?Quelle est la complexité temporelle du code?

for i from 1 to N: 
    for j from 1 to V: 
     for k from 1 to A[i]://max(A) = V 
      z = z + k

Source

2014-09-13 象嘉道

C'est comme vous l'avez dit. La seule exception pourrait être si A [i], même si V peut être au maximum, il sera, par exemple, toujours constant "en moyenne" (complexité amortie). Pas plus de détails - il y a beaucoup de bonnes ressources pour cela. Et les universités, bien sûr. – PawelP

Pour un exemple de ce que dit Pawell, supposons que A soit plein de zéros à l'exception d'une seule valeur, qui est V. La boucle interne ne fonctionnera que pour i donc la complexité totale du temps sera O (NV + V^2 – hugomg

Oui, la complexité temporelle est O (NV^2). C'est tout. – Hungry

ouais, chaque fois que nous parlons de O-notation, nous pensons toujours à la (ou le pire des cas) la limite supérieure .

Ainsi, la complexité de ce code sera égal à

O(N*V*maximum_value_of_A) 
=O(N*V*V) // since,maximum value of A=V,so third loop can maximally iterate from 1 to V---V times 
=O(N*V^2).

Source

2014-09-13 15:51:26

Veuillez également répondre à la question! –

Bien sûr, il est O (NV^2) cela signifie que le code est plus lent jamais que cela. Parce que max (A) = V, vous pouvez dire que le pire des cas serait quand à chaque indice de A il y a V. Si oui, alors la complexité peut être limitée à O (NV * V).

Vous pouvez calculer très grossièrement que la complexité de la boucle for k peut être O (moyenne (A)). Cela nous permet de dire que toute la fonction est Omega (NV * s (A)), où avg (A) < = V.

notation Theta (ce qui signifie la complexité asympthotical) serait peut être déclaré comme Theta (NV * O (V)), O (V) représentant la complexité d'une fonction qui ne croîtra jamais plus vite que V, mais n'est pas constante.

Source

2014-09-13 16:03:10 3yakuya

Quelle est la complexité temporelle du code?

Répondre

Questions connexes