La taille d'entrée d'un certain algorithme est n^2+n*m. Son temps d'exécution est O(m*n^3). Le temps d'exécution peut-il être considéré comme polynomial dans la taille d'entrée ?
Réponses
Trop de publicités?
amit
Points
74385
Oui, c'est le cas. Il fonctionne en O(max{n,m}^4) qui est en temps polynomial pour l'entrée qui est plus petite que O(max{n^2,n*m}^2) qui est quadratique dans la taille de l'entrée.
Note : Ceci suppose que l'entrée est de taille n^2+n*m et non un nombre de cette "taille" - parce qu'un nombre peut être représenté comme log(n^2+n*m) bits, ce qui ne vous permettra d'obtenir qu'un pseudo-polynôme solution.
Le temps d'exécution T(n,m) est dit polynomial dans la taille d'entrée S(n,m) = n^2+n*m s'il existe un polynôme dans S qui est une borne supérieure de T(n,m).
Considérons le polynôme S^2(n,m) = (n^2+n*m)^2 = n^4 + 2(n^2)n*m + (n^2)(m^2). Comme n^4 et (n^2)(m^2) sont des carrés d'entiers positifs, ils sont positifs, donc S^2(n,m) > 2(n^2)n*m > n^3 * m.
Puisque T(n,m) est O(n^3 * m) et que S^2(n,m) > n^3 * m, T(n,m) est O(S^2(n,m)) et le temps d'exécution est donc limité par un polynôme dans la taille de l'entrée.
