Quelle est la complexité donnée pour le problème suivant est O (n). Ne devrait-il pas être O (n ^ 2)? En effet, la boucle extérieure est O (n) et interne est également O (n), donc N * N = O (n ^ 2)?
La feuille de réponses de cette question indique que la réponse est O (n) . Comment est-ce possible? P>
public static void q1E(int n) {
int count = 0;
for (int i = 0; i < n; i++) {
count++;
for (int j = 0; j < n/2; j++) {
count++;
}
}
}
5 Réponses :
La complexité des deux code est O (n * n)
La boucle extérieure exécute SO
Que si vous ajoutez le Progression arithmétique est La boucle extérieure exécute SO
Que si vous ajoutez la progression arithmétique, c'est N fois et la boucle interne varie de 0 à n-1 fois
total = 1 + 2 + 3 + 4 ... + n
n * (n + 1) / 2 < / code> est o (n * n)
n fois et la boucle interne varie de 0 à n-1/2 fois
total = 1 + 1/2 + 3/2 + 4/2 ... + n / 2
n * (n + 1) / 4 est également o (n * n)
Donc, si N / 2 le fait-il encore égal à O (n)? Mais l'itération pour la boucle interne est la moitié de la boucle extérieure qui fait une différence?
@ user1085135: o (n) a la signification linéaire . Peu importe quelle constante il est multipliée par, ce qui ne compte que c'est que est linéaire
Le premier exemple est o (n ^ 2) , il semble donc qu'ils ont commis une erreur. Pour calculer (de manière informelle) le deuxième exemple, nous pouvons faire n * (n / 2) = (n ^ 2) / 2 = O (n ^ 2) . Si cela n'a pas de sens, vous devez aller et brosser ce que le sens de quelque chose étant O (n ^ k) est.
premier cas est définitivement La seconde est o (n ^ 2)
O (n ^ 2) aussi parce que vous omettez des constantes lorsque vous calculez BIG O
Votre feuille de réponse est fausse, le premier algorithme est clairement O (n ^ 2).
La notation Big-Oh est "pire des cas", donc lors du calcul de la valeur Big-OH, nous ignorons généralement les multiplications / divisions par les constantes.
qui étant dit, votre deuxième exemple est également O (n ^ 2) dans le pire des cas car, bien que la boucle interne soit "seulement" 1/2 N, le N est le facteur de liaison claire. Dans la pratique, le deuxième algorithme sera inférieur à O (N ^ 2) des opérations - mais Big-OH est destiné à être un "pire des cas" (c.-à-d. Layouche maximale), le nombre exact d'opérations est donc ignoré en faveur de Se concentrer sur la manière dont l'algorithme se comporte comme n approche l'infini.
Le deuxième algorithme ne sera pas inférieur à O (n ^ 2), c'est précisément O (n ^ 2). Je soupçonne que vous n'êtes pas assez clair sur quoi "O (n ^ 2)" signifie réellement. Cela signifie que comme indique N à l'infini, l'heure d'exécution augmente pour l'algorithme de deux valeurs de N est proportionnelle à la différence entre ces N valeurs au carré.
Non. Dans la pratique, la complexité du temps réel de l'algorithme sera légèrement inférieure à O (n ^ 2). Cependant, parce que Big-OH est une liaison maximale, nous disons que c'est O (n ^ 2). Vous avez raison que le facteur n / 2 est clairement borné par N - comme je l'ai indiqué dans ma réponse. Il existe d'autres mesures de bornisation (c.-à-d. Big-theta) qui calculent le facteur de sélection différemment.
Pourquoi pensez-vous que la complexité du temps réel de l'algorithme sera inférieure à O (n ^ 2)? Je prétends que ce sera précisément o (n ^ 2) parce que la complexité de l'algorithme précisément correspond à la définition de O (n ^ 2). Si ce n'est pas exactement O (n ^ 2), alors rien n'est. Nous disons c'est O (n ^ 2) car il est O (n ^ 2). Vous semblez vouloir faire ce flou, déroutant et imprécier quand il est absolument, cristal clair.
Parce que la complexité réelle est O (n ^ 2) + c, où c est une certaine constante. Dans ce cas, c est négatif. Donc, ce sera légèrement moins que droit n ^ 2. Le C est insignifiant, mais vous devriez toujours écrire la "réponse" comme O (n ^ 2) - c
Une complexité de O (n ^ 2) + C signifie précisément la même chose qu'une complexité de O (n ^ 2) .
Les deux sont O (n ^ 2) . Votre réponse est fausse. Ou vous avez peut-être écrit la question de manière incorrecte.
Je pense que la partie supérieure est O (n ^ 2) et quel doute que vous avez à propos de la deuxième?
Cela signifie que la réponse fournie par mon professeur est incorrecte HMM.
Il semble que la feuille de réponses contienne des erreurs.