C’est techniquement un algorithme d’o (1) pour « Hello World » ?

Question

Serait ce considéré comme un algorithme d’o (1) pour « Hello, World ! » ??

Je suis à l’aide du

extrait de code comme une boucle occupée à mettre en comme une plaisanterie, chaque fois que quelqu'un demande un algorithme d’une certaine complexité. Cela serait correct ?

Answer 1

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épendante 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 pour décrire cette non-relation existant entre

Answer 2

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?'. 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. 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:

Un algorithme est une méthode efficace qui peut être exprimé dans un quantité limitée d'espace et de temps et dans des conditions bien définies langage formel pour le calcul d'une fonction. Partant d'un état initial et initiale d'entrée (peut-être vide), le mode d'emploi décrit un calcul qui, lorsqu'il est exécuté, produit par un nombre fini de bien défini les états successifs, finalement, la production de "sortie" et se terminant sur un final de l'état.

Ce que c'est, techniquement, est un système de contrôle. À partir de wikipedia;

Un système de contrôle est un dispositif ou ensemble de dispositifs, qui gère, commandes, dirige ou réglemente le comportement des autres appareils ou les systèmes.

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 une lecture de ce document sur le Fort de Church-Turing Hypothèse

Résumé

La vision classique du calcul des positions de calcul comme une boîte fermée de transformation des intrants (les nombres rationnels ou finis de chaînes de caractères) pour les sorties. Selon l'affichage interactif de calcul, le calcul est un cours interactif plutôt qu'une fonction basée sur la transformation d'une entrée à une sortie. Plus précisément, la communication avec le monde extérieur qui se passe pendant le calcul, et non pas avant ou après. Cette approche modifie radicalement notre compréhension de ce qu'est le calcul et la façon dont il s'inspire.

L'acceptation de l'interaction comme un nouveau paradigme est entravée par la Forte Thèse de Church-Turing (SCT), la croyance répandue que les Machines de Turing (TMs) de capture de tout calcul, de sorte que les modèles de calcul plus expressive que les TMs sont impossibles. Dans ce papier, nous montrons que le SCT réinterprète l'original de la Thèse de Church-Turing (CTT) de manière à ce que Turing n'a jamais prévu; ses communément admis l'équivalence de l'original est un mythe. Nous avons d'identifier et d'analyser les raisons historiques de la croyance répandue dans le SCT. Seulement en acceptant qu'il est faux que nous pouvons commencer à adopter l'interaction comme un paradigme alternatif de calcul

Answer 3

Non, votre code a le temps de la complexité de l' 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.

Qu'est-ce que et comment Big O travaille dans CS

Big O la 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 grandeurs sont pas l'entrée (pour lequel il faut d'abord avoir une "mesure" de la fonction) et le temps d'exécution.
Ils sont de la longueur du codage d'une instance du problème¹ et une mesure de l'intérêt.

Les plus couramment utilisés sont les paramètres

1. Le nombre d'étapes nécessaires pour compléter l'algorithme dans un modèle de calcul.
2. L'espace requis, si un tel concept existe, par le modèle de calcul.

Est implicitement supposé un TM comme le modèle ainsi que le premier point se traduit par le nombre de demandes de la transition² fonction, c'est à dire "étapes", et le second se traduit par le nombre 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) de la complexité, malgré le fait que le codage d'une instance d'un tel tableau doit avoir une longueur d' n*b+(n-1) où b (constante) nombre de symboles de chaque élément. C'est parce qu' b est considéré comme une constante du modèle de calcul et donc l'expression ci-dessus et n sont asymptotiquement le même.

Cela explique aussi pourquoi un algorithme semblable à la Division de première instance est une exponentielle algorithme malgré le fait d'être essentiellement un for(i=2; i<=sqr(N); i++) algorithme de type³.

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 à propos de la "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.

Plus précisément l'instance est:

<DeltaTime>

Où l' <> signifie tout, non pathologique, de codage de choix.

Voir ci-dessous pour les très importantes précisions.

Si 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 d' 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 reificates⁵ fois, 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 travail⁴.

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 le choix de l'encodage d' <DeltaTime>, ce qui est essentiellement un condensé de l'écriture <(CurrentTime, TimeInFuture)>. Puisque le temps n'existe pas au prieuré, le codage de CurrentTime pourrait très bien être la parole 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 de la physique temps 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 son temps de la complexité?" et "Combien de temps cela prend-il?" pour les très très différente des 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 ^_^

---

¹ Ce qui explique aussi la nécessité d'une approche asymptotique que chaque instance a un autre, mais non arbitraire, de la longueur.
² j'espère que je suis en utilisant le terme correct en anglais ici.
³ Aussi c'est pourquoi on trouve souvent des log(log(n)) termes dans le calcul.
⁴ Id est, une étape doit occuper une partie finie, mais pas nulle, ni pas connecté, l'intervalle de temps.
⁵ 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.

Answer 4

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 les 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 la taille de l'image. 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:

• On peut considérer un algorithme comme une constante fonction qui prend en entrée de n'importe quelle taille, l'ignore, attend un montant fixe de temps, et de finitions. Dans ce cas, son exécution est f(n) = const, et c'est un O(1)-temps de l'algorithme. C'est ce que vous vous attendiez à entendre, non? Oui, il est, techniquement, un O(1)-algorithme.
• On peut considérer l' 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 à d'autres personnes.
• Oh, mais attendez, si k=TwentyYearsLater est l'entrée, puis sa 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 la n de l'exécution et est donc f(n) = 2^n - x. Semble que votre algorithme est juste devenue exponentielle lent! Ugh.
• Une autre entrée pour le programme est en fait le flux de réponses données par le système d'exploitation de la séquence de DateTime.Now des 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ère TwentyYearsLater élément. Dans ce cas, le moteur d'exécution est de nouveau f(n) = n et que 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 l' 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 en O(1/n)-taille de pixel!

Answer 5

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, le système de temps maintenant, 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, January 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.

Pour cela:

Je suis en train de penser à l'aide de la [rédigé le code] 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?

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 l' TwentyYearsFromNow pour l'année 20110, 75699436, ou 123456789 et le big-O est toujours en O(n).