1.1) entier Min[1..k] booléen Trouvé[1..n] pour j de 1 à n Trouvé[j] <- faux pour i de 1 à k min <- +oo // c'est-à-dire, le plus grand entier représentable argmin <- -1 pour j de 1 a n si non Trouvé[j] si T[j] <= min min <- T[j] argmin <- j Min[i] <- min Trouvé[argmin] <- vrai 1.2) Tri(T) entier Min[1..k] pour i de 1 à k Min[i] <- T[i] 1.3) Le premier algorithme fait n + kn opérations ; le deuxième en fait n log(n) + k. Si k << n (pour la précision, k < (n log n - 1)/(n - 1) - 1), le premier algorithme est plus performant, avec un nombre d'opérations O(n), contre O(n log(n)) du deuxième. Par contre, si k ~ n, le deuxième est plus performant, O(n log(n)), vis-à-vis de O(n^2) du premier. Il faut faire tout de même attention au fait que tout cela c'est toujours à une constante multiplicative près (que l'on ne maîtrise pas bien en pratique). Si, par exemple, on code le 1.1 et le 1.2 en Python et que l'on utilise comme fonction Tri() la méthode sort(), qui est native (c-à-d, écrite en un langage bas-niveau et compilée dans l'interprète) et donc incomparablement plus rapide du code Python interprété, le terme n log(n) du coût du deuxième algorithme sera multiplié par un facteur tellement petit qu'en pratique le deuxième algorithme sera toujours le plus performant et très nettement. 2) Logarithmes 2.1) log_2(n) 2.2) i + 1, partie entière de log_2(n) + 1 et 32 respectivement 2.3) pour n petit, le 1er algorithme est moins performant du 2ème mais, pour n grand (> 40.000 environs), le 1er algorithme est plus performant du 2ème ; quant au 3ème algorithme, il est toujours le plus performant des trois. 3) Le juste prix Stratégie: on commence avec un interval de nombres possibles [bottom, top], où bottom = 1 et top = 1000 ; à chaque essai, on propose le nombre middle = (bottom + top)/2 ; si le voisin dit que le nombre qu'il a choisi est supérieur, bottom <- middle ; s'il dit que le nombre est inférieur, top <- middle. De cette façon, il faudra log(1000) essais dans le pire cas pour deviner. Comme 1024 = 2^10, on peut affirmer que 10 essais devraient suffir. Par contre, en choisissant n nombres au hazard, la probabilité de deviner sera de p(n) = 1 - 0.999^n (c'est-à-dire, 1 - la probabilité qu'aucun des nombres choisis soit le juste) ; pour n << 1000, p(n) ~ n/1000 : p(10) = 0.01, p(20) = 0.02, p(50) = 0.0488. Si, par contre, on suppose que les n nombres choisis soient tous distincts, p(n) est exactement n/1000. Donc, dans le pire cas, il faut choisir tous les 1000 nombres, c'est-à-dire, faire 1000 essais, 100 fois le nombre d'essais de la stratégie optimale. 4) Dynamic Array 4.1) - version mémoire t <- ALLOUER(n) i <- 0 répéter nb <- GÉNÉRATEUR() si nb != -1 si i >= n s <- ALLOUER(2 * n) pour j de 0 à i - 1 Mem[s + j] <- Mem[t + j] // recopie des i éléments n <- 2 * n t <- s Mem[t + i] <- nb i <- i + 1 tant que nb != -1 // n cases allouées, i éléments pertinents - version à la C T <- ALLOUER(n) i <- 1 nb <- GÉNÉRATEUR() tantque nb != -1 { si i = n + 1 { Tbis <- ALLOUER(2 * n) recopie(Tbis, T, n) // recopie des n éléments n <- n * 2 T <- Tbis } T[i] <- nb i <- i + 1 nb <- GÉNÉRATEUR() } // n cases allouées, i-1 éléments pertinents 4.2) La fonction ALLOUER aura été appelée log_2(m) - 1 fois. Le nombre total de cases consommées sera la somme des tailles des tableaux alloués : somme pour i = 0 à log_2(m) - 1 de 2^i. Le nombre d'éléments copiés sera somme pour i = 0 à log_2(m) - 2 de 2^i. 4.3) 4.4)