J'ai créé une fonction qui boucle à travers le tableau et imprime deux valeurs du tableau qui peuvent totaliser une valeur K. La boucle for externe est O (n), mais la boucle interne me déroute un peu si le runtime est un O (Log n) ou O (n). Pouvez-vous aider s'il vous plaît? Merci !!
int canMakeSum(int *array, int n, int key){
int i, j;
for(i = 0; i < n; i++){
for(j = (i+1); j < n; j++){
if(array[i]+array[j] == key){
printf("%d + %d = %d\n", array[i], array[j], key);
}
}
}
}
3 Réponses :
Comme les boucles internes dépendent de la valeur de la boucle externe, vous ne pouvez pas trouver la complexité du porgram total sans analyser les deux ensemble. La complexité de la boucle interne est n - i - 1 .
Si vous souhaitez calculer la complexité du programme, vous pouvez faire la somme sur n - i -1 de i = 0 à i = n - 1 . Par conséquent, la complexité totale est T (n) = (n - 1) + (n-2) + ... + 1 + 0 = (n-1) n / 2 = \ Theta (n ^ 2) (car l'instruction de la boucle interne a une complexité constante ( \ Theta (1) )).
J'ai compris!! Merci. Est-il possible d'améliorer l'algorithme de la fonction entière et de le rendre O (n) ou O (n log n)?
Bien que la boucle interne diminue le nombre d'éléments qu'elle analyse pour chaque itération de la boucle externe, elle serait toujours O (n). La complexité temporelle globale est O (n ^ 2).
Imaginez que vous avez un tableau de 25 000 éléments. Au point de départ à i = 0 et j = 1 , le nombre d'éléments que j parcourra (dans le pire des cas, aucune correspondance avec la clé) est de 24 999 éléments. Ce qui est une petite différence par rapport au nombre total d'éléments, c'est donc "comme" passer par n éléments.
J'ai compris!! Merci. Est-il possible d'améliorer l'algorithme de la fonction entière et de le rendre O (n) ou O (n log n)?
Comme d'autres l'ont déjà montré, la boucle interne est toujours O (n) ; c'est une moyenne de n / 2 itérations, les valeurs 1 à n étant réparties uniformément sur les itérations de la boucle externe.
Oui, vous pouvez résoudre le problème dans O (n log n) .
Commencez par trier le tableau; c'est n log n . Maintenant, vous avez un processus linéaire ( O (n) ) pour trouver toutes les combinaisons.
lo = 0
hi = n-1
while lo < hi {
sum = array[lo] + array[hi]
if sum == k {
print "Success", array[lo], array[hi]
lo += 1
hi -= 1
}
else if sum < k // need to increase total
lo += 1
else // need to decrease total
hi -= 1
La boucle interne s'exécute (n-1) + (n-2) + ... + 1 = n * (n-1) / 2 fois. Additionne jusqu'à un total de O (n ^ 2)