Serait-ce classé 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 pense utiliser le

DateTime TwentyYearsLater = new DateTime(2035,01,01);
while ( DateTime.Now < TwentyYearsLater )
{ 
   // ... 
}

extrait de code comme une boucle occupée à mettre en blague chaque fois que quelqu'un demande un algorithme d'une certaine complexité. Serait-ce correct?

La notation Big O dans ce contexte est utilisée 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 pour cette entrée.

Votre opération n'a pas d'entrée à laquelle la sortie peut être liée, donc l'utilisation de la notation Big O n'a pas de sens. Le temps que prend l'opération est indépendant des entrées de l'opération (qui est ... aucune). Comme il n'y a 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 relation inexistante

La notation Big-O signifie à peu près «étant donné une opération sur une quantité de travail, N, combien de temps de calcul, proportionnel à N, prend 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 sur lesquelles agir. Donc ce n'est pas le cas O(anything).

Encore pire; ce n'est pas techniquement un algorithme. Un algorithme est une méthode de calcul de la valeur d'une fonction mathématique - les fonctions mathématiques sont un mappage d'une entrée à une sortie. Comme cela ne prend aucune 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ée dans une quantité finie d'espace et de temps et dans un langage formel bien défini pour le calcul d'une fonction. Partant d'un état initial et d'une entrée initiale (peut-être vide), les instructions décrivent un calcul qui, lorsqu'il est exécuté, passe par un nombre fini d'états successifs bien définis, produisant finalement une "sortie" et se terminant à un état final final.

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

Un système de contrôle est un appareil, ou un ensemble d'appareils, qui gère, commande, dirige ou régule le comportement d'autres appareils ou systèmes.

Pour les personnes souhaitant une réponse plus approfondie sur la différence entre les fonctions mathématiques et les algorithmes, et les capacités plus puissantes des ordinateurs à effectuer des opérations secondaires telles que la sortie de la console, l'affichage de graphiques ou le contrôle de robots, lisez cet article sur le Hypothèse forte de Church-Turing

Abstrait

La vision classique du calcul positionne le calcul comme une transformation en boîte fermée d'entrées (nombres rationnels ou chaînes finies) en sorties. Selon la vision interactive de l'informatique, le calcul est un processus interactif continu plutôt qu'une transformation basée sur la fonction d'une entrée en une sortie. Plus précisément, la communication avec le monde extérieur se produit pendant le calcul, pas avant ou après. Cette approche change radicalement notre compréhension de ce qu'est le calcul et de sa modélisation.

L'acceptation de l'interaction en tant que nouveau paradigme est entravée par la Strong Church-Turing Thesis (SCT), la croyance répandue que les machines de Turing (TM) capturent tous les calculs, de sorte que les modèles de calcul plus expressifs que les TM sont impossibles. Dans cet article, nous montrons que SCT réinterprète la thèse originale de Church-Turing (CTT) d'une manière que Turing n'a jamais voulue; son équivalence communément supposée à l'original est un mythe. Nous identifions et analysons les raisons historiques de la croyance largement répandue en SCT. Ce n'est qu'en acceptant que c'est faux que nous pouvons commencer à adopter l'interaction comme paradigme alternatif du calcul

Non, votre code a une complexité temporelle de O(2^|<DeltaTime>|),

Pour un codage correct de l'heure actuelle.
S'il vous plaît, laissez-moi d'abord m'excuser pour mon anglais.

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

La notation Big O n'est pas utilisée pour lier l'entrée d'un programme à son temps d'exécution .
La notation Big O est, en laissant la rigueur derrière elle, un moyen d'exprimer le rapport asymptotique de deux quantités .

Dans le cas de l'analyse d'algorithme, ces deux grandeurs sont ne pas l'entrée (pour laquelle il faut d'abord avoir une fonction "mesure") et le temps d'exécution.
Ce sont la longueur du codage d'une instance du problème ¹ et une métrique d'intérêt.

Les métriques couramment utilisées sont

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

