Partage
  • Partager sur Facebook
  • Partager sur Twitter

complexité

Anonyme
14 mars 2020 à 17:54:52

bonjour à tous,

aujourd'hui ,je reviens encore vers vous et j'aimerai aborder un sujet très complexe tel qu'il est mentionné sur le titre de mon sujet la complexité algorithmique.j'ai lu tant de choses sur cela  , mais il  y'a toujours des ambiguïtés qui m'habitent et je souhaite avoir un éclaircissement plus simple à comprendre à ce que Google m'affiche quand je fais des recherches.

j'ai bien compris la définitions des notations Ω,θ,σ, .

Mes PROBLÈMES sont :

1-) comment savoir si un algorithme peut  s'exécuter en θ(quelque chose) si il est en Ω(quelque chose).

2-)comment savoir si un algorithme peut  s'exécuter en θ(quelque chose) si il est en σ (quelque chose).

3-) comment savoir si un algorithme peut  s'exécuter en Ω(quelque chose) si il est en σ (quelque chose).

4-)comment savoir si un algorithme peut  s'exécuter en Ω(quelque chose) si il est en θ(quelque chose).

5-)comment savoir si un algorithme peut  s'exécuter en σ(quelque chose) si il est en θ(quelque chose).

6-)comment savoir si un algorithme peut  s'exécuter en σ(quelque chose) si il est en Ω(quelque chose).

...ainsi de suite

:AUSSI VOIR PRESQUE LA MEME CHOSE AVEC PIRE ET MEILLEUR DES CAS

 si un algorithme est en θ(quelque chose) dans le pire des cas comment savoir s'il existe des cas en
σ(quelque chose)? 

ainsi toutes les propositions qu'on peut avoir comme mentionné dessus.

nb:je souhaite avoir une explication s'il vous plaît bien détaillée (acceptable même avec shéma donné )

MERCI À toute personne qui prend de son temps pour me lire et me répondre .

BONNE JOURNÉE
  • Partager sur Facebook
  • Partager sur Twitter
14 mars 2020 à 18:19:59

Deja une chose : il a n'y a pas 1 complexicité mais à minima deux. Une en temps et une en espace.

Un exemple simple : tu veux calculer un cosinus.

1) tu fais un algorithme complexe en temps (plusieurs calculs), mais qui ne nécessite quasiment pas de mémoire.

2) tu fais une table des cosinus avec une certaine précision. Tu ne fais plus qu'une opération, mais ça prends de la mémoire.

3) tu fais un système hybride avec des tables pour les calculs intermédiaires.

Ensuite ta complexité en temps peut être exprimé en (pire cas, cas moyen, meilleur cas), ou (moyenne, écart type)... Pour ça, pardonne moi, mais on va manquer de place ici :-). Tu as Wikipédia qui est très bien fait. Un forum ne vaudra jamais un cours. De même que regarder toutes les saisons de Dr House ne donne pas un doctorat en médecine. 

  • Partager sur Facebook
  • Partager sur Twitter
Anonyme
14 mars 2020 à 18:48:56

merci pour votre réponse , mais ca m'aide pas

,et avant que je poste là je suis déjà passé sur wiki , si j'avais compris je ne passerai pas ici

-
Edité par Anonyme 14 mars 2020 à 18:50:27

  • Partager sur Facebook
  • Partager sur Twitter
14 mars 2020 à 22:02:12

Alors, pourrais-tu dans ce cas préciser la question ? J'avoue ne pas bien comprendre la deuxième partie.

si un algorithme est en θ(quelque chose) dans le pire des cas comment savoir s'il existe des cas en
σ(quelque chose)? 

Comment savoir si il existe un plus court chemin quand tu ne connais pas la topologie exacte ? Pour prendre un exemple simple : décomposition en série de Fourier. Tu sais que si tu as un signal symétrique, tu vas pouvoir calculer uniquement la moitié des coefficient. Mais je ne pense pas qu'il y a une théorie complète applicable pour tous les algorithmes de manière générale. 

Après tu as des analyses de complexité informatique basée sur la topologie, qui permet de classer les problèmes. Tu peux prouver mathématiquement que ton algorithme est optimal (et encore), mais c'est pour un algo bien précis.

D'ailleurs je crois que le problème P = NP n'a pas encore été résolu et fait partie des problèmes du millénaire. 

PS : Enfin une question intéressante :-) 

-
Edité par raoullevert 14 mars 2020 à 22:05:39

  • Partager sur Facebook
  • Partager sur Twitter
Anonyme
15 mars 2020 à 12:54:51

Si je prouve qu’un algorithme est en Θ(n3) dans le pire des cas, peut-il exister des cas enO(n2) ?comment je peux répondre à ceci?
  • Partager sur Facebook
  • Partager sur Twitter
15 mars 2020 à 13:19:44

C'est un peu compliqué sans cas précis en fait. C'est un peu comme étudier les minimas d'une fonction uniquement à partir de sa limite en +inf ....

Avec le "Master theorem" peut être ? 

Si tu divises ton algo en sous problèmes, tu vas voir dans quel cas tu peux simplifier ton algo global, non ? 

<=>

Si tu fais un arbre de complexité, tu peux calculer la complexité globale selon la branche suivie. 

Par contre, c'est compliqué de généraliser ce genre de chose. La méthode d'akara-Bazzi par exemple peut être une méthode dans le cas des algo récursifs. Je ne sais pas si ça peut t'aider ? 

  • Partager sur Facebook
  • Partager sur Twitter
Anonyme
15 mars 2020 à 14:05:24

franchement c'est une question d'examen , elle est fourni de ce genre , on a vu en cours que le théorème général et je ne vois pas comment résoudre avec ceci
  • Partager sur Facebook
  • Partager sur Twitter
15 mars 2020 à 14:11:12

Si on réponds a on quel diplôme alors ?
  • Partager sur Facebook
  • Partager sur Twitter
Anonyme
15 mars 2020 à 17:32:47

Bon en même temps je peux pas t'aider plus mon pti chat. Tu m'en vois désolé.
  • Partager sur Facebook
  • Partager sur Twitter