Si nous avons un algorithme qui est l'ordre N^2*logN, et si cela prend 1 ms avec la taille d'entrée 64; faut-il 2^10 * (11/6) ms pour exécuter cet algorithme avec la taille d'entrée 2048? J'utilise des proportions directes ici, c'est pourquoi cela me semblait défectueux.Complexité temporelle
manière la plus simple à résoudre est probablement diviser 2048 par 64, branchez le nombre résultant dans l'équation de la complexité, et le résultat est le nombre de millisecondes pour la taille d'entrée 2048.
Cela semble très raisonnable, alors la réponse est si f (x) = x^2 * logx, alors f (2^11/2^6) = f (2^5), n'est-ce pas? –
Ce n'est généralement pas la façon dont la complexité temporelle est présentée/fonctionne. 'O (N^2 * log (N))' peut signifier par exemple que l'algorithme prend '15 N^2 * log (27 N) + 573 N + 10000000000' étapes pour les entrées de taille' N'. –
Si les termes inférieurs commandés sont ignorés? Est-ce ainsi, n'est-ce pas? Parce que j'ai écrit un programme simple avec 3 boucles imbriquées ne faisant rien, et ils ont obéi à la règle Robert a expliqué. –
Avez-vous essayé de lancer l'algorithme avec un 2048 taille d'entrée définie? Combien de temps at-il fallu? – Dai
Ces chiffres sont si petits qu'il y a une probabilité non négligeable que les termes d'ordre inférieur aient encore un impact significatif. –
En fait c'est un problème de complexité de temps sur papier, je n'ai pas essayé d'écrire un algorithme dont l'ordre est N^2 * logN et les entrées essayées. –