int sum = 0;
for (int i = 0; i*i < N; i++){
for (int j = 0; j*j < 4*N; j++){
for (int k = 0; k < N*N; k++){
sum++;
}
}
}
je sais que l'ordre de croissance de ce segment de code est N^3.Mais j'ai besoin d'expliquer correctement pour cela.quel est l'ordre de croissance de ce segment de code? Expliquer peu bit
Je sais que l'ordre de croissance de ce segment de code est N^3
Oui, vous avez raison.
Le nombre total d'exécution est sqrt(N) * sqrt(4 * N) * (N^2) qui est -
sqrt(N) * sqrt(4 * N) * (N^2)
=> 2 * sqrt(N) * sqrt(N) * (N^2)
=> 2 * N * (N^2)
=> 2 * (N^3)
=> O(N^3)
C'est toujours pareil ... J'ai d'abord répondu et donné des explications encore plus détaillées pourquoi vous pouvez simplement multiplier, mais la réponse plus tard est acceptée et plus les upvotes, c'est ridicule. – maraca
Salut @maraca, je n'ai pas remarqué votre réponse jusqu'à ce que j'ai posté ma réponse, Il était presque en quelques secondes différence, même pas minute. Et ces choses arrivent avec moi beaucoup de fois, c'est vraiment frustrant. Je suis upvoting votre réponse :) –
Vous pouvez analyser les boucles étape par étape, parce que les compteurs sont indépendants les uns des autres:
boucle extérieure: sqrt exécutée (n) fois. Boucle moyenne: exécutée sqrt (4 * n) = 2 * sqrt (n) fois.
Boucle interne: exécutée n^2 fois. Multiplier les résultats: sqrt (n) * 2 * sqrt (n) * n^2 = 2 * n^3
Ainsi suit O (n^3).
Comme simplement des opérations de comptage? De la boucle externe à l'intérieur. 'sqrt (N) * sqrt (N) * N^2 -> N^3' –
Ce n'est pas un doublon. La chose la plus importante à mentionner est que ** les compteurs sont indépendants **. Ce qui n'est pas le cas dans l'autre question. ** Alors seulement, il est possible de simplement multiplier les résultats **. – maraca