Complexité temporelle pour un algorithme impliquant deux boucles for

Question

public static void main(String[] args) {

  Scanner sc = new Scanner(System.in);

  int n = sc.nextInt();
  int m = sc.nextInt();
  int result = 0;

  for (int i=0; i < n; i++) {
    for (int j=m; j > 0; j--)
      result += 1;
    m -= 1;

  }
  System.out.println(result);
}

La question est une question vraie ou fausse. L'énoncé est "La complexité temporelle du programme suivant lorsque n est beaucoup plus grand que 2 m est O (n m)". Vrai ou faux?

La complexité temporelle de la question fait référence à la complexité temporelle la plus défavorable. Voici ce que j'ai fait jusqu'à présent:

La boucle interne s'exécute m fois et la valeur de m diminue de 1 à chaque fois. Le nombre total d'itérations de la boucle intérieure est alors: m + m - 1 + m - 2 + m - 3 + .... + 3 + 2 + 1.

On peut considérer cela comme une suite arithmétique.

Le nombre total d'itérations de la boucle intérieure est alors: m (m + 1) / 2 = (m ² + m) / 2.

Une fois que m a atteint 0, puisque n est beaucoup plus grand que 2 * m, la boucle externe continuera à fonctionner en temps O (1) pendant n - m fois plus.

Ainsi, la complexité temporelle est: (m ² + m) / 2 + n - m = O (m ² ).

Est-ce la bonne façon d'aborder cette question?

Answer 1

Non, ce n'est pas correct. Tout d'abord, il n'y a pas de «pire cas» ou de «meilleur cas» ici, puisque le nombre d'étapes est entièrement déterminé par net m.

La question est, comme vous l'avez dit, une question oui / non. Donc, simplement calculer la complexité temporelle n'est pas la bonne approche pour cette question (et au fait, le résultat n'est pas O(m^2) - vous ne pouvez pas simplement laisser tomber n!)

Votre raisonnement jusqu'à la dernière étape est correct. Le nombre d'étapes est, comme vous l'avez correctement calculé, (m^2 - m)/2 + n(après simplification). La question est: est (m^2 - m)/2 + nun membre de l'ensemble O(mn), sous l'hypothèse que n >> 2m?

Ignorant les constantes par souci de simplicité, écrivons l'hypothèse sous forme d'inégalité:

(m^2 - m)/2 + n < nm (eventually, as n, m grow)

Maintenant en divisant par des nmdeux côtés on obtient l'inégalité équivalente

(m - 1)/(2n) + 1/m < 1

Par l'hypothèse, le premier terme disparaît, il nous reste donc 1/m < 1ce qui est clairement vrai à mmesure que grandit. L'hypothèse est donc correcte et la réponse est oui .