La différence entre le Temps de la Complexité et de temps de fonctionnement

Demandais juste si, dans une question, il est de parler du temps d'Exécution d'un algorithme, signifie-t-il le même que le Temps de la Complexité ou est-il une différence entre les deux?

Tout dépend du contexte dans lequel le terme a été utilisé. Quand votre patron est de se demander pourquoi le "run-time" était de 3 heures, il ne parle pas de la complexité algorithmique. Lorsque votre professeur vous demande ce que le "run-time" de l'algorithme, il n'est probablement pas pour vous demander de sortir votre chronomètre et le temps.

OriginalL'auteur Harshay | 2011-02-06

  1. 12

    Temps d'exécution est combien de temps il faut un programme à exécuter. Le temps de la complexité est une description du comportement asymptotique du temps de fonctionnement en entrée la taille tend vers l'infini.

    Vous pouvez dire que le temps d'exécution "est" O(n^2) ou que ce soit, parce que c'est le idiomatiques façon de décrire la complexité des classes et des big-O de notation. En fait, le temps d'exécution n'est pas une classe de complexité, il s'agit soit d'une durée ou d'une fonction qui vous donne la durée. "Être en O(n^2)" est une propriété mathématique de la fonction, pas un la caractérisation complète. Le fonctionnement exact du temps pourrait être 2036*n^2 + 17453*n + 18464 de cycles CPU, ou quoi que ce soit. Pas que vous avez très souvent besoin de savoir que beaucoup de détails, et de toute façon elle pourrait dépendre de l'entrée effective ainsi que la taille de l'entrée.

    "Comme l'entrée de la taille tend vers l'infini", c'est vrai.

    OriginalL'auteur Steve Jessop

  2. 2

    La complexité du temps et les temps d'exécution sont deux choses différentes au total.

    Temps de la complexité est un concept théorique liée à des algorithmes, lors de l'exécution de ce temps est le temps d'un code de courir, pas du tout théorique.

    Deux algorithmes peuvent avoir la complexité en même temps, dire O(n^2), mais on peut prendre deux fois plus de temps en cours comme les autres.

    OriginalL'auteur akaHuman

  3. 1

    "Temps d'exécution" désigne l'algorithme en considération:

    Un autre algorithme pourrait être en mesure de résoudre le même problème asymptotiquement plus rapide, qui est, avec moins de temps de fonctionnement.

    "Le temps de la complexité" sur l'autre main est inhérente au problème à l'examen.
    Il est défini comme le moins de temps de fonctionnement de tout algorithme résolvant le problème dit.

    La même distincting s'applique à d'autres mesures de l'algorithmique des coûts tels que la mémoire, #processeurs, la communication de volume etc.

    (Blum du Speedup Théorème démontre que le "moins" de temps peut en général pas être réalisable...)

    OriginalL'auteur Martin Ziegler

  4. 0

    Pour analyser un algorithme est de déterminer la quantité de ressources (comme le temps et le stockage) nécessaire pour l'exécuter. La plupart des algorithmes sont conçus pour fonctionner avec des entrées de longueur arbitraire. Habituellement, le efficiency or running time of an algorithm est exprimé comme une fonction relative à l'entrée de la longueur de la number of steps (time complexity) ou emplacements de stockage (espace de la complexité).

    OriginalL'auteur ayush

  5. 0

    De CLRS 2.2 pg. 25

    Le temps d'exécution d'un algorithme sur une entrée donnée est le nombre
    de opérations primitives ou “étapes” exécutée. Il est commode de
    définir la notion d'étape, de sorte qu'il est indépendant de l'ordinateur comme
    possible.

    Maintenant à partir de Wikipédia

    ... le temps de la complexité d'un algorithme permet de quantifier la quantité de temps pris par un algorithme à exécuter en fonction de la longueur de la chaîne
    représentant l'entrée.

    Complexité temporelle est communément estimée par comptage du nombre de
    opérations élémentaires effectuée par l'algorithme, où une école élémentaire
    l'opération prend un montant fixe de temps à effectuer.

    D'avis que les deux descriptions de souligner la relation de la taille de l'entrée pour le nombre de primitives/opérations élémentaires.

    Je crois que ceci permet de préciser les deux font référence au même concept.

    Dans la pratique, mais vous remarquerez que enterprisey jargon rarement les matchs de terminologie savante, par exemple, des tonnes de gens à travailler faire de l'optimisation du code, mais rarement de résoudre les problèmes d'optimisation.

    OriginalL'auteur pgpb.padilla