Détermination des complexités temporelles des algorithmes les plus défavorables

Question

Les deux algorithmes ont-ils la même caractérisation thêta de Θ (n^2)?

int sum = 0; 
for (int i = 0; i < n; i++) 
    for (int j = 0; j < n * n; j++) 
     sum++; 

int sum = 0; 
for (int i = 0; i < n; i++) 
    for (int j = 0; j < i; j++) 
     sum++; 

Si ce n'est pas le cas, cela signifie-t-il que cette caractérisation n'est pas Θ (n^3)?

int sum = 0; 
for (int i = 0; i < n; i++) 
    for (int j = 0; j < i * i; j++) 
     for (int k = 0; k < j; k++) 
      sum++; 

Answer 1

@ Dan, pour le premier, vous avez vraiment dire j < n * n plutôt que j < n? Si oui, la complexité temporelle du premier est Θ (n^3), n'est-ce pas? Si vous vouliez dire j < n, alors je crois que les deux premiers sont tous les deux Θ (n^2): Le premier prend n^2 pas, et le second prend 1 + 2 + ... + n = n (n + 1)/2 qui est Θ (n^2). Je pense que le troisième est Θ (n^4), mais c'est plus difficile à prouver. Certainement O (n^4).