Complexité pour 2n^2 + n

Question

Si un problème de complexité 2n^2 + n peut être résolu en 24 unités de temps pour n = 2, combien de temps cela prend-il pour n = 4 ?

On m'a dit que la réponse est 48. Mais je crois que cela devrait être 24^2 parce que la complexité de l'algorithme est O(n^2).

J'apprécierais si quelqu'un pouvait m'éclairer.

Answer 1

La notation du grand O est simplement une notation asymptotique. En termes stricts, f(n)=O(n^2) signifie qu'il existe des nombres réels A et B et un entier n0, tels que An^2 <= f(n) <= Bn^2, pour n >= n0.

Par conséquent, tout d'abord si n < n0, la tendance ne doit même pas suivre n^2. Deuxièmement, pour n >= n0, vous êtes seulement assuré que f(n) est borné (comme mentionné ci-dessus). Si vous vouliez approximer, O(n^2) signifie que pour de grands n, vous pouvez ignorer les termes d'ordre inférieur, f(n) --> 2n^2, cependant, pour de petits n cela introduira une erreur significative.

Dans votre cas, vous avez la forme fonctionnelle exacte de la performance, f(n) = 2n^2+2, donc vous devriez l'utiliser!

Supposez que chaque étape prend du temps T0 avec un temps constant C, alors T(n) = T0*(2n^2+n) + C. Si C = 0, alors:

1. Trouvez T0: T(2) = 24 = T0*(2(2)^2+2) => T0 = 2.4 heures
2. Utilisez T0 pour n=4, T(4) = (2.4 heures)*(2(4)^2+4) = 86.4 heures

Answer 2

La complexité O(f(n)) comprend toutes les calculs qui prennent un temps de c*f(n)+d, où c et d sont des constantes. Si d=0 alors :

Dans le cas où n=2 et la complexité O(2n^2+2) est de 24 :

24 = (2*2^2 + 2)*c, donc c = 24/10 = 2.4

Maintenant nous calculons pour n=4 :

(2*4^2+4)*2.4 = 36*2.4 = 86.4 unités de temps

Si d n'est pas égal à 0, alors c = (24-d)/10 et pour n=4 cela prendrait

36*(24-d)/10 +d = 86.4 + 0.9d

Donc, il est impossible que la réponse soit 48, ce qui implique en outre un algorithme linéaire

Answer 3

Je ne pense certainement pas que cela soit 24^2. Si vous parlez de O(n^2) et que vous avez un exemple prenant 24 unités de temps pour n = 2, cela signifierait qu'il faudrait environ 4 fois plus de temps pour terminer pour n = 4 (2^2 = 4; 4^2 = 16 - environ 4 fois).

Si vous calculez différemment en remplaçant n = 2 dans 2*n^2 + n, vous obtenez 10. Si 10 = 24, cela signifie qu'il faut 2,4 unités de temps pour chaque cycle. Puis, en remplaçant n = 4, vous obtenez 2*4^2 + 4 = 36 et en multipliant par 2.4, vous obtenez 86.4

Answer 4

En utilisant Ruby comme langage mathématique, la formule de l'OP est

f = -> x { 2 * x ** 2 + x }

(1) En supposant qu'une étape de l'algorithme prend 1 unité de temps, la réponse est 50, car le terme constant c est

c = 24 - f.( 2 ) #=> 10
# et
c + f.( 4 ) #=> 50

Sous cette hypothèse, la réponse est 50.

(2) Si, cependant, nous permettons à une étape de l'algorithme de prendre e unités de temps au lieu de 1 unité de temps, alors la constante c sera :

24 - e * 10

et le temps d'exécution pour n == 4 sera

24 + e * 26        # donne 50 pour e == 1

(3) Avec une hypothèse supplémentaire, que le temps constant est nul (c'est-à-dire, que la formule donnée est exacte), nous avons

24 - e * 10 == 0

Et les réponses de Candide, bcorso et Milky Dinescu s'appliquent.

Bien que la question de l'OP ne déclare pas littéralement qu'une étape == 1 unité de temps, je pense toujours que telle était l'intention de l'auteur, également basée sur le résultat typique et facile à vérifier du manuel de 50.