J'essaie de dériver l' article classique dans le titre uniquement par des moyens élémentaires (pas de fonctions génératrices, pas d'analyse complexe, pas d'analyse de Fourier) bien qu'avec beaucoup moins de précision. Bref, je veux "seulement" prouver que la hauteur moyenne hnhnh_n d'un arbre à nnn...
Étant donné un tableau de entiers, chaque élément du tableau peut être augmenté d'un nombre fixe avec une certaine probabilité , 0 \ leq i <n . Je dois trouver le nombre attendu de swaps qui auront lieu pour trier le tableau à l'aide du tri à bulles .AAANNNbbbp[i]p[i]p[i]0≤i<n0≤i<n0 \leq i...
Considérant ce pseudo-code d'une bulle: FOR i := 0 TO arraylength(list) STEP 1 switched := false FOR j := 0 TO arraylength(list)-(i+1) STEP 1 IF list[j] > list[j + 1] THEN switch(list,j,j+1) switched := true ENDIF NEXT IF switched = false THEN break ENDIF NEXT Quelles seraient les idées de base...
Comment prouvez-vous que la hauteur attendue d'un arbre de recherche binaire construit de façon aléatoire avec nœuds est ? Il y a une preuve dans CLRS Introduction to Algorithms (chapitre 12.4), mais je ne la comprends pas.O ( log n )nnnO(logn)O(Journaln)O(\log