Quelle est la durée de ces mystères?

Question

mystery(int A[1..n], int n) { 
     // pre: n is a power of 2 for i=1..n { 
     for i = 1...n { 
      A[i] = A[i] + 1; 
     } 
     if (n>1) mystery(A, n/2); 
    } 

} 

Je pense que dans le pire des cas, cela fonctionne dans O (n), ai-je raison?

---

Edit: Ceci est d'un autre ancien examen (qui a des réponses pour nous), mais l'algorithme suivant fonctionne en O (n * log n) (selon par la réponse). Pourquoi ça? Je pense que ces deux ne devraient différer que par quelques constantes.

void silly (int n) 
    if (n>1) 
     for (int i=0; i<n; i++) 
      output "looping for fun" 
     silly(n/2) 
     for (int i=0; i<n; i++) 
      output "looping for more fun" 
     silly(n/2) 
     for (int i=0; i<n; i++) 
      output "looping for even more fun" 

Answer 1

Oui, c'est O (n). Vous pouvez vérifier la santé d'esprit en examinant les valeurs:

A(1) = 1 iteration 
A(2) = 2 + A(1) = 3 
A(4) = 4 + A(2) = 7 
A(8) = 8 + A(4) = 15 
A(16) = 16 + A(8) = 31 
A(32) = 32 + A(16) = 63 
... 

Vous voyez qu'il est mise à l'échelle linéaire où A (n) est essentiellement un facteur linéaire de n.

Pour répondre au commentaire: non ce n'est pas O (2n) ou O (2n-1). Il n'y a pas de O (2n). Tout est O (n). Voir Plain english explanation of Big O.

Edit: votre exemple a une différence essentielle: elle appelle elle-même deux fois pas une fois. Sanity vérifier les résultats à nouveau. En outre, cette version a une caractéristique trompeuse en ce que la boucle est répétée trois fois mais trois est constante ici et comme indiqué précédemment il n'y a pas O (n), donc je vais seulement compter un de ces boucles:

A(1) = 1 
A(2) = 2 + 2 * A(1) = 4 
A(4) = 4 + 2 * A(2) = 12 
A(8) = 8 + 2 * A(4) = 32 
A(16) = 16 + 2 * A(8) = 80 
A(32) = 32 + 2 * A(16) = 192 
... 

Alors, quelle est la relation? Eh bien, si vous résolvez un (n) (pour n étant une puissance de 2):

A(n) = n + 2 * A(n/2) 
    = n + 2 * (n/2 + 2 * A(n/4)) 
    = 2n + 4 * A(n/4) 
    = 2n + 4 * (n/4 + 2 * A(n/8)) 
    = 3n + 8 * A(n/8) 

Vous pouvez résoudre ce au cas général:

A(n) = log2(n) * n + A(n/n) 
    = log2(n) * n + 1 (since A(1) = 1) 

Et c'est là O (n log n) vient de.

Answer 2

Yup. Le nombre de A[i] = A[i] + 1 affectations dans un appel à mystery(..., N) sera:

N + N/2 + N/4 + ... + 1 

En supposant que N est une puissance de 2, cette série est évaluée à 2 * N - 1. Il y aura un nombre équivalent d'incréments de i, et log2(N) tests de `N> 1 ', appels récursifs au mystère et aux divisions.

En gros, c'est 4 * N + 3 * log2(N) opérations (en supposant qu'ils ont poids égal ... si ce n'est pas grave).

La limite de ce que N tend à l'infini est dans la plage C1 * N à C2 * N opérations, pour certaines constantes C1 et C2. En d'autres termes, la complexité de calcul est O(N).

Answer 3

Je suis en train d'évaluer un sujet de mi-session sur ce sujet en ce moment!

De toute façon, appelons l'exécution de cet algorithme T (n). La for-loop prend n fois, et la fonction s'appelle elle-même avec la valeur n/2. Donc T (n) = T (n/2) + n.

Nous pouvons résoudre cette récurrence en utilisant le Master Theorem et nous constatons que l'algorithme prend Theta (n)

Answer 4

Il est O(n).

Dérivation. Vous pouvez le déduire à l'aide du Master Theorem, ou la façon plus simple d'expansion:

On suppose que le temps d'exécution est mystry()T(n), alors il est:

T(n) = n + T(n/2) # n for the loop, T(n/2) for the recursive call 
    = n + (1/2)n + T(n/4) 
    = n + (1/2)n + (1/4)n + (1/8)n + ... 
    = n (1 + 1/2 + 1/4 + 1/8 + ...) 
    = n \Sum^{\inf}_{i=0} (1/2^i) 
    = n * (2) 
    = 2 n = O(n)