Complexité temporelle de cet algorithme utilisant la notation Big-O

Question

Je dois trouver la complexité temporelle du pseudocode que j'ai créé et la spécifier en utilisant la notation Big-O. Le problème est que je ne sais pas comment le calculer quand j'ai une instruction if à l'intérieur de boucles for imbriquées.
Voici mon pseudocode, ce qui est entre parenthèses est le nombre d'opérations:

Algorithm largestProduct(A)
  Input array A
  Output largest product value of two elements in array A, the values and their indices
  index1 ← 0                                          (1)
  index2 ← 0                                          (1)
  n ← A length                                        (1)
  max ← 0                                             (1)
  for i ← 0 to n-1 do                                 (n)
    for j ← i + 1 to n do                             (n^2)
      if max < A[ i ] * A[ j ] then                   (?)
        max ← A[ i ] * A[ j ]
        index1 ← i
        index2 ← j
  return max, A[index1], index1, A[index2], index2

Merci d'avance pour votre aide.

Answer 1

Étant donné que les opérations à l'intérieur de l' ifinstruction et sa condition n'affectent pas le nombre d'itérations et qu'il s'agit d'opérations uniques (constantes), vous pouvez considérer l' ifinstruction comme un fichier O(1).

Il est vrai que les forboucles imbriquées font des O(n^2)itérations, par conséquent, il y a une quantité constante de O(n^2)temps d' exécution des opérations , ce qui le rend O(n^2)*O(1)=O(n^2)global.