Algorithmique élémentaire

[psp]

Bonjour,

Cet algorithme inverse les éléments d'un tableau de taille n,

def swapp(tab , i , j)
int aux=tab[i]
tab[i]=tab[j]
tab[j]=aux


def main(tab)
n=taille(tab)
j=n/2
if(n%2==0)
i=(n/2)-1
else
i=(n/2)
while(j<n){
swapp(tab,i,j)
i=i-1
j=j+1
print tab
}

Y'a une dizaine de question mais je vous donne celles qui me posent problème
On pose
Je dois démontrer que et
Avec :
la valeur de i à la fin de la k-ème itération de la boucle while
la valeur de j à la fin de la k-ème itération de la boucle while

Déterminer la complexité de l'algorithme

[Ezra]

Cet algorithme inverse les éléments d'un tableau de taille n,


Y'a une dizaine de question mais je vous donne celles qui me posent problème
On pose
Je dois démontrer que et
Avec :
la valeur de i à la fin de la k-ème itération de la boucle while
la valeur de j à la fin de la k-ème itération de la boucle while

Déterminer la complexité de l'algorithme

Que sait-on des types de complexité et de leur calcul pour les tris, où on remplace un élément à la position par un élément à la position dans une table, de taille , avec les cases rangées de à ?
Revois ton cours : en exemple, la recherche séquentielle d'un élément parmi est linéaire, car il est facile de montrer que l'on fait opérations en moyenne, opérations dans le pire cas et dans le meilleur cas.