Je veux m'assurer que ma façon de travailler avec la complexité de l'espace et du temps est bonne. Je suis un étudiant en informatique et je travaille à temps partiel et j'ai eu cet exercice en plus de mon travail pour un cours que je suis par l'entreprise pour laquelle je travaille et je me demande si je comprends bien la complexité ou si je suis sur le fausse piste!

J'essaie de comprendre la complexité temporelle et spatiale de deux cas. J'ai déjà fait quelques étapes et j'ai essayé, donc ci-dessous, vous trouverez mes réflexions et réponses sur trois méthodes/fonctions différentes dans le code Java. Faites défiler vers le bas pour les exercices.

Cas 1:

  public int func1(int n) {

   int total = 0;
     for (int i = 0; i < n; i++) {
      for (int j = 50; j > 0; j--) {
       for (int k = 0; k < j/2; k++) {
        total++;
       }
      }
     }
     return sum;
    }

Complexité temporelle
Pour la complexité temporelle, je pense que la boucle externe est O(n), la boucle du milieu est O (1) et la boucle la plus interne est également O (1) car elle n'a rien à voir avec la première boucle, donc ai-je raison si cela est Grand O(1 * 1 * n) => Grand O(n) ??

Complexité spatiale
La complexité spatiale de celui-ci doit probablement être Big O (1) car il n'y a pas de nouvelles variables instanciées dans les boucles. Seules les boucles elles-mêmes et le total int = 0. Mais cela n'a rien à voir avec le n également. Donc je suppose que Space est Big O(1).

Cas 2:

  public int func2(int n) {
      if (n > 0) {
      int[] array = new int[n+n];
      return func2(n-1) + func2(n-2);
     } else {
      return 0;
     }
    }

Complexité temporelle
La complexité temporelle de celui-ci est un peu plus difficile pour moi, à cause du tableau au début. . Mais je ne sais pas si cela peut être n^2 à cause du retour double récursion func2(n-1) + func2(n-2).. Suis-je dans la bonne direction avec Big O(n)?

Complexité spatiale
Et pour le dernier de tous, je pense que la complexité spatiale dans ce cas est 2n, qui est alors n ? Parce qu'à chaque fois que la fonction est appelée, elle crée un nouveau tableau avec une longueur de 2n, donc si n=4 le tableau a une longueur de 8, et alors l'itération suivante est de 6 etc.

Donc ma réponse finale est Big O(n) pour la complexité spatiale.

0
techanimal259 6 nov. 2020 à 16:12

1 réponse

Meilleure réponse

Votre analyse du premier cas est correcte.

Le deuxième cas est plus difficile. Vous ne pouvez pas vraiment évaluer la complexité temporelle avec précision, car :

  • C'est certainement exponentiel en n;
  • Si vous avez besoin d'une limite de complexité stricte, vous devez obtenir la base et l'exposant exactement ; et
  • Vous ne savez pas vraiment combien de temps prend cette allocation. Dans certains systèmes, c'est O(n), car la mémoire sera mise à zéro pour des raisons de sécurité. Dans certains cas, il sera amorti en O(n) car un ramasse-miettes de copie est en cours d'utilisation. Dans certains cas, il sera indéterminé car une liste libre doit être parcourue.

n

La complexité spatiale est la mémoire totale allouée simultanément. Encore une fois, cela dépend des détails de l'implémentation, mais nous pouvons supposer que vous utilisez un langage de récupération de mémoire qui ne nécessite pas que la mémoire soit libérée, car sinon vous faites une horrible erreur en ne la libérant pas. Donc...

Étant donné que le tableau alloué n'est utilisé nulle part, il n'y a aucune référence à celui-ci, donc si le langage est récupéré par la mémoire, la complexité de l'espace sera de O(n), car le tableau peut être récupéré immédiatement après son allocation.

1
Matt Timmermans 6 nov. 2020 à 14:23