On suppose implicitement un TM comme modèle de sorte que le premier point se traduit par le nombre d'applications de la transition ² fonction de , c'est-à-dire «étapes», et le second traduit le nombre de cellules de bande différentes écrites au moins une fois .

Est-il aussi souvent supposé implicitement que nous pouvons utiliser un codage polynomialement lié au lieu de l'original, par exemple une fonction qui recherche un tableau du début à la fin est O(n)complexe malgré le fait qu'un codage d'une instance d'un tel tableau devrait avoir une longueur de n*b+(n-1)oùb est le nombre (constant) de symboles de chaque élément. En effet, il best considéré comme une constante du modèle de calcul et donc l'expression ci-dessus et nsont asymptotiquement identiques.

Cela explique également pourquoi un algorithme comme la Division de première instance est un algorithme exponentiel bien qu'il soit essentiellement un for(i=2; i<=sqr(N); i++)algorithme similaire ³ .

Voir ça .

Cela signifie également que la grande notation O peut utiliser autant de paramètres dont on peut avoir besoin pour décrire le problème, n'est-il pas inhabituel d'avoir un k paramètre pour certains algorithmes.

Donc ce n'est pas de "l'entrée" ou de "qu'il n'y a pas d'entrée".

Étude de cas maintenant

La notation Big O ne remet pas en question votre algorithme, elle suppose simplement 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 délicat (comme le vôtre).

Pour résoudre votre problème, vous avez utilisé la date actuelle et une date future, elles doivent donc faire partie du problème d'une manière ou d'une autre; en termes simples: ils font partie de l'instance du problème.

Plus précisément, l'instance est:

<DeltaTime>

Où le <>signifie un codage de choix, non pathologique.

Voir ci-dessous pour des clarifications très importantes .

Donc, votre grand temps de complexité O est juste O(2^|<DeltaTime>|), car vous effectuez un certain nombre d'itérations qui dépendent de la valeur du temps actuel. Il ne sert à rien de mettre d'autres constantes numériques car la notation asymptotique est utile car elle élimine les constantes (donc par exemple l'utilisation deO(10^|<DeltaTime>|*any_time_unit) est inutile).

Où est la partie délicate

Nous avons fait une hypothèse importante ci-dessus: que le modèle de calcul réifie ⁵ temps, et par temps j'entends le temps physique (réel?). Un tel concept n'existe pas dans le modèle de calcul standard, une MT ne connaît pas le temps, nous associons le temps au nombre d'étapes car c'est ainsi que fonctionne notre réalité ⁴ .

Dans votre modèle, cependant, le temps fait partie du calcul, vous pouvez utiliser la terminologie des personnes fonctionnelles en disant que Main n'est pas pur mais que le concept est le même.

Pour comprendre cela, il faut noter que rien n'empêche le Framework d'utiliser un faux temps qui s'exécute deux, cinq, dix fois plus vite que le temps physique. De cette façon, votre code fonctionnera dans «la moitié», «un cinquième», «un dixième» du «temps».

Cette réflexion est importante pour le choix du codage de <DeltaTime>, c'est essentiellement une manière condensée d'écrire <(CurrentTime, TimeInFuture)>. Puisque le temps n'existe pas au prieuré, le codage de CurrentTime pourrait très bien être le mot Now (ou tout autre choix) la veille pourrait être codé comme Hier , là en cassant l'hypothèse que la longueur du codage augmente avec le temps physique avance (et celui de DeltaTime diminue)

Nous devons modéliser correctement le temps dans notre modèle de calcul afin de faire quelque chose d'utile.

Le seul choix sûr que nous pouvons faire est d'encoder des horodatages avec des longueurs croissantes (mais toujours sans utiliser unaire) au fur et à mesure que le temps physique avance. C'est la seule vraie propriété du temps dont nous avons besoin et celle dont l'encodage a besoin pour capturer. Ce n'est qu'avec ce type d'encodage que votre algorithme peut avoir une complexité temporelle.

Votre confusion, le cas échéant, provient du fait que le mot temps dans les phrases «Quelle est sa complexité temporelle ? et "Combien de temps cela prendra-t-il?" signifie des choses très très différentes

Hélas, la terminologie utilise les mêmes mots, mais vous pouvez essayer d'utiliser "étapes de complexité" dans votre tête et vous poser à nouveau votre question, j'espère que cela vous aidera à comprendre que la réponse est vraiment ^ _ ^

¹ Cela explique aussi la nécessité d'une approche asymptotique que chaque instance a un autre, mais pas arbitraire, longueur.
² J'espère que j'utilise le terme anglais correct ici.
^C'est aussi pourquoi nous trouvons souvent des log(log(n))termes en mathématiques.
⁴ Id est, un pas doit occuper un intervalle de temps fini, mais non nul, ni non connexe.
⁵ Cela signifie que le mode de calcul en tant que connaissance du temps physique en elle, qui est peut l' exprimer à ses conditions. Une analogie est le fonctionnement des génériques dans le framework .NET.

Bien qu'il y ait un tas de bonnes réponses ici, permettez-moi de les reformuler un peu.

La notation Big-O existe pour décrire les fonctions . Lorsqu'il est appliqué à l'analyse d'algorithmes, cela nous oblige à définir d'abord certaines caractéristiques de cet algorithme en termes de fonction . Le choix courant consiste à considérer le nombre d'étapes en fonction de la taille d'entrée . Comme indiqué dans d'autres réponses, proposer une telle fonction dans votre cas semble étrange, car il n'y a pas d '«entrée» clairement définie. Nous pouvons toujours essayer de le faire:

• Nous pouvons considérer votre algorithme comme une fonction constante qui prend toute entrée de n'importe quelle taille, l'ignore, attend un laps de temps fixe et se termine. Dans ce cas, son runtime est f (n) = const , et c'est un algorithme O (1) -time. C'est ce que vous vous attendiez à entendre, non? Oui, c'est, techniquement, un algorithme O (1) .
• Nous pouvons considérer le TwentyYearsLatercomme le paramètre d'intérêt semblable à la "taille d'entrée". Dans ce cas, le runtime est f (n) = (nx) où x est le "moment présent" au moment de l'invocation. Vu de cette façon, il s'agit d'un algorithme à temps O (n). Attendez-vous à ce contre-argument chaque fois que vous montrez votre algorithme techniquement O (1) à d'autres personnes.
• Oh, mais attendez, si k =TwentyYearsLater est l'entrée, alors sa taille n est, en fait, le nombre de bits nécessaires pour la représenter, c'est-à-dire n = log (k) . La dépendance entre la taille de l'entrée n et le runtime est donc f (n) = 2 ^ n - x . On dirait que votre algorithme est devenu exponentiellement lent! Pouah.
• Une autre entrée du programme est en fait le flux de réponses donné par le système d'exploitation à la séquence d' DateTime.Nowappels dans la boucle. Nous pouvons en fait imaginer que toute cette séquence est fournie en entrée au moment où nous exécutons le programme. Le runtime peut alors être considéré comme dépendant de la propriété de cette séquence - à savoir sa longueur jusqu'au premier TwentyYearsLaterélément. Dans ce cas, le runtime est à nouveau f (n) = n et l'algorithme est O (n) .

Mais là encore, dans votre question, vous n'avez même pas dit que vous étiez intéressé par le runtime. Et si vous parliez de l'utilisation de la mémoire? En fonction de la manière dont vous modélisez la situation, vous pouvez dire que l'algorithme est O (1) -memory ou, peut-être, O (n) -memory (si l'implémentation de DateTime.Nownécessite de garder une trace de toute la séquence d'invocation, quelque part).

Et si votre objectif était de trouver quelque chose d'absurde, pourquoi ne pas aller à fond et dire que vous vous intéressez à la façon dont la taille du code de l'algorithme en pixels à l'écran dépend du niveau de zoom choisi. Cela pourrait être quelque chose comme f (zoom) = 1 / zoom et vous pouvez déclarer fièrement que votre algorithme est de taille O (1 / n) -pixel!

Je suis légèrement en désaccord avec Servy. Il y a une entrée dans ce programme, même si ce n'est pas évident, et c'est l'heure du système. C'est peut-être une technicité que vous n'aviez pas prévue, mais votre TwentyYearsFromNowvariable n'est pas dans vingt ans à partir de l' époque du système , elle est attribuée statiquement au 1er janvier 2035.

Donc, si vous prenez ce code et que vous l'exécutez sur une machine dont l'heure système est le 1er janvier 1970, cela prendra 65 ans, quelle que soit la vitesse de l'ordinateur (il peut y avoir des variations si son horloge est défectueuse ). Si vous prenez ce code et que vous l'exécutez sur une machine dont l'heure système est le 2 janvier 2035, il se terminera presque instantanément.

Je dirais que votre entrée, nest January 1st, 2035 - DateTime.Now, et c'est O (n).

Ensuite, il y a aussi la question du nombre d'opérations. Certaines personnes ont noté que des ordinateurs plus rapides atteindraient la boucle plus rapidement, entraînant plus d'opérations, mais ce n'est pas pertinent. Lorsque vous travaillez avec la notation big-O, nous ne considérons pas la vitesse du processeur ou le nombre exact d'opérations. Si vous avez pris cet algorithme et que vous l'exécutez sur un ordinateur, puis que vous l'exécutez à nouveau, mais pendant 10 fois plus longtemps sur le même ordinateur, vous vous attendez à ce que le nombre d'opérations augmente du même facteur de 10x.

Quant à ceci:

Je pense utiliser l'extrait de code [code rédigé] comme une boucle occupée à mettre en plaisanterie chaque fois que quelqu'un demande un algorithme d'une certaine complexité. Serait-ce correct?

Non, pas vraiment. D'autres réponses ont couvert cela, alors je voulais juste le mentionner. Vous ne pouvez généralement pas corréler les années d'exécution à une notation big-O. 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 pourrais changer l' TwentyYearsFromNowannée 20110, 75699436 ou 123456789 et le big-O est toujours O (n).

L'analyse Big-O traite de la quantité de traitement impliquée lorsque la quantité de données traitées augmente sans limite.

Ici, vous n'avez vraiment affaire qu'à un seul objet de taille fixe. En tant que tel, l'application de l'analyse big-O dépend fortement (principalement?) De la façon dont vous définissez vos termes.

Par exemple, vous pourriez vouloir dire l'impression de la sortie en général et imposer une attente si longue que toute quantité raisonnable de données serait / sera imprimée exactement dans la même période de temps. Vous devez également ajouter un peu plus de définitions quelque peu inhabituelles (sinon carrément fausses) pour aller très loin - en particulier, l'analyse big-O est généralement définie en termes du nombre d'opérations fondamentales nécessaires pour effectuer un tâche particulière (mais notez que la complexité peut également être considérée en termes de choses comme l'utilisation de la mémoire, pas seulement l'utilisation du processeur / les opérations effectuées).

Le nombre d'opérations fondamentales se traduit généralement assez étroitement par le temps nécessaire, ce n'est donc pas un énorme problème de traiter les deux comme synonymes. Malheureusement, cependant, nous sommes toujours coincés avec cette autre partie: la quantité de données traitées augmente sans limite. Cela étant, aucun délai fixe que vous pouvez imposer ne fonctionnera vraiment. Pour assimiler O (1) à O (N), vous devez imposer un délai infini afin que toute quantité fixe de données prenne une éternité à s'imprimer, tout comme le ferait une quantité infinie de données.

big-O par rapport à quoi?

Vous semblez comprendre que twentyYearsLaterc'est une «entrée». Si en effet vous avez écrit votre fonction comme

void helloWorld(int years) {
   // ...
}

Ce serait O (N) où N = années (ou dites simplement O(years) ).

Je dirais que votre algorithme est O (N) par rapport au nombre que vous écrivez dans la ligne de code commençant par twentyYearsLater =. Mais les gens ne considèrent généralement pas les nombres dans le code source réel comme entrée. Ils peuvent considérer l'entrée de ligne de commande comme entrée, ou l'entrée de signature de fonction comme entrée, mais très probablement pas le code source lui-même. C'est ce que vous contestez avec votre ami - est-ce «l'entrée»? Vous configurez votre code de manière à le faire apparaître intuitivement comme une entrée, et vous pouvez certainement demander son grand temps d'exécution O par rapport au nombre N sur la ligne 6 de votre programme, mais si vous utilisez un tel choix non par défaut comme entrée, vous devez vraiment être explicite à ce sujet.

Mais si vous considérez l'entrée comme quelque chose de plus habituel, comme la ligne de commande ou l'entrée de la fonction, il n'y a pas de sortie du tout et la fonction est O (1). Cela prend vingt ans, mais comme big-O ne change pas jusqu'à un multiple constant, O (1) = O (vingt ans).

Question similaire - quel est le temps d'exécution de:

void sortArrayOfSizeTenMillion(int[] array)

En supposant qu'il fait ce qu'il dit et que l'entrée est valide, et que l'algorithme exploite un tri rapide ou un tri à bulles ou tout ce qui est raisonnable, c'est O (1).

Cet "algorithme" est correctement décrit comme O (1) ou temps constant. On a fait valoir qu'il n'y a pas d'entrée dans ce programme, donc il n'y a pas de N à analyser en termes de Big Oh. Je ne suis pas d'accord pour dire qu'il n'y a pas d'entrée. Lorsqu'il est compilé dans un exécutable et appelé, l'utilisateur peut spécifier n'importe quelle entrée de longueur arbitraire. Cette longueur d'entrée est le N.

Le programme ignore simplement l'entrée (quelle que soit sa longueur), donc le temps pris (ou le nombre d'instructions machine exécutées) est le même quelle que soit la longueur de l'entrée (environnement fixe donné = heure de début + matériel), d'où O (1 ).

Une chose qui m'étonne n'a pas encore été mentionnée: la notation big-O est une borne supérieure!

Le problème que tout le monde a remarqué est qu'il n'y a pas de N décrivant les entrées de l'algorithme, il n'y a donc rien avec quoi faire une analyse big-O. Cependant, ceci est facilement atténué avec quelques astuces de base, telles que l'acceptation int net l'impression des nheures "Hello World" . Cela permettrait de contourner cette plainte et de revenir à la vraie question de savoir comment fonctionne cette DateTimemonstruosité.

Il n'y a aucune garantie réelle que la boucle while se terminera un jour. Nous aimons penser que cela doit à un moment donné, mais considérons que cela DateTime.nowrenvoie la date et l'heure du système . Il n'y a en fait aucune garantie que cela augmente de manière monotone. Il est possible qu'un singe entraîné pathologiquement change constamment la date et l'heure du système au 21 octobre 2015 à 12:00:00 UTC jusqu'à ce que quelqu'un donne au singe des chaussures à ajustement automatique et un hoverboard. Cette boucle peut en fait fonctionner pendant une durée infinie!

Quand vous creusez réellement dans la définition mathématique des notations big-O, ce sont des bornes supérieures. Ils démontrent le pire des cas, aussi improbable soit-il. Le pire des cas * ici est un runtime infini, nous sommes donc obligés de déclarer qu'il n'y a pas de notation big-O pour décrire la complexité d'exécution de cet algorithme. Il n'existe pas, tout comme 1/0 n'existe pas.

* Edit: d'après ma discussion avec KT, il n'est pas toujours valable de supposer que le scénario que nous modélisons avec la notation big-O est le pire des cas. Dans la plupart des cas, si un individu ne spécifie pas le cas que nous utilisons, il a l'intention d'explorer le pire des cas. Cependant, vous pouvez effectuer une analyse de complexité big-O sur le meilleur scénario d'exécution.

La complexité est utilisée pour mesurer la «puissance» de calcul en termes de temps / espace. La notation Big O est utilisée pour comparer quels problèmes sont "calculables" ou "non calculables" et aussi pour comparer quelles solutions -algorithmes- sont meilleures que d'autres. En tant que tel, vous pouvez diviser n'importe quel algorithme en deux catégories: ceux qui peuvent être résolus en temps polynomial et ceux qui ne le peuvent pas.

Des problèmes comme le tamis d'Erathostène sont O (n ^ exp) et sont donc résolubles pour de petites valeurs de n. Ils sont calculables, mais pas en temps polynomial (NP) et donc lorsqu'on leur demande si un nombre donné est premier ou non, la réponse dépend de la grandeur de ce nombre. De plus, la complexité ne dépend pas du matériel, donc avoir des ordinateurs plus rapides ne change rien ...

Hello World n'est pas un algorithme et, en tant que tel, il 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, déterminez s'il est pair ou impair. Maintenant, est-il important que le nombre donné ait 500 chiffres? Non, car il suffit de vérifier si le dernier chiffre est pair ou impair. Un algorithme plus complexe consisterait à déterminer si un nombre donné se divise uniformément par 3. Bien que certains nombres soient "faciles" à calculer, d'autres sont "difficiles" et c'est à cause de leur ampleur: comparez le temps qu'il faut pour déterminer le rappel entre un nombre à un chiffre et un autre à 500 chiffres.

Un cas plus complexe serait de décoder un texte. Vous avez un tableau aléatoire apparent de symboles dont vous savez également qu'ils transmettent un message à ceux qui ont la clé de déchiffrement. Disons que l'expéditeur a utilisé la clé à gauche et que votre Hello World lirait: Gwkki Qieks. La solution "big-hammer, no-brain" produirait toutes les combinaisons pour ces lettres: de Aaaa à Zzzz, puis rechercherait un dictionnaire de mots pour identifier les mots valides et partager les deux lettres communes du chiffrement (i, k) dans la même position. Cette fonction de transformation est ce que Big O mesure!

La plupart des gens semblent manquer deux choses très importantes.

1. Le programme fait avoir une entrée. Il s'agit de la date / heure codée en dur par rapport à laquelle l'heure du système est comparée. Les entrées sont sous le contrôle de la personne exécutant l'algorithme, et l'heure système ne l'est pas. La seule chose que la personne exécutant ce programme peut contrôler est la date / heure à laquelle elle a été codée en dur dans la comparaison.

2. Le programme varie en fonction de la valeur d' entrée , mais pas de la taille de l' ensemble d' entrée , ce qui concerne la notation big-O.

Par conséquent, il est indéterminé, et la meilleure notation «big-O» pour ce programme serait probablement O (null), ou éventuellement O (NaN).

Tout le monde a fait remarquer à juste titre que vous ne définissez pas N , mais la réponse est non selon l'interprétation la plus raisonnable. Si N est la longueur de la chaîne que nous imprimons et "bonjour, monde!" est juste un exemple, comme nous pourrions le déduire de la description de ceci comme un algorithme «pour hello, world!», alors l'algorithme est O ( N ), parce que vous pourriez avoir une chaîne de sortie qui prend trente, quarante ou cinquante ans à imprimer, et vous ajouter seulement un temps constant à cela. O ( kN + c ) ∈ O ( N ).

Addenda:

À ma grande surprise, quelqu'un conteste cela. Rappelez-vous les définitions du grand O et du grand Θ. Supposons que nous ayons un algorithme qui attend pendant une durée constante c puis imprime un message de longueur N en temps linéaire. (Ceci est une généralisation de l'exemple de code original.) Disons arbitrairement que nous attendons vingt ans pour commencer à imprimer, et que l'impression d'un billion de caractères prend encore vingt ans. Soit c = 20 et k = 10¹², par exemple, mais tout nombre réel positif fera l'affaire. C'est un taux de d = c / k (dans ce cas 2 × 10⁻¹¹) ans par caractère, donc notre temps d'exécution f ( N ) est asymptotiquementdN + cannées. Chaque fois que N > k , dN = c / k N > c . Par conséquent, dN < dN + c = f ( N ) <2 dN pour tout N > k , et f ( N ) ∈ Θ ( N ). QED

Je pense que les gens sont rejetés parce que le code ne ressemble pas à un algorithme traditionnel. Voici une traduction du code qui est plus bien formée, mais qui reste fidèle à l'esprit de la question d'OP.

void TrolloWorld(long currentUnixTime, long loopsPerMs){
    long laterUnixTime = 2051222400000;  //unix time of 01/01/2035, 00:00:00
    long numLoops = (laterUnixTime-currentUnixTime)*loopsPerMs;

    for (long i=0; i<numLoops; i++){
        print ("It's still not time to print the hello …");
    }
    print("Hello, World!");
}

Les entrées sont explicites alors qu'avant elles étaient implicitement données par le moment où le code a été lancé et par la vitesse du matériel exécutant le code. Le code est déterministe et a une sortie bien définie pour des entrées données.

En raison des limitations imposées aux entrées que nous pouvons fournir, il existe une limite supérieure au nombre d'opérations qui seront exécutées, donc cet algorithme est en fait O (1).

À ce stade, oui

Cet algorithme a une entrée implicite, à savoir l'heure à laquelle le programme est démarré. Le temps d'exécution variera linéairement ¹ selon le moment où il est démarré. Au cours de l'année 2035 et après, la boucle while se termine immédiatement et le programme se termine après des opérations constantes ² . On pourrait donc dire que le runtime est O(max(2035 - start year, 1))³ . Mais puisque notre année de début a une valeur minimale, l'algorithme ne prendra jamais plus de 20 ans pour s'exécuter (c'est-à-dire une valeur constante).

Vous pouvez rendre votre algorithme plus conforme à votre intention en définissant DateTime TwentyYearsLater = DateTime.Now + new TimeSpan(365*20,0,0,0);⁴

¹ Cela vaut pour le sens plus technique du temps d'exécution mesuré en nombre d'opérations car il y a un nombre maximum d'opérations par unité de temps.
² En supposant que la récupération DateTime.Nowest une opération constante, ce qui est raisonnable.
³ J'abuse un peu de la grosse notation O ici parce que c'est une fonction décroissante par rapport à start year, mais nous pourrions facilement rectifier cela en l'exprimant en termes de years prior to 2035.
⁴ L'algorithme ne dépend plus de l'entrée implicite du temps de démarrage, mais c'est sans conséquence.

Je dirais que c'est O (n). en utilisant http://www.cforcoding.com/2009/07/plain-english-explanation-of-big-o.html comme référence.

Qu'est-ce que Big O?

La notation Big O cherche à décrire la complexité relative d'un algorithme en réduisant le taux de croissance aux facteurs clés lorsque le facteur clé tend vers l'infini.

et

Le meilleur exemple de Big-O auquel je puisse penser est celui de l'arithmétique. Les opérations arithmétiques de base que nous avons apprises à l'école étaient:

une addition; soustraction; multiplication; et la division. Chacun de ces éléments est une opération ou un problème. Une méthode pour résoudre ces problèmes est appelée un algorithme.

Pour votre exemple,

étant donné l'entrée de n = 20 (avec unités années).

l'algorithme est une fonction mathématique f (). où f () attend pendant n ans, avec des chaînes de «débogage» entre les deux. Le facteur d'échelle est 1. f () peut être réduit / ou augmenté en modifiant ce facteur d'échelle.

dans ce cas, la sortie est également 20 (la modification de l'entrée change la sortie de manière linéaire).

essentiellement la fonction est

f(n) = n*1 = n
    if  n = 20, then 
f(20) = 20