Complexité du temps de l'algorithme simple Question

Je travaille sur une affectation pour un cours d'introduction à la datamining. J'essaie de comprendre la complexité temporelle d'un algorithme (voir ci-dessous)? Est-il linéaire/exponentiel/log/quadratique/polynominal? Des conseils sur la façon d'aborder une question comme celle serait très appréciéComplexité du temps de l'algorithme simple Question

Considérons l'algorithme suivant pour trouver le troisième plus petit élément un tableau:

Entrée: n, a[1..n] - tableau a de nombres, et n est sa taille, n> = 3
sortie: - retour 3ème plus petit nombre
variables temporaires: b[1..3], t, i

Code:

b[1] = a[1] 
b[2] = a[2] 
if b[1] > b[2] then t=b[1]; b[1]=b[2]; b[2]=t 
b[3] = a[3] 
if b[2] > b[3] then t=b[2]; b[2]=b[3]; b[3]=t 
if b[1] > b[2] then t=b[1]; b[1]=b[2]; b[2]=t 
for (i = 4; i <= n; i = i+1) 
    if a[i] < b[3] then b[3] = a[i] 
    if b[2] > b[3] then t=b[2]; b[2]=b[3]; b[3]=t 
    if b[1] > b[2] then t=b[1]; b[1]=b[2]; b[2]=t 
return b[3]

Source

2009-10-26 Bilson

Il n'y a qu'une seule boucle, il n'y a rien imbriqué, et aucun autre appel de fonction ou quelque chose de même bizarre à distance. Qu'est-ce que tu penses? –

Et jusqu'où êtes-vous allé par vous-même? –

cette classe de datamining n'avait-elle pas une sorte d'intro préalable aux algorithmes? – Autoplectic

Il est linéaire, car la seule boucle interne se répète au plus n fois et n'effectue que des opérations à temps constant.

Plus précisément

1. b[1] = a[1] 
2. b[2] = a[2] 
3. if b[1] > b[2] then t=b[1]; b[1]=b[2]; b[2]=t 
4. b[3] = a[3] 
5. if b[2] > b[3] then t=b[2]; b[2]=b[3]; b[3]=t 
6. if b[1] > b[2] then t=b[1]; b[1]=b[2]; b[2]=t 
7. for (i = 4; i <= n; i = i+1) 
8. | if a[i] < b[3] then 
9. | | b[3] = a[i] 
10. | | if b[2] > b[3] then t=b[2]; b[2]=b[3]; b[3]=t 
11. | | if b[1] > b[2] then t=b[1]; b[1]=b[2]; b[2]=t 
12. return b[3]

Les lignes 1-6 sont exécutées qu'une seule fois et doit être constante de temps. Dans le contexte d'une seule exécution de la boucle for, les lignes 8 à 11 ne sont exécutées qu'une seule fois et sont toutes des opérations à temps constant; qui sont ensuite répétés ~ n-3 fois.

Source

2009-10-26 22:43:43 CoderTao

Une bonne règle est: combien de fois faites-vous une boucle sur l'entrée?

Source

2009-10-26 22:45:06 dameiss

Ceci est O (n), il est toujours bon de regarder ce que l'entrée est, et voir ce qui change si vous deviez ajouter un autre élément au tableau dans ce cas.

Vous constaterez que vous devrez parcourir le tableau pour trouver le 3ème plus petit élément du tableau.

Source

2009-10-26 23:11:51 mduvall

Complexité du temps de l'algorithme simple Question

Répondre

Questions connexes