Erreur de link
Pour ce qui est du message d’erreur sur
g++ -std=c++17 test.cpp -o -Wall -Wextra -pedantic test.out
J’ai personnellement pris l’habitude que ce qui suit le -o doit être le nom de l’exécutable. Je ne sais pas si l’erreur vient de là. Sinon, vu que je suis sur des systèmes GNU bien configurés (i.e. pas MinGW, là c’est la loose), je compilerai même (indirectement, merci mon IDE — gvim) avec
# Attention impératif de pas de fichier `Makefile` dans le répertoire courant
CXXFLAGS='-std=c++17 -Wall -Wextra -pedantic` make test
Voire en mode abusé
export CXXFLAGS='-std=c++17 -Wall -Wextra -pedantic`
make test
make test
./test
make test
Code "faux" & pas KISS la complexité
Il donne un résultat FAUX
Où voyez-vous (vu que vous êtes deux) qu’il est faux? Pour chaque lettre, l’ensemble des lettres est parcouru "deux" fois, et en commençant à 0, la lettre courante est bien comptée une et une seule fois quand i == j. C’est moi qui ne suis pas réveillé?
Après, il y a bien un hic : un même résultat est affiché k fois. Il manquerait un | sort -u
Et quand bien même il serait faux, cela ne peut que me renforcer dans le besoin de la simplification de l’algo. Entre un algo simple et un complexe qui fait la même chose, je pense que l’on a tous appris (avec l’expérience) l’importance de la simplicité. Ce n’est pas une question d’optimisation. Et si on veut virer la redondance, à part sortir des enclumes pour stocker les résultat et enchainer sur sort + uniq, on en revient à la version type en O(N).
Est-ce moi qui associe simplicité avec table associative ici dans ce kata bien éprouvé?
Accessoirement, je range l’algorithmie dans les bases du développement, et dans l’algorithmie les notions de complexité. Et cet exo (résolu par l’OP dans sa forme maladroite) est un exemple type de kata algorithmique. Je suis quelque peu surpris du message de ne pas s’embêter avec ça.
@OP, "complexité" en trop peu de mots
Pour faire simple quand pour réaliser quelque chose :
- si on trouve directement, on parle de O(1)
- si il faut faire une/quelques boucles de k*N+a itérations fictives (k et x nombres constants), on parle de O(N) car la quantité de traitements est fonction linéaire du nombre d’itérations N
- si on a 2, 3, 4, 42… boucles l’une après l’autre, on est O(N) toujours — je passe les cas où le nombre d’éléments n’est pas exactement le même, ce qui est le cas de l’algo type de calcul + exploitation d’histogramme
- si on a 2 boucles imbriquées, là ça multiplie: O(N x N) -> O(N²)
- si on a 3 boucle imbriquées, là ça multiplie: O(N x N x N) -> O(N3) — on rejoint ce qu’à expliqué mon voisin du dessus, pour 10 éléments en plus, on se prend un x100 (en N²), un x1000 en N3, etc
- et il y a les cas de compléxités polynomiale O(NM) — arg!
- et les cas de recherche dichotomique: quand on peut couper la poire en deux (cf l’exo de recherche d’un nombre entre 1 et 100 qui peut se faire en 7 coups max) -> O(ln N) — voire les tris efficaces en O(N ln N), etc
Après, les difficultés, c’est que les algos se mêlent avec des structures de données qui vont nous aider à mémoriser de façon plus ou moins intuitive des résultats intermédiaires.
Ici, on passe à la complexité inférieure en utilisant des tables associatives, qui de préférence permettent de faire l’association {lettre -> nombre d’occurrences de la lettre} en un coup (i.e en O(1))
