Est-ce techniquement un algorithme O(1) pour le “Hello World”?
Serait-ce être considéré comme un algorithme O(1) pour "Hello, World!" ??
public class Hello1
{
public static void Main()
{
DateTime TwentyYearsLater = new DateTime(2035,01,01);
while ( DateTime.Now < TwentyYearsLater )
{
System.Console.WriteLine("It's still not time to print the hello ...");
}
System.Console.WriteLine("Hello, World!");
}
}
Je suis en train de penser à l'aide de la
DateTime TwentyYearsLater = new DateTime(2035,01,01);
while ( DateTime.Now < TwentyYearsLater )
{
//...
}
extrait de code comme une boucle occupée à mettre une blague à chaque fois que quelqu'un demande un algorithme d'une certaine complexité. Serait-ce correct?
- C'est
O(N)
complexité, nonO(1)
- Mais ne pas la boucle occupée ajouter un nombre constant d'opérations?
- Non, vous ne savez pas combien de fois il va passer à travers la boucle, même si vous connaissez le montant exact de cette différence dans le temps entre le moment où vous démarrez le programme et la date spécifiée. C'est dépendante de la vitesse de l'ordinateur en cours d'exécution, il est, quoi d'autre est en cours d'exécution sur elle, comment le CPU horaires de la tâche, etc.
- Il n'y a pas de
N
que l'algorithme dépend, de sorte que vous ne pouvez pas réellement dire que c'est un algorithme O(N). - Techniquement il n'y a pas d'entrée, de sorte
N
n'a même pas de sens. Mais vous pouvez envisager d'DateTime.Now
une entrée qui fait encore la personne à charge sur le résultat. Si vous pouvez supposer une valeur réaliste pourDateTime.Now
, alors oui, le programme des boucles d'une quantité constante de temps. - FYI bigocheatsheet.com
- L'énoncé du problème doivent définir ce N est.
- La machine quelque chose s'exécute sur est totalement indifférent à la complexité algorithmique. La complexité théorique de la mesure qui ne tient pas compte de toute la mise en œuvre des parties spécifiques.
- C'est vrai pour la plupart des algorithmes. Lorsque vous écrivez un tri rapide pour une liste du nombre de comparaisons effectuées est complètement indépendante du matériel de l'exécuter; c'est seulement en fonction du nombre d'éléments dans la liste. Mais la boucle occupée voici les résultats dans le code qui effectue l'opération dans un manoir qui est dépendant du matériel en cours d'exécution. Une telle relation est très rare (et généralement pas sensible), mais certainement pas impossible.
- Eh bien, dans ce cas, il est certainement le cas...
- Aussi, Servy d'origine commentaire à propos de la machine qui exécute le programme a été une réponse à des OP question à propos d'un "nombre constant d'opérations," il n'est donc pas (directement) de présenter toutes les réclamations au sujet des machines et de la complexité algorithmique.
- pas de "manoir". Pas quelque chose que je devrais normalement la peine de corriger, mais probablement à un certain moment, quelqu'un devrait vous laisser savoir...
- Je pense qu'un peu de code qui dépend de l'extérieur défini
DateTime.Now
n'est pas considéré comme un algorithme en premier lieu. - Si vous utilisez l'exemple de Thread.Sommeil(new Timespan(365*20, 0,0,0)) au lieu de cela, cela élimine le problème de la "SystemTime" en entrée, ce qui peut rendre la question plus claire.
- Tout d'abord. Un algorithme, sans aucun apport peut être considéré comme un algorithme? sorcière problemas de la résolution? Date et chaîne de caractères à imprimer pourraient être considérées comme des variables? PS:de 10 heures de travail, ne prenez pas ce commentaire sérieux
- Ce n'est même pas un algorithme. Un algorithme implique de prendre des décisions à produire de la sortie désirée à partir d'une donnée d'entrée, mais cela imprime Bonjour tout le Monde, peu importe.
- Il y a des gens ici qui définitivement devriez lire à propos de comment Big O est défini au lieu de marmonner quelque chose à propos de l'entrée, la sortie, le nombre de calculs bla, bla.
- BTW la question montre très peu d'effort de recherche, pour dire le moins. Mais il est clair comme le cristal. Et quand une question provoque beaucoup de discussions, il doit être utile. +1 🙂
- Vous assurez-vous commencé une discussion entre les intellectuels ici, OP.
- Si nous supposons DateTime.Maintenant, en tant que paramètre, le programme des boucles de 0 fois suffisamment grandes valeurs de date / heure.Maintenant. Non pas qu'il ferait aucune différence, mais n aurait log(DateTime.Maintenant) pas DateTime.Maintenant.
TwentyYearsLater
est essentiellement une entrée de l'algorithme, dans ce cas, c'estO(N)
. C'est à dire: l'algorithme prend exactement aussi longtemps que vous dire pour qu'il puisse prendre; il est directement proportionnelle à la quantité de temps que vous avez spécifié.- En général, les questions ayant trait à l'analyse des algorithmes pourrait obtenir de meilleures réponses à Informatique.
- nom d'utilisateur vérifie
- Ce n'est pas à même de répondre aux exigences de "Hello World". Il imprime un tas de trucs supplémentaires. Il ne passe pas mon "Hello World" test de régression suite...
- ce n'est pas un algorithme, ce n'est pas la résolution de tout problème, il suffit de boucles, sauf si vous l'exécuter après la 1/1/2035
- veuillez utiliser une minuterie à la place. la lecture de la boucle while fait mal
Vous devez vous connecter pour publier un commentaire.
Big O la notation dans ce contexte est utilisé pour décrire une relation entre la taille de l'entrée d'une fonction et le nombre d'opérations qui doivent être effectuées pour calculer le résultat de cette entrée.
Votre opération n'a pas d'entrée que la sortie peut être lié à, l'utilisation d'un Grand O la notation est absurde. Le temps que l'opération est indépendant à l'une des entrées de l'opération (qui est...aucun). Puisqu'il n'y est pas de relation entre l'entrée et le nombre d'opérations effectuées, vous ne pouvez pas utiliser Big O décrire inexistante relation
O(max(1, 2035 - yearTheProgramIsStarted))
?IO
en Haskell) est un puits sans fond, donc si vous prenez en compte tout type d'interférence avec la machine qui exécute le programme, nous allons seulement obtenir ridicule les résultats jusqu'à l'incorporation de la mort thermique de l'univers 🙂DateTime
pour l'heure de début à l'entrée. Comme je l'ai dit plus tôt, l'horloge système peut changer au fil du temps. Et encore une fois, vous ne pouvez pas mapper directement la quazi d'entrée que vous décrivez pour une sortie fixée. Il n'est pas un nombre d'opérations effectuées pour une heure de début, ou même pour les deux programmes qui sont toujours un bon de la valeur deDateTime.Now
, de sorte que vous ne pouvez pas relier les deux que les changements de temps, parce que vous ne pouvez même pas se rapportent eux quand le temps ne pas modifier.Big-O notation signifie à peu près " en raison d'une opération sur une quantité de travail, N, combien de temps de calcul proportionnel à N, l'algorithme de prendre?'. Par exemple, le tri d'un tableau de taille N peut prendre N^2, Nlog(N), etc.
Cela n'a aucune quantité de données d'entrée pour agir sur. Il n'est donc pas
O(anything)
.Pire encore; ce n'est pas techniquement un algorithme. Un algorithme est une méthode pour le calcul de la valeur d'une fonction mathématique, fonctions mathématiques sont une cartographie à partir d'une entrée à une sortie. Puisque cela ne prend pas d'entrée et ne renvoie rien, ce n'est pas une fonction, au sens mathématique. De wikipedia:
Ce que c'est, techniquement, est un système de contrôle. De wikipedia,
Pour les gens qui veulent un peu plus en profondeur réponse à propos de la différence entre les fonctions mathématiques et les algorithmes, et le plus puissant des capacités des ordinateurs pour faire des côte-d'effectuer des choses comme la sortie de la console, l'affichage graphique, ou le contrôle de robots, ont un la lecture de cette feuille de papier sur le Fort de Church-Turing Hypothèse
Résumé
Non, votre code a le temps de la complexité de
O(2^|<DeltaTime>|)
,Pour un bon codage de l'heure actuelle.
S'il vous plaît, laissez-moi d'abord de m'excuser pour mon anglais.
Ce qui est et comment Big O travaille dans CS
Big O notation n'est pas utilisé pour attacher la saisie d'un programme avec son temps d'exécution.
Big O la notation est, laissant la rigueur derrière, une façon d'exprimer la asymptotique rapport de deux quantités.
Dans le cas de l'algorithme d'analyse de ces deux quantités sont pas l'entrée (pour lequel il faut d'abord avoir une "mesure" de la fonction) et le temps de fonctionnement.
Ils sont de la longueur du codage d'une instance du problème1 et une mesure de l'intérêt.
Les plus couramment utilisés sont les paramètres
Est implicitement supposé un TM comme le modèle ainsi que le premier point se traduit par la nombre d'applications de la transition2 la fonction, c'est à dire "étapes", et le second se traduit par le nombre de de bande différente des cellules écrit au moins une fois.
Est-il aussi souvent implicitement supposé que nous pouvons utiliser une polynomialement liées à l'encodage à la place de celui d'origine, par exemple une fonction qui recherche un tableau du début à la fin a
O(n)
complexité, malgré le fait que le codage d'une instance d'un tel tableau doit avoir la longueur den*b+(n-1)
oùb
est l' (constante) nombre de symboles de chaque élément. C'est parce queb
est considéré comme une constante du modèle de calcul et donc l'expression ci-dessus etn
sont asymptotiquement le même.Ce qui explique aussi pourquoi un algorithme comme le Division De Première Instance est un exponentielle algorithme malgré le fait d'être essentiellement un
for(i=2; i<=sqr(N); i++)
algorithme de type3.Voir cette.
Cela signifie également que big O la notation peut utiliser autant de paramètres, on peut à décrire le problème, n'est-il pas rare d'avoir un k paramètre pour certains algorithmes.
Donc ce n'est pas sur "entrée" ou que "il n'y a pas d'entrée".
Étude de cas maintenant
Big O la notation n'est pas question de votre algorithme, c'est juste suppose que vous savez ce que vous faites. C'est essentiellement un outil applicable partout, même à un algorithme, qui peut être délibérément difficile (comme le vôtre).
Pour résoudre votre problème, vous avez utilisé la date du jour et une date future, de sorte qu'ils doivent être une partie du problème en quelque sorte; il suffit de mettre: ils font partie de l'instance du problème.
Spécifiquement l'instance est:
<DeltaTime>
Où la
<>
signifie tout, non pathologique, de codage de choix.Voir ci-dessous pour très important précisions.
De sorte que votre grand O de la complexité en temps est juste
O(2^|<DeltaTime>|)
, parce que vous faites un certain nombre d'itération qui dépend de la valeur de temps en cours.Il est inutile de mettre les autres constantes numériques comme la notation asymptotique est utile, car elle élimine les constantes (ainsi, par exemple, l'utilisation de
O(10^|<DeltaTime>|*any_time_unit)
est inutile).Où la partie la plus délicate est
Nous avons fait une hypothèse importante ci-dessus: le fait que le modèle de calcul reificates5 de temps, et par le temps, je veux dire la (vraie?) le temps physique.
Il n'y a pas un tel concept dans la norme, modèle de calcul, un TM ne sais pas le temps, nous le lien du temps avec le nombre d'étapes car c'est notre réalité de travail4.
Dans votre modèle, cependant le temps est de la partie de calcul, vous pouvez utiliser la terminologie de la fonctionnelle de gens en disant que le Principal n'est pas pure, mais le concept est le même.
Pour comprendre cela, il convient de noter que rien n'empêche le Cadre à l'aide d'un faux temps qui courent deux fois, cinq, dix fois plus rapide que le temps physique. De cette façon, votre code sera exécuté dans un "demi", "un cinquième", "un dixième" de "temps".
Cette réflexion est importante pour choisir l'encodage de
<DeltaTime>
, c'est essentiellement un condensé façon d'écrire <(CurrentTime, TimeInFuture)>.Puisque le temps n'existe pas au prieuré, le codage de CurrentTime pourrait très bien être le mot Maintenant (ou autre choix) le jour avant pourrait être codé comme Hier, il y en brisant l'hypothèse que la longueur du codage augmentation que le temps physique va de l'avant (et l'un des DeltaTime diminue)
Nous avons correctement le modèle de temps dans notre modèle de calcul afin de faire quelque chose d'utile.
Le seul choix que nous pouvons faire est de coder les horodatages avec l'augmentation des longueurs (mais pas encore à l'aide de unaire) que le temps physique de l'avant. C'est le seul vrai bien de temps dont nous avons besoin et celui de l'encodage des besoins de l'attraper.
Est-ce qu'avec ce type de codage que votre algorithme peut être donné une fois de la complexité.
Votre confusion, le cas échéant, résulter du fait que le mot temps dans les phrases "qu'est-Ce que sa temps complexité?" et "Combien temps cela prend-il?" pour les très très différentes choses
Hélas la terminologie utiliser les mêmes mots, mais vous pouvez essayer d'utiliser "les étapes de la complexité" dans votre tête et re-poser votre question, j'espère que cela va vous aider à comprendre la réponse est vraiment ^_^
1 Ce qui explique aussi la nécessité d'une approche asymptotique que chaque instance a un autre, mais non arbitraire, de la longueur.
2 j'espère que je suis en utilisant le terme correct en anglais ici.
3 Aussi, c'est pourquoi on trouve souvent dans les
log(log(n))
termes dans le calcul.4 Id est, une étape doit occuper une partie finie, mais pas nulle, ni pas connecté, l'intervalle de temps.
5 Cela signifie que le mode de calcul en tant que connaissance de la physique du temps, c'est peut l'exprimer avec ses termes. Une analogie sont comment les génériques de travail dans le .NET framework.
O(2^n)
? Il n'est pas clair pour les débutants.O(2^|<DeltaTime>|)
- en affirmant que cela signifie "O(2^[la longueur de la représentation de DeltaTime)]" (pas de "O(2^[la valeur absolue de DeltaTime])"), ainsi qu'avec des explications sur pourquoi la durée de DeltaTime de représentation de la matière - qui est, ce que l'opération est réalisé sur la base du nombre de bits de rendre cette réponse beaucoup plus claire et vraiment génial.for(i = k1; i < k2; i++)
. La complexité du temps de cet extrait estO(2^|<k2-k1>|)
. De manière informelle, il est souvent dit qu'il a de la complexitéO(k2-k1)
, c'est-à-linéaire dans le DeltaK. Mais c'est un abus. Sik1
etk2
les nombres décimaux avec 3 chiffres (y compris de grandes 0s), leurs valeurs sont de l'ordre de 10^3. Si ils étaient 4 chiffres de leurs valeurs serait de l'ordre de 10^4, et ainsi de suite. C'est comment big O notation est utilisée dans les CS. Vous avez raison, cependant, je l' vraiment devrait faire cette réponse plus claire! J'ai perdu quelque chose dans la traduction 🙁DeltaTime
à la place de son valeur, vous êtes juste à ajouter de la confusion. Par exemple, mais ce raisonnement n'optimale de l'algorithme de tri a le temps de la complexité $O(n\cdot log n)$. Pourquoi? Parce que vous vous uniquement finitely de nombreux distinguer les objets à trier, dans ce cas, vous pouvez toujours utiliser un seau de tri pour trier en $O(n)$. Ou votre la taille de l'objet est sans limite, auquel cas $O(n\cdot log n)$ ne tiendra pas, car un seul de comparaison n'aurez pas de temps constant...plusn
éléments peuvent être codées avecn*b + n-1 + 2
. Notez comment, ici, la longueur est proportionnelle à la valeur den
. Cependant lors du codage d'un entierk
la longueur du codage est proportionnelle àlog n
. Ainsi, le tri de réduire la complexité estO(n log n)
, oùn
est le nombre d'éléments. Si la taille de chaque élément est illimitée, on ne peut même pas comparer les éléments de fini le temps.log k
paslog n
Bien qu'il existe un tas de réponses grands ici, permettez-moi de reformuler tous un peu.
Big-O notation existe pour décrire fonctions. Lorsqu'il est appliqué à l'analyse d'algorithmes cela exige de nous d'abord à définir certaines caractéristiques de cet algorithme en termes de fonction. Le choix commun envisage certain nombre de mesures en fonction de taille d'entrée. Comme indiqué dans d'autres réponses, à venir avec une telle fonction dans votre cas semble étrange, car il n'est pas clairement défini "entrée". On peut toujours essayer de le faire, si:
TwentyYearsLater
que l'entrée "-taille"-comme paramètre d'intérêt. Dans ce cas, le moteur d'exécution est f(n) = (n-x) où x est le "maintenant le moment" au moment de l'invocation. Vu de cette façon, il est un O(n) en temps de l'algorithme. S'attendre à ce contre-argument à chaque fois que vous allez montrer votre techniquement O(1)-algorithme de à d'autres personnes.TwentyYearsLater
est l'entrée, puis son taille n est, en fait, le nombre de bits nécessaires pour représenter, par exemple, n = log(k). La dépendance entre la taille de l'entrée de n et d'exécution est donc f(n) = 2^n - x. Semble que votre algorithme est juste devenue exponentielle lent! Ugh.DateTime.Now
invocations dans la boucle. On peut effectivement imaginer que toute cette séquence est fourni en entrée, pour le moment, nous exécuter le programme. Le moteur d'exécution peut alors être considéré dépendent de la propriété de cette séquence - à savoir sa longueur jusqu'à la premièreTwentyYearsLater
élément. Dans ce cas, le moteur d'exécution est de nouveau f(n) = n et l'algorithme est O(n).Mais encore une fois, dans votre question, vous n'avez même pas dire que vous avez été intéressé par de l'exécution. Que si tu voulais parler de l'utilisation de la mémoire? Selon comment le modèle de la situation, on peut dire que l'algorithme est O(1)-mémoire ou, peut-être, O(n)-mémoire (si la mise en œuvre de
DateTime.Now
nécessite de garder une trace de l'ensemble de l'invocation de la séquence somewhy).Et si votre objectif est d'en arriver à quelque chose d'absurde, pourquoi ne pas vous allez tous dire que vous êtes intéressé à la façon dont la taille de l'algorithme en code en pixels sur l'écran dépend du niveau de zoom choisi. Cela pourrait être quelque chose comme f(zoom) = 1/zoom et vous pouvez fièrement déclarer votre algorithme à O(1/n)-taille de pixel!
DateTime.Now
invocations " est la véritable entrée ici. Mais je pense que la conclusion ne doit pas être que c'est O(n), mais il est O(k), où k est la longueur jusqu'à la premièreTwentyYearsLater
élément.Je suis en désaccord avec Servy légèrement. Il y a une entrée à ce programme, même s'il n'est pas évident, et c'est le système du temps. Ce pourrait être une technicité vous n'aviez pas prévu, mais votre
TwentyYearsFromNow
variable n'est pas vingt ans à compter de la système est maintenant temps, il est affecté de manière statique au 1er janvier 2035.Donc, si vous prenez ce code et l'exécuter sur une machine qui a un système de temps du 1er janvier 1970, il va prendre de 65 ans, quelle que soit la vitesse de l'ordinateur (il peut y avoir une certaine variation si son horloge est défectueux). Si vous prenez ce code et de l'exécuter sur une machine qui a un système de temps de 2 janvier 2035, il sera terminé presque instantanément.
Je dirais que votre entrée,
n
, estJanuary 1st, 2035 - DateTime.Now
, et il est O(n).Puis il y a aussi la question du nombre d'opérations. Certaines personnes ont remarqué que les ordinateurs plus rapides, le succès à la boucle rapidement, causant plus d'opérations, mais c'est hors de propos. Lorsque vous travaillez avec des big-O de notation, nous ne tenons pas compte de la vitesse du processeur ou le nombre exact des opérations. Si vous avez pris cet algorithme et il a couru sur un ordinateur, et puis il a couru de nouveau, mais pour 10x plus de temps sur le même ordinateur, vous vous attendez à ce que le nombre d'opérations de croissance par le même facteur de 10x.
Que pour cela:
Non, pas vraiment. D'autres réponses ont couvert ce, donc, je voulais juste le mentionner. Vous ne pouvez pas généralement en corrélation années d'exécution de tout big-O de notation. Par exemple. Il n'y a aucun moyen de dire 20 ans d'exécution = O(n^87) ou quoi que ce soit d'autre d'ailleurs. Même dans l'algorithme que vous avez donné, je pouvais changer le
TwentyYearsFromNow
de l'année 20110, 75699436, ou 123456789 et le big-O est toujours en O(n).When working with big-O notation, we don't consider the speed of the processor or the exact number of operations.
C'est une fausse déclaration. Assez beaucoup n'importe quelle opération que vous essayez de calculer le Big O valeur ne changera pas le nombre d'opérations effectuées en fonction du matériel, mais celui-ci n'. Big O est juste un moyen de relier le nombre d'opérations à la taille de l'entrée. Pour la plupart des opérations, qui est indépendant du matériel du système. Dans ce cas, il n'est pas.If you took this algorithm and ran it on a computer, and then ran it again but for 10x longer on the same computer, you would expect the number of operations to grow by the same factor of 10x.
C'est aussi une fausse déclaration. L'environnement n'est pas nécessairement de modifier le nombre d'opérations dans la boucle de façon linéaire. Il pourrait, par exemple, être d'autres programmes sur l'ordinateur qui utilisent plus ou moins de temps PROCESSEUR à différents points dans le temps, en changeant le temps donné à cette demande constamment au fil du temps.Big-O de l'analyse traite de la quantité de traitement impliqués comme la quantité de données traitées augmente sans limite.
Ici, vous êtes vraiment seulement affaire qu'à un seul objet de taille fixe. En tant que tel, l'application de big-O de l'analyse dépend fortement (surtout?) sur la façon dont vous définissez vos termes.
Par exemple, vous pourriez dire de l'impression en général, et en imposant une attente si longue que toute quantité raisonnable de données serait/sera imprimé exactement dans la même période de temps. Vous devez également ajouter un peu plus dans la voie d'un peu inhabituel (pour ne pas dire mauvais) définitions pour aller très loin si--en particulier, big-O de l'analyse est généralement définie en termes de nombre d'opérations fondamentales nécessaires pour effectuer une tâche particulière (mais notez que la complexité peut aussi être considéré en termes de choses comme l'utilisation de la mémoire, et pas seulement l'utilisation de l'UC/opérations effectuées).
Le nombre d'opérations fondamentales se traduit généralement assez étroitement à temps, cependant, il n'est donc pas une immense étendue de traiter les deux sont synonymes. Malheureusement, cependant, nous sommes encore coincés avec l'autre partie: la quantité de données traitées augmente sans limite. Cela étant le cas, aucun retard fixes, vous pouvez imposer fonctionnera vraiment. Assimiler O(1) O(N), vous auriez à imposer une infinité de retard, de sorte que tout montant fixe de données a pris une éternité à l'impression, tout comme une quantité infinie de données.
big-O par rapport à quoi?
Vous semblez être l'intuition qu'
twentyYearsLater
est une "entrée". En effet, si vous avez écrit votre fonction en tant queIl serait O(N) où N = ans (ou juste dire
O(years)
).Je dirais que votre algorithme est O(N) par rapport à ce nombre il vous arrive d'écrire dans la ligne de code commençant par
twentyYearsLater =
. Mais les gens font habituellement pas compte des numéros dans le code source que l'entrée. Ils pourraient considérer l'entrée de ligne de commande comme entrée, ou la signature de la fonction entrée de l'entrée, mais, probablement pas le code source lui-même. C'est ce que vous vous disputez avec votre ami, est - ce la "entrée"? Vous définissez votre code de manière à la rendre intuitivement ressembler à une entrée, et vous pouvez certainement demander à son grand O temps d'exécution avec le nombre N à la ligne 6 de votre programme, mais si vous utilisez un tel non-choix par défaut en entrée vous avez vraiment besoin d'être explicite à ce sujet.Mais si vous prenez l'entrée à quelque chose de plus habituelles, comme la ligne de commande ou l'entrée à la fonction, il n'y a pas de sortie à tous et que la fonction est en O(1). Il faut vingt ans, mais depuis le big-O ne change pas jusqu'à une constante multiples, O(1) = O(vingt ans).
La même question - quelle est la durée d':
En supposant qu'elle fait ce qu'elle dit et l'entrée est valide, et l'algorithme de harnais d'un quicksort ou de tri à bulles ou quoi que ce soit raisonnable, c'est O(1).
Cet "algorithme" est correctement décrit comme O(1) ou à temps constant. Il a été avancé qu'il n'y a pas d'entrée de ce programme, donc il n'est pas N d'analyser en termes de Big Oh. Je suis en désaccord qu'il n'y a pas d'entrée. Lorsque cela est compilé dans un fichier exécutable et de l'appelé, l'utilisateur peut spécifier n'importe quelle entrée de longueur arbitraire. Qui d'entrée de longueur est le N.
Le programme ignore l'entrée (de n'importe quelle longueur), de sorte que le temps pris (ou le nombre d'instructions machine exécutée) est la même quelle que soit la longueur de l'entrée (fixe donné environnement = heure de début + matériel), donc O(1).
Let's suppose that there is a finite lower bound on the amount of time a loop iteration takes
C'est une fausse hypothèse. Le programme peut toujours courir. Tout ce que j'ai à faire est d'installer mon système d'horloge à 50 ans à partir de maintenant, le lancer, et ça va jamais finir. Ou je pourrais continuer d'avancer l'horloge de retour plus vite qu'il se déplace vers l'avant, ou de commencer à un moment indéterminé dans le passé. Vous simplement ne peut pas supposer qu'il y a une borne inférieure sur combien de temps le programme s'exécute, il peut toujours courir. Mais, même si nous prenons votre (faux) hypothèse est vraie, vous ne pouvez toujours pas de rapporter le nombre d'opérations effectuées à l'entrée.Une chose que je suis surpris n'a pas encore été mentionnés:-big-O notation est une limite supérieure!
La question tout le monde a remarqué, c'est qu'il n'est pas N décrivant les entrées de l'algorithme, donc il n'y a rien à faire big-O de l'analyse. Cependant, cela est facilement atténués avec la ruse, comme l'acceptation d'une
int n
et l'impression de "Hello World"n
fois. Qui serait autour de plainte et de revenir à la vraie question de savoir commentDateTime
monstruosité œuvres.Il n'y a aucune garantie que la boucle while va jamais se terminer. Nous aimons à penser qu'il a au certains temps, mais nous considérons que
DateTime.now
renvoie la date et l'heure système. Il n'y a effectivement aucune garantie que cela est de plus en plus monotone. Il est possible qu'il y est quelques pathologiquement singe dressé en constante évolution, le système de la date et de l'heure de retour à octobre 21, 2015 12:00:00 UTC jusqu'à ce que quelqu'un donne le singe quelques auto-montage de chaussures et un hoverboard. Cette boucle peut même courir pour une quantité infinie de temps!En fait, quand vous creusez dans la définition mathématique de big-O notations, ils sont les limites supérieures. Ils démontrent le pire des cas, peu importe combien peu probable. Le pire des cas* scénario ici est infini et l'exécution, de sorte que nous sommes obligés de déclarer que il n'y a pas de big-O notation pour décrire l'exécution de la complexité de cet algorithme. Il se complique pas exister, comme 1/0 n'existe pas.
* Edit: a partir de ma discussion avec KT, il n'est pas toujours valable à présumer que le scénario que nous modélisation avec big-O de notation est le pire des cas. Dans la plupart des cas, si une personne omet de préciser auquel cas nous utilisons, ils visent à explorer le pire des cas. Cependant, vous pouvez faire un big-O de l'analyse de la complexité sur le meilleur moment de l'exécution.
f
et déclarer une fonctiong
être le même quef
, mais avec un domaine limité à seulement incluref
's dans le meilleur des cas, et puis faire grand-oh surg
, mais il commence à sonner dégénérer lorsque vous faites cela.Complexité est utilisé pour mesurer de calcul "des chevaux" en termes de temps/espace. Big O notation est utilisée pour comparer des problèmes qui sont "calculable" ou "pas calculable" et aussi pour comparer les solutions -les algorithmes - sont mieux que d'autres. En tant que tel, vous pouvez diviser l'algorithme en deux catégories: ceux qui peuvent être résolus en temps polynomial et ceux qui ne le peuvent pas.
Problèmes, comme le Crible d'Erathostene O(n ^exp) et sont donc résoluble pour de petites valeurs de n. Ils sont calculables en temps polynomial (NP) et donc lorsque l'on a demandé si un nombre donné est premier ou non, la réponse dépend sur l'ampleur de ce nombre. En outre, la complexité ne dépend pas du matériel, afin d'avoir des ordinateurs plus rapides, rien ne change...
Bonjour tout le Monde, n'est pas un algorithme, et en tant que tel est insensé de tenter de déterminer sa complexité-qui n'en est pas. Un algorithme simple peut être quelque chose comme: étant donné un nombre aléatoire, de déterminer s'il est pair ou impair. Maintenant, il importe que le nombre donné a 500 chiffres? Non, parce que vous n'avez qu'à vérifier si le dernier chiffre est pair ou impair. Un algorithme plus complexe serait de déterminer si un nombre donné répartit uniformément par 3. Bien que certains numéros sont "faciles" à calculer, d'autres sont en "dur" et c'est à cause de son ampleur: comparer le temps qu'il faut pour déterminer la remaninder entre un nombre à un chiffre et d'autres, avec plus de 500 chiffres.
De plus en plus complexes, ce serait le cas pour décoder un texte. Vous avez une apparente ensemble aléatoire de symboles qui vous le savez sont véhiculer un message pour ceux qui ont la clé de décryptage. Disons que l'expéditeur a utilisé la clé vers la gauche et votre Bonjour tout le Monde pourra lire: Gwkki Qieks. Le "big-marteau, no-brain" la solution serait de produire toutes les combinaisons de ces lettres: a partir de Aaaa à Zzzz, puis rechercher un dictionnaire de mots à identifier les mots qui sont valides et partager les deux lettres en commun dans le cypher (i, k) dans la même position. Cette fonction de transformation est ce que Big O mesures de!
La plupart des gens semblent être à côté de deux choses très importantes.
Le programme ne ont une entrée. Il est codé en dur date/heure
contre lequel le système de temps est comparé. Les entrées sont sous le contrôle de la personne de l'exécution de l'algorithme,et l'heure du système ne l'est pas. La seule chose que la personne qui exécute ce programme peut contrôler, c'est la date/heure ils ont codé en dur dans la comparaison.
Le programme varie en fonction de l'entrée valeur, mais pas la taille de l'entrée ensemble, ce qui est le big-O notation est concernés par.
Par conséquent, il est de durée indéterminée, et le meilleur "big O" de notation pour ce programme serait probablement O(null), ou, éventuellement, O(NaN).
Tout le monde l'a souligné à juste titre que vous ne définissez pas N, mais la réponse est non en vertu de la plupart interprétation raisonnable. Si N est la longueur de la chaîne, nous sommes d'impression et de “hello, world!” est juste un exemple, comme on pourrait le déduire de la description de ce qu'est un algorithme “pour
hello, world!
”, alors l'algorithme est O(N), car vous pourriez avoir une sortie de chaîne de caractères qui prend trente, quarante ou cinquante ans à l'impression, et vous êtes en train d'ajouter qu'une constante de temps pour que. O(kN+c) ∈ O(N).Addendum:
À ma grande surprise, quelqu'un conteste cette. Rappeler les définitions de big O et grand Θ. Supposons que nous avons un algorithme qui attend une quantité constante de temps c puis imprime un message de longueur N dans le temps linéaire. (C'est une généralisation de l'original du code de l'échantillon.) Nous allons arbitrairement dire que nous nous attendre vingt ans pour lancer l'impression, et que l'impression d'un billion de personnages prend une vingtaine d'années. Laissez c = 20 et k = 1012, par exemple, mais tout réel positif numéros de le faire. C'est un taux de d = c/k (dans ce cas 2×10-11) ans par caractère, de sorte que notre temps d'exécution f(N) est asymptotiquement dN+c ans. Chaque fois que N > k, dN = c/k N > c. Par conséquent, dN < dN+c = f(N) < 2 dN pour tous N > k, et f(N) ∈ Θ(N). Q. E. D.
hello, world!
que l'entrée qui est autorisé à varier et N que sa longueur est le choix naturel basé sur la description. Je suis désolé que le point a volé au-dessus de votre tête et vous m'avez mal compris, comme disent quelque chose de différent. Je ne pense pas que la poursuite de la discussion serait productive.hello, world!
un exemple plutôt que la seule chose qu'il ait jamais imprime, à la discussion de son temps à la complexité a un sens, et nous pouvons aborder le vrai point de la question, qui est de savoir si l'ajout d'une grande constante au moment de l'exécution des modifications à l'ordre de son temps à la complexité. (No.) Crier les uns sur les autres ne sert à rien. J'espère vous revoir votre downvote.Je pense que les gens sont jetés parce que le code n'a pas look comme une tradition de l'algorithme. Voici une traduction du code qui est le plus bien-formé, mais reste fidèle à l'esprit de l'OP de la question.
Les entrées sont explicites, alors qu'avant, ils étaient implicitement donné par le temps, le code a été commencé à et par la vitesse du matériel de l'exécution du code. Le code est déterministe et a un domaine bien défini de sortie pour des entrées données.
En raison des limitations qui sont imposées sur les entrées, nous pouvons fournir, il existe une limite supérieure pour le nombre d'opérations qui seront exécutées, de sorte que cet algorithme est en fait en O(1).
À ce point dans le temps, oui
Cet algorithme implicite d'entrée, à savoir le temps que le programme est commencé. Le temps d'exécution varie linéairement1 selon le moment où il est lancé. Au cours de l'année 2035, et après, la boucle while se termine immédiatement et le programme s'arrête après la constante d'opérations2. Ainsi, il pourrait être dit que le moteur d'exécution est
O(max(2035 - start year, 1))
3. Mais depuis notre début de l'année a une valeur minimale, l'algorithme ne prendra jamais plus de 20 ans à exécuter (c'est à dire une valeur constante).Vous pouvez faire de votre algorithme plus conforme à votre intention par la définition de
DateTime TwentyYearsLater = DateTime.Now + new TimeSpan(365*20,0,0,0);
41 Ce qui vaut pour le plus de sens technique du terme de temps d'exécution mesuré en nombre d'opérations, car il y a un nombre maximum d'opérations par unité de temps.
2 en Supposant que l'extraction de
DateTime.Now
est une constante de l'opération, ce qui est raisonnable.3 je suis un peu abuser de big O la notation ici parce que c'est une fonction décroissante à l'égard de
start year
, mais on pourrait facilement remédier à cela en les exprimant en termes deyears prior to 2035
.4 Ensuite, l'algorithme ne dépend plus de l'implicite à l'entrée de l'heure de début, mais ça n'a pas de conséquence.
Je dirais que c'est O(n).
à l'aide de http://www.cforcoding.com/2009/07/plain-english-explanation-of-big-o.html comme une référence.
et
Pour votre exemple,
compte tenu de l'entrée de n = 20 (avec des unités ans).
l'algorithme est une fonction mathématique f(). où f() se trouve être attendre la n des années, avec 'debug' chaînes de caractères entre les deux. Le facteur d'échelle est de 1. f() peut être réduit ou augmenté par l'évolution de ce facteur d'échelle.
pour ce cas, la sortie est également à 20 (modification de l'entrée à la sortie linéaire).
essentiellement la fonction est