Comment f (n)

Question

J'ai lisée Ce tutoriel sur la complexité de temps , et je suis un peu perplexe sur son explication de Big $ O $ Notation. Ça écrit:

$ o (g (n))= $ { $ f (n) $ : là existent des constantes positives $ C $ C $ et $ n_0 $ telle que $ 0 \ Leq f (n) \ Leq c * g (n) $ pour tous $ n> n_0 $ .

.

La façon dont je comprends, $ C * g (n) $ désigne $ C $ multiplié par $ g (n) $ . Si tel est le cas, alors comment l'expression ci-dessus spécifie-t-elle le temps et non seulement que $ C * g (n) $ est supérieur à $ f (n) $ ? Ou suis-je incorrect, et c'est une notation que je ne comprends pas? Ma compréhension de la complexité du temps est très rudimentaire, alors pardonnez-moi si ce n'est qu'une erreur stupide de ma part.

Answer 1

Comment F (n)

Ce n'est pas le cas. La notation Bachmann-Landau est simplement une façon pratique de comparer le taux de croissance des fonctions. Cela ne dit rien sur ce que ces fonctions signifient et nous pouvons être à peu près sûrs que Bachmann ne pensait pas aux ordinateurs lorsqu'il est arrivé en 1894.

quelle signification vous attribuez à ces fonctions est à vous de choisir. Par exemple, lors de l'analyse des algorithmes de tri basés sur la comparaison, nous prenons généralement $ n $ pour être le nombre d'éléments de la collection et $ F (n) $ Pour être le nombre de comparaisons, ou le nombre de swaps, ou le nombre de comparaisons et de swaps.

Notez également que tout cela est toujours relatif à un modèle de machine ou à un modèle de coût.

Par exemple très simple, si je devais vous demander quelle est la complexité du pire des cas algorithmique pour la copie d'une liste, vous diriez $ o (n) $ . Mais en fait, la la réponse correcte serait "Je ne peux pas vous dire que parce que vous n'avez pas spécifié le modèle de la machine". Parce que, par exemple, dans une machine Turing, la copie d'une liste est $ O (n ^ 2) $ , car pour chaque élément en cours de copie, la tête du TM a conduire plus loin et plus loin pour atteindre la fin de la liste pour écrire l'élément suivant.

Answer 2

dire que l'heure d'exécution d'un algorithme est dans $ o (g (n)) $ donne, comme vous l'avez noté, seule une limite supérieure. De plus, la limite supérieure est donnée avec les constantes $ C $ C $ et $ n_0 $ inconnu. Donc oui, ce sont des informations assez faibles sur la durée de fonctionnement.

la constante non spécifiée $ C $ peut contenir les informations sur le coût réel des opérations de base de l'algorithme, qui peut être inconnue et / ou variable entre les courses, mais toujours connu pour coûter une durée limitée. La constante non spécifiée $ n_0 $ reflète que la liaison donnée fait référence à de grandes tailles de l'entrée (ou quel que soit le paramètre $ n $ < / span> représente).

autres symboles sont utilisés pour donner d'autres types ou informations plus précises sur la durée de fonctionnement.