Bienvenue sur mon blog ! Étudiant touche à tout, ce site est un lieu libre de partage d’experiences, de tuto et de découvertes sur tout et rien.
Complexite
Classes de complexité
| Déterministe | non-Déterministe | |
|---|---|---|
| temps | p,EXPTIME | np, NEXPTIME |
| espace | LOGSPACE, PSPACE, EXPSPACE | NLOGSPACE |
complexité logarithmique
- O(1) : constant
- O(n) : linéaire
- O(log n) : logarithmique
- O(n log n) : quasi-linéaire
- O(n²) : quadratique
- O(n³) : cubique
- O(n^k) : polynomial
- O(2ⁿ) : exponentielle
- O(n!) : factorielle
| algo | ||
|---|---|---|
| constant | O(1) | set |
| logarithmique | O(log n) | liste |
| linéaire | O(n) | recherche dichotomique, dans un tableaux trié |
| quasi-linéaire | O(n log n) | tri d’un tableaux (fusion) |
| quadratique | O(n²) | tri d’un tableaux (insertion) |
| cubique | O(n³) | multiplication de matrices |
| polynomial | O(n^k) | |
| exponentielle | O(2ⁿ) | problème du sac à dos |
| factorielle | O(n!) | problème du voyageur de commerce |
Problème complexe
Problème du voyageur de commerce
- problème NP-complet
- O(n!)
- 10 villes : 3 628 800
Problème du sac à dos
knapack problem
…Comment configurer github
Pour utiliser github sur son ordinateur il faut installer git, ajouter une clé ssh dans son compte github et configurer git, puis télécharger le projet, ces étapes sont indispensables sur chaque machine.
Installer git
Vérifier si git est déjà installé : git --version sinon télécharger git
Configurer git en local
C’est les informations qui seront affichées dans les commits, il faut les configurer une fois par machine.
- Configurer le nom d’utilisateur :
git config --global user.name "John Doe" - Configurer l’adresse mail :
git config --global user.email
Les informations sont stockées dans le fichier ~/.gitconf, si vous voulez les modifier vous pouvez le faire directement dans le fichier.
Design Patterns
C’est quoi ?
Les patterns offrent des solutions à des problèmes récurrents rencontrés par les développeurs, Ils permettent de :
- Limiter le couplage
- Faciliter la maintenance
- Être moins rigide face au changement
Ils sont indispensables à connaître pour le développeur :
- Pour s’assurer d’une meilleure conception
- Pour dialoguer avec les développeurs (à travers le “langage pattern”)
- Pour comprendre les frameworks
Un livre écrit par le GoF (Gang of Four : Erich Gamma, Richard Helm, Ralph Johnson, John Vlissides) décrit 23 Design Patterns appliqués à la conception orientée objet, classés en trois catégories :
…