Czy zostanie to sklasyfikowane jako algorytm O (1) dla „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!");
   }
}

Myślę o użyciu

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

fragment kodu jako zajętą ​​pętlę, którą można wstawić jako żart, gdy ktoś prosi o algorytm o określonej złożoności. Czy to byłoby poprawne?

Notacja Big O w tym kontekście jest używana do opisania związku między rozmiarem wejścia funkcji a liczbą operacji, które należy wykonać, aby obliczyć wynik dla tego wejścia.

Twoja operacja nie ma danych wejściowych, z którymi można by powiązać dane wyjściowe, więc używanie notacji Big O jest bezsensowne. Czas potrzebny na operację jest niezależny od danych wejściowych operacji (czyli ... brak). Ponieważ nie ma żadnego związku pomiędzy wejściem i liczby wykonywanych operacji, nie można wykorzystać Big O, aby opisać tę nieistniejącą relację

Notacja Big-O oznacza z grubsza „biorąc pod uwagę ilość pracy, N, ile czasu obliczeń, proporcjonalnie do N, zajmuje algorytm?”. Np. Sortowanie tablicy o rozmiarze N może zająć N ^ 2, Nlog (N) itp.

To nie ma ilości danych wejściowych do działania. Więc tak nie jest O(anything).

Nawet gorzej; to nie jest technicznie algorytm. Algorytm to metoda obliczania wartości funkcji matematycznej - funkcje matematyczne to odwzorowanie jednego wejścia na wyjście. Ponieważ nie wymaga to żadnych danych wejściowych i nic nie zwraca, nie jest to funkcja w sensie matematycznym. Z Wikipedii:

Algorytm jest skuteczną metodą obliczania funkcji, którą można wyrazić w określonej przestrzeni i czasie oraz w dobrze zdefiniowanym języku formalnym. Rozpoczynając od stanu początkowego i początkowego wejścia (być może pustego), instrukcje opisują obliczenia, które po wykonaniu przechodzą przez skończoną liczbę dobrze zdefiniowanych kolejnych stanów, ostatecznie wytwarzając „wyjście” i kończąc na końcowym stanie końcowym.

Technicznie rzecz biorąc, jest to system kontroli. Z Wikipedii;

System sterowania to urządzenie lub zestaw urządzeń, które zarządzają, sterują, kierują lub regulują zachowanie innych urządzeń lub systemów.

Osoby, które chcą bardziej dogłębnej odpowiedzi na temat różnicy między funkcjami matematycznymi i algorytmami oraz potężniejszych zdolności komputerów do wykonywania działań ubocznych, takich jak wyjście konsoli, wyświetlanie grafiki lub sterowanie robotami, mogą przeczytać ten artykuł na temat Silna hipoteza Kościoła Turinga

Abstrakcyjny

Klasyczny pogląd na obliczanie obliczania pozycji jako transformację zamkniętych danych wejściowych (liczb wymiernych lub skończonych łańcuchów) na wyniki. Zgodnie z interaktywnym poglądem na obliczenia, obliczenia są ciągłym procesem interaktywnym, a nie opartą na funkcjach transformacją danych wejściowych do wyjściowych. W szczególności komunikacja ze światem zewnętrznym ma miejsce podczas obliczeń, a nie przed nimi ani po nich. Takie podejście radykalnie zmienia nasze rozumienie tego, czym są obliczenia i jak je modeluje.

Akceptacja interakcji jako nowego paradygmatu jest utrudniona przez Mocną Tezę Kościoła Turinga (SCT), powszechne przekonanie, że Maszyny Turinga (TM) przechwytują wszystkie obliczenia, więc modele obliczeń bardziej wyraziste niż TM są niemożliwe. W tym artykule pokazujemy, że SCT reinterpretuje oryginalną tezę Church-Turinga (CTT) w sposób, jakiego Turing nigdy nie zamierzał; jego powszechnie przyjęta równoważność z oryginałem jest mitem. Identyfikujemy i analizujemy historyczne przyczyny powszechnej wiary w SCT. Tylko przyjmując, że jest fałszywa, możemy zacząć przyjmować interakcję jako alternatywny paradygmat obliczeń

Nie, Twój kod ma złożoność czasową O(2^|<DeltaTime>|),

Do prawidłowego zakodowania aktualnego czasu.
Proszę, pozwól mi najpierw przeprosić za mój angielski.

Co to jest i jak działa Big O w CS

Notacja Big O nie jest używana do powiązania wejścia programu z jego czasem wykonywania .
Notacja Big O jest sposobem na wyrażenie asymptotycznego stosunku dwóch wielkości , pozostawiając za sobą rygor .

W przypadku analizy algorytmu te dwie wielkości nie są danymi wejściowymi (dla których trzeba najpierw mieć funkcję „miary”) i czasem działania.
Są to długość kodowania wystąpienia problemu ¹ i miara będąca przedmiotem zainteresowania.

Powszechnie używane metryki to

1. Liczba kroków potrzebnych do wykonania algorytmu w danym modelu obliczeń.
2. Przestrzeń wymagana przez model obliczeń, jeśli taka koncepcja istnieje.

Domyślnie zakłada się TM jako modelu, tak, że pierwszy punkt przekłada się na szeregu zastosowań przejście ² funkcję , czyli „działania”, a drugi przekłada liczby różnych komórek Taśma zapisana co najmniej raz .

Czy często zakłada się niejawnie, że zamiast oryginalnego możemy użyć kodowania wielomianowego, na przykład funkcja przeszukująca tablicę od początku do końca ma O(n)złożoność, mimo że kodowanie instancji takiej tablicy powinno mieć długość n*b+(n-1)gdzie bjest (stałą) liczbą symboli każdego elementu. Dzieje się tak, ponieważ bjest uważana za stałą modelu obliczeniowego, a więc wyrażenie powyżej i njest asymptotycznie takie same.

Wyjaśnia to również, dlaczego algorytm taki jak podział prób jest algorytmem wykładniczym , mimo że zasadniczo jest for(i=2; i<=sqr(N); i++)podobnym algorytmem ³ .

Zobacz to .

Oznacza to również, że notacja dużego O może używać tylu parametrów, które mogą być potrzebne do opisania problemu, czy nie jest niczym niezwykłym posiadanie parametru k dla niektórych algorytmów.

Więc to nie jest o „wejściu” lub, że „nie ma sygnału”.

Studium przypadku teraz

Notacja Big O nie kwestionuje twojego algorytmu, po prostu zakłada, że ​​wiesz, co robisz. Zasadniczo jest to narzędzie stosowane wszędzie, nawet w przypadku algorytmu, który może być celowo podstępny (jak twój).

Aby rozwiązać problem, użyłeś daty bieżącej i przyszłej, więc muszą one w jakiś sposób być częścią problemu; po prostu: są częścią przypadku problemu.

Konkretnie chodzi o:

<DeltaTime>

Gdzie <>oznacza jakiekolwiek, niepatologiczne, kodowanie z wyboru.

Poniżej znajdują się bardzo ważne wyjaśnienia.

Więc twój wielki czas złożoności O jest po prostu O(2^|<DeltaTime>|), ponieważ wykonujesz pewną liczbę iteracji, która zależy od wartości bieżącego czasu. Nie ma sensu wprowadzać innych stałych numerycznych, ponieważ notacja asymptotyczna jest przydatna, ponieważ eliminuje stałe (więc na przykład użycie O(10^|<DeltaTime>|*any_time_unit)jest bezcelowe).

Gdzie jest trudna część

Zrobiliśmy jedno ważne założenie powyżej: model obliczeń reifikuje ⁵ razy, a przez czas mam na myśli (rzeczywisty?) Czas fizyczny. W standardowym modelu obliczeniowym nie ma takiej koncepcji, TM nie zna czasu, łączymy czas z liczbą kroków, ponieważ tak działa nasza rzeczywistość ⁴ .

Jednak w twoim modelu czas jest częścią obliczeń, możesz użyć terminologii ludzi funkcjonalnych, mówiąc, że Main nie jest czysty, ale koncepcja jest taka sama.

Aby to zrozumieć, należy zauważyć, że nic nie stoi na przeszkodzie, aby Framework używał fałszywego czasu, który działa dwa, pięć, dziesięć razy szybciej niż czas fizyczny. W ten sposób Twój kod będzie działał w „połowie”, „jednej piątej”, „jednej dziesiątej” „czasu”.

Ta refleksja jest ważna przy wyborze kodowania <DeltaTime>, jest to zasadniczo skondensowany sposób pisania <(CurrentTime, TimeInFuture)>. Ponieważ czas nie istnieje w klasztorze, kodowanie CurrentTime mogłoby bardzo dobrze oznaczać słowo Teraz (lub jakikolwiek inny wybór), które dzień wcześniej można zakodować jako Wczoraj , łamiąc założenie, że długość kodowania rośnie wraz z czasem fizycznym idzie do przodu (a DeltaTime maleje)

Musimy odpowiednio modelować czas w naszym modelu obliczeniowym, aby zrobić coś pożytecznego.

Jedynym bezpiecznym wyborem, jaki możemy zrobić, jest kodowanie znaczników czasu o rosnących długościach (ale nadal bez użycia jednoargumentowego), gdy czas fizyczny posuwa się naprzód. To jedyna prawdziwa właściwość czasu, którego potrzebujemy, i ta, którą musi wychwycić kodowanie. Czy tylko przy takim typie kodowania algorytm może mieć złożoność czasową.

Twój błąd, jeśli w ogóle, wynikają z faktu, że słowo czas w oznaczeniach "Jaka jest jego czas złożoność? i „Ile czasu to zajmie?” oznacza bardzo różne rzeczy

Niestety terminologia używa tych samych słów, ale możesz spróbować użyć w swojej głowie „złożoności kroków” i ponownie zadać sobie pytanie, mam nadzieję, że pomoże Ci to zrozumieć, że odpowiedź naprawdę brzmi ^ _ ^

¹ Wyjaśnia to również potrzebę podejścia asymptotycznego, ponieważ każdy przypadek ma inną, ale nie arbitralną długość.
² Mam nadzieję, że używam tutaj prawidłowego angielskiego terminu.
³ Również dlatego często log(log(n))w matematyce znajdujemy terminy.
^{4 To} znaczy, krok musi zajmować jakiś ograniczony, ale nie zerowy, ani niepołączony, przedział czasu.
⁵ Oznacza to, że tryb obliczeniowy jako znajomość czasu fizycznego w nim jest, to znaczy można go wyrazić swoimi terminami. Analogią jest sposób działania typów ogólnych w środowisku .NET.

Chociaż jest tutaj wiele świetnych odpowiedzi, pozwolę sobie trochę je przeformułować.

Do opisu funkcji istnieje notacja Big-O . W przypadku zastosowania do analizy algorytmów wymaga to najpierw zdefiniowania pewnych cech tego algorytmu w kategoriach funkcji . Powszechnym wyborem jest rozważenie liczby kroków jako funkcji rozmiaru danych wejściowych . Jak zauważono w innych odpowiedziach, wymyślenie takiej funkcji w twoim przypadku wydaje się dziwne, ponieważ nie ma jasno zdefiniowanego „wejścia”. Nadal możemy spróbować to zrobić:

• Możemy traktować twój algorytm jako stałą funkcję, która przyjmuje dane wejściowe dowolnego rozmiaru, ignoruje je, czeka przez określony czas i kończy pracę. W tym przypadku jego czas wykonania to f (n) = const i jest to algorytm czasu O (1). To właśnie spodziewałeś się usłyszeć, prawda? Tak, technicznie rzecz biorąc, jest to algorytm O (1) .
• Możemy traktować ten parametr TwentyYearsLaterjako parametr podobny do „wielkości wejściowej”. W tym przypadku środowisko wykonawcze to f (n) = (nx), gdzie x to „czas teraz” w momencie wywołania. Patrząc w ten sposób, jest to algorytm czasu O (n). Spodziewaj się tego kontrargumentu, ilekroć chcesz pokazać innym technicznie swój algorytm O (1) .
• Och, ale poczekaj, jeśli k =TwentyYearsLater jest wejściem, to jego rozmiar n jest w rzeczywistości liczbą bitów potrzebnych do jego przedstawienia, tj. N = log (k) . Zależność między rozmiarem wejścia n a czasem działania wynosi zatem f (n) = 2 ^ n - x . Wygląda na to, że twój algorytm stał się wykładniczo wolny! Fuj.
• Innym wejściem do programu jest w rzeczywistości strumień odpowiedzi udzielonych przez system operacyjny na sekwencję DateTime.Nowwywołań w pętli. Możemy sobie wyobrazić, że cała ta sekwencja jest podawana jako dane wejściowe w momencie uruchamiania programu. Można wtedy uznać, że środowisko wykonawcze zależy od właściwości tej sekwencji - mianowicie od jej długości do pierwszego TwentyYearsLaterelementu. W tym przypadku czas wykonania ponownie wynosi f (n) = n, a algorytm to O (n) .

Ale z drugiej strony, w swoim pytaniu nie powiedziałeś nawet, że interesuje Cię środowisko wykonawcze. A co by było, gdybyś miał na myśli użycie pamięci? W zależności od tego, jak modelujesz sytuację, możesz powiedzieć, że algorytmem jest O (1) -pamięć lub, być może, O (n) -pamięć (jeśli implementacja DateTime.Nowwymaga pewnego śledzenia całej sekwencji wywołań).

A jeśli Twoim celem było wymyślenie czegoś absurdalnego, dlaczego nie pójdziesz na całość i nie powiesz, że interesuje Cię to, jak rozmiar kodu algorytmu w pikselach na ekranie zależy od wybranego poziomu powiększenia. Może to być coś w rodzaju f (zoom) = 1 / zoom i możesz z dumą zadeklarować, że twój algorytm ma rozmiar piksela O (1 / n) !

Muszę się trochę nie zgodzić z Servy. Program zawiera dane wejściowe, nawet jeśli nie jest to oczywiste, i to jest czas systemu. Może to być kwestia techniczna, której nie zamierzałeś, ale twoja TwentyYearsFromNowzmienna nie jest teraz dwadzieścia lat od czasu systemu , jest statycznie przypisana do 1 stycznia 2035 r.

Więc jeśli weźmiesz ten kod i wykonasz go na maszynie, która ma czas systemowy 1 stycznia 1970 roku, ukończenie tego zajmie 65 lat, niezależnie od szybkości komputera (mogą wystąpić pewne różnice, jeśli jego zegar jest uszkodzony ). Jeśli weźmiesz ten kod i wykonasz go na maszynie, która ma czas systemowy 2 stycznia 2035 r., Zakończy się prawie natychmiast.

Powiedziałbym, że twój wkład njest January 1st, 2035 - DateTime.Nowi to jest O (n).

Następnie pojawia się kwestia liczby operacji. Niektórzy zauważyli, że szybsze komputery szybciej uderzą w pętlę, powodując więcej operacji, ale to nie ma znaczenia. Podczas pracy z notacją duże-O nie bierzemy pod uwagę szybkości procesora ani dokładnej liczby operacji. Gdybyś wziął ten algorytm i uruchomił go na komputerze, a następnie uruchomił go ponownie, ale 10 razy dłużej na tym samym komputerze, można by oczekiwać, że liczba operacji wzrośnie o ten sam współczynnik 10x.

A co do tego:

Myślę o użyciu fragmentu [zredagowanego kodu] kodu jako zajętej pętli do umieszczenia jako żart, gdy ktoś poprosi o algorytm o określonej złożoności. Czy to byłoby poprawne?

Nie, nie bardzo. Inne odpowiedzi obejmowały to, więc chciałem tylko o tym wspomnieć. Zasadniczo nie można skorelować lat wykonania z jakąkolwiek notacją duże-O. Na przykład. Nie można powiedzieć, że 20 lat egzekucji = O (n ^ 87) lub cokolwiek innego w tej sprawie. Nawet w algorytmie, który podałeś, mógłbym zmienić TwentyYearsFromNowrok na 20110, 75699436 lub 123456789, a duże-O to nadal O (n).

Analiza Big-O obejmuje ilość przetwarzania, ponieważ ilość przetwarzanych danych rośnie bez ograniczeń.

Tutaj tak naprawdę masz do czynienia tylko z jednym obiektem o ustalonym rozmiarze. W związku z tym zastosowanie analizy big-O zależy w dużym stopniu (przede wszystkim?) Od tego, jak definiujesz swoje terminy.

Na przykład, możesz ogólnie mieć na myśli drukowanie wyników i narzucanie tak długiego oczekiwania, aby każda rozsądna ilość danych została / zostanie wydrukowana dokładnie w tym samym okresie. Musisz także dodać trochę więcej w ramach nieco nietypowych (jeśli nie całkowicie błędnych) definicji, aby zajść bardzo daleko - w szczególności analiza dużych-O jest zwykle definiowana w kategoriach liczby podstawowych operacji potrzebnych do przeprowadzenia konkretne zadanie (ale pamiętaj, że złożoność można również rozpatrywać w kategoriach takich rzeczy, jak użycie pamięci, a nie tylko użycie procesora / przeprowadzone operacje).

Liczba podstawowych operacji zwykle przekłada się dość ściśle na czas, który zajmuje, więc nie jest to duże rozciąganie, traktując te dwie jako synonimy. Niestety, wciąż tkwimy w tym drugim aspekcie: ilość przetwarzanych danych rośnie bez ograniczeń. W takim przypadku żadne ustalone opóźnienie, które możesz narzucić, nie zadziała. Aby zrównać O (1) z O (N), musiałbyś narzucić nieskończone opóźnienie, tak aby wydrukowanie dowolnej ustalonej ilości danych trwało wiecznie, tak jak zrobiłaby to nieskończona ilość danych.

big-O w stosunku do czego?

Wydajesz się intuicyjny, że twentyYearsLaterjest to „wejście”. Jeśli rzeczywiście napisałeś swoją funkcję jako

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

Byłoby to O (N), gdzie N = lata (lub po prostu powiedz O(years)).

Powiedziałbym, że twój algorytm to O (N) w stosunku do dowolnej liczby, którą napiszesz w linii kodu zaczynającej się od twentyYearsLater =. Ale ludzie zwykle nie biorą pod uwagę liczb w rzeczywistym kodzie źródłowym jako danych wejściowych. Mogą uznać dane wejściowe wiersza poleceń za dane wejściowe lub dane wejściowe sygnatury funkcji jako dane wejściowe, ale najprawdopodobniej nie sam kod źródłowy. Właśnie o to spierasz się ze swoim przyjacielem - czy to jest „wkład”? Skonfigurowałeś swój kod w taki sposób, aby intuicyjnie wyglądał jak dane wejściowe i zdecydowanie możesz zapytać o jego duże O w odniesieniu do liczby N w linii 6 twojego programu, ale jeśli użyjesz takiego innego niż domyślnego wyboru jako wejście naprawdę musisz wyraźnie o tym powiedzieć.

Ale jeśli uznasz, że dane wejściowe są czymś bardziej zwyczajnym, jak wiersz poleceń lub dane wejściowe funkcji, w ogóle nie ma wyjścia, a funkcją jest O (1). Trwa to dwadzieścia lat, ale ponieważ duże-O nie zmienia się aż do stałej wielokrotności, O (1) = O (dwadzieścia lat).

Podobne pytanie - jaki jest czas działania:

void sortArrayOfSizeTenMillion(int[] array)

Zakładając, że robi to, co mówi, a dane wejściowe są prawidłowe, a algorytm wykorzystuje szybkie sortowanie lub sortowanie bąbelkowe lub cokolwiek rozsądnego, to O (1).

Ten „algorytm” jest poprawnie opisany jako O (1) lub stały czas. Argumentowano, że nie ma danych wejściowych do tego programu, stąd nie ma N do analizy w kategoriach Wielkiego Oh. Nie zgadzam się, że nie ma żadnego wkładu. Gdy jest to kompilowane do pliku wykonywalnego i wywoływane, użytkownik może określić dowolne dane wejściowe o dowolnej długości. Ta długość wejściowa to N.

Program po prostu ignoruje dane wejściowe (o dowolnej długości), więc czas potrzebny (lub liczba wykonanych instrukcji maszynowych) jest taki sam niezależnie od długości wejścia (dane środowisko = czas rozpoczęcia + sprzęt), stąd O (1 ).

Jedna rzecz, którą jestem zaskoczony, nie została jeszcze wspomniana: notacja duże-O jest górną granicą!

Problem, który wszyscy zauważyli, polega na tym, że nie ma N opisującego dane wejściowe do algorytmu, więc nie ma z czym robić analizy big-O. Można to jednak łatwo złagodzić za pomocą pewnych podstawowych sztuczek, takich jak zaakceptowanie int ni wydrukowanie nczasów „Hello World” . To pozwoliłoby obejść tę skargę i wrócić do prawdziwego pytania, jak DateTimedziała ta potworność.

Nie ma rzeczywistej gwarancji, że pętla while kiedykolwiek się zakończy. Lubimy myśleć, że musi na jakiś czas, ale uważają, że DateTime.nowzwraca datę i czas systemowy . Właściwie nie ma gwarancji, że będzie się to monotonicznie rosło. Jest możliwe, że jakaś patologicznie wyszkolona małpa nieustannie zmienia systemową datę i godzinę z powrotem na 21 października 2015 r. 12:00:00 UTC, dopóki ktoś nie da małpie automatycznie dopasowanych butów i deskolotki. Ta pętla może faktycznie działać przez nieskończoną ilość czasu!

Kiedy faktycznie zagłębisz się w matematyczną definicję notacji duże-O, są to górne granice. Przedstawiają najgorszy scenariusz, nieważne jak mało prawdopodobny. Najgorszy scenariusz * w tym przypadku to nieskończone środowisko wykonawcze, więc jesteśmy zmuszeni zadeklarować, że nie ma notacji duże-O opisującej złożoność tego algorytmu w czasie wykonywania. Nie istnieje, tak jak nie istnieje 1/0.

* Edytuj: z mojej dyskusji z KT nie zawsze można zakładać, że scenariusz, który modelujemy za pomocą notacji duże-O, jest najgorszym przypadkiem. W większości przypadków, jeśli dana osoba nie określi, którego przypadku używamy, zamierzała zbadać najgorszy przypadek. Możesz jednak przeprowadzić analizę złożoności typu big-O w najbardziej optymalnym czasie wykonywania.

Złożoność jest używana do pomiaru mocy obliczeniowej w kategoriach czasu / przestrzeni. Notacja Big O jest używana do porównania, które problemy są „obliczalne” lub „nieobliczalne”, a także do porównania, które rozwiązania - algorytmy - są lepsze od innych. W związku z tym każdy algorytm można podzielić na dwie kategorie: te, które można rozwiązać w czasie wielomianowym i te, których nie można rozwiązać.

Problemy takie jak Sito Erathostenu są O (n ^ exp) i dlatego można je rozwiązać dla małych wartości n. Są obliczalne, ale nie w czasie wielomianowym (NP), a zatem na pytanie, czy dana liczba jest pierwsza, czy nie, odpowiedź zależy od wielkości tej liczby. Co więcej, złożoność nie zależy od sprzętu, więc szybsze komputery niczego nie zmieniają ...

Hello World nie jest algorytmem i jako taki nie ma sensu próbować określić jego złożoności - która jest żadną. Prostym algorytmem może być coś takiego: podając liczbę losową, określ, czy jest parzysta, czy nieparzysta. Czy to ma znaczenie, że podana liczba ma 500 cyfr? Nie, ponieważ musisz tylko sprawdzić, czy ostatnia cyfra jest parzysta czy nieparzysta. Bardziej złożonym algorytmem byłoby ustalenie, czy dana liczba dzieli się równo przez 3. Chociaż niektóre liczby są „łatwe” do obliczenia, inne są „trudne”, a dzieje się tak ze względu na ich wielkość: porównaj czas potrzebny do określenia przypomnienia między liczba składająca się z jednej cyfry i druga zawierająca 500 cyfr.

Bardziej złożonym przypadkiem byłoby odkodowanie tekstu. Masz pozornie losową tablicę symboli, o których wiesz, że przekazują wiadomość osobom posiadającym klucz odszyfrowywania. Powiedzmy, że nadawca użył klawisza po lewej stronie, a Twój Hello World powinien przeczytać: Gwkki Qieks. Rozwiązanie typu „duży młotek, bez mózgu” stworzyłoby wszystkie kombinacje tych liter: od Aaaa do Zzzz, a następnie przeszukał słownik słów, aby zidentyfikować, które słowa są prawidłowe i udostępnić dwie wspólne litery w szyfrze (i, k) w w tej samej pozycji. Ta funkcja transformacji jest tym, co mierzy Big O!

Wydaje się, że większości ludzi brakuje dwóch bardzo ważnych rzeczy.

1. Program ma mieć wejście. Jest to zakodowana na stałe data / godzina, z którą porównywany jest czas systemowy. Wejścia są pod kontrolą osoby wykonującej algorytm, a czas systemowy nie. Jedyną rzeczą, którą może kontrolować osoba uruchamiająca ten program, jest data / godzina, którą wpisała na stałe do porównania.

2. Program różni się w zależności od wartości wejściowej , ale nie od rozmiaru zestawu wejściowego , co jest tym, czego dotyczy notacja duże-O.

Dlatego jest nieokreślony, a najlepszym zapisem „duże-O” dla tego programu byłoby prawdopodobnie O (zerowe) lub prawdopodobnie O (NaN).

Wszyscy słusznie zauważyli, że nie definiujesz N , ale odpowiedź brzmi nie w najbardziej rozsądnej interpretacji. Jeśli N jest długością napisu, który drukujemy, i „witaj, świecie!” jest tylko przykładem, jak możemy wywnioskować z opisu tego jako algorytmu „dla hello, world!”, wtedy algorytmem jest O ( N ), ponieważ możesz mieć ciąg wyjściowy, którego wydrukowanie zajmuje trzydzieści, czterdzieści lub pięćdziesiąt lat, a ty dodajemy do tego tylko stały czas. O ( kN + c ) ∈ O ( N ).

Uzupełnienie:

Ku mojemu zdziwieniu ktoś to kwestionuje. Przypomnij sobie definicje dużego O i dużego Θ. Załóżmy, że mamy algorytm, który czeka przez stałą ilość czasu c, a następnie wypisuje wiadomość o długości N w czasie liniowym. (Jest to uogólnienie oryginalnej próbki kodu). Powiedzmy arbitralnie, że czekamy dwadzieścia lat na rozpoczęcie drukowania, a wydrukowanie biliona znaków zajmuje kolejne dwadzieścia lat. Na przykład niech c = 20 i k = 10¹², ale wystarczą wszystkie dodatnie liczby rzeczywiste. To jest współczynnik d = c / k (w tym przypadku 2 × 10⁻¹¹) lat na znak, więc nasz czas wykonania f ( N ) jest asymptotycznydN + c lat. Zawsze, gdy N > k , dN = c / k N > c . Dlatego dN < dN + c = f ( N ) <2 dN dla wszystkich N > k oraz f ( N ) ∈ Θ ( N ). CO BYŁO DO OKAZANIA

Myślę, że ludzie są wyrzucani, ponieważ kod nie wygląda jak tradycyjny algorytm. Oto tłumaczenie kodu, które jest lepiej sformułowane, ale pozostaje wierne duchowi pytania 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!");
}

Dane wejściowe są jawne, podczas gdy wcześniej zostały one niejawnie podane do czasu uruchomienia kodu i szybkości sprzętu, na którym działa kod. Kod jest deterministyczny i ma dobrze zdefiniowane dane wyjściowe dla danych danych wejściowych.

Ze względu na ograniczenia nałożone na dane wejściowe, które możemy dostarczyć, istnieje górna granica liczby operacji, które zostaną wykonane, więc ten algorytm jest w rzeczywistości O (1).

W tej chwili tak

Ten algorytm ma niejawne dane wejściowe, a mianowicie czas uruchomienia programu. Czas wykonania będzie się zmieniać liniowo ^{1 w} zależności od tego, kiedy zostanie uruchomiony. W roku 2035 i później pętla while natychmiast wychodzi, a program kończy się po stałych operacjach ² . Można więc powiedzieć, że czas działania wynosi O(max(2035 - start year, 1))³ . Ale ponieważ nasz rok początkowy ma wartość minimalną, algorytm nigdy nie zajmie więcej niż 20 lat na wykonanie (tj. Wartość stała).

Możesz sprawić, by twój algorytm był bardziej zgodny z twoimi intencjami, definiując DateTime TwentyYearsLater = DateTime.Now + new TimeSpan(365*20,0,0,0);⁴

¹ Dotyczy to bardziej technicznego sensu czasu wykonania mierzonego jako liczba operacji, ponieważ istnieje maksymalna liczba operacji na jednostkę czasu.
² Zakładając, że pobieranie DateTime.Nowjest operacją ciągłą, co jest rozsądne.
³ W pewnym sensie nadużywam tutaj dużej notacji O, ponieważ jest to funkcja malejąca w stosunku do start year, ale możemy to łatwo naprawić, wyrażając to w kategoriach years prior to 2035.
⁴ Wtedy algorytm nie zależy już od niejawnych danych wejściowych czasu rozpoczęcia, ale nie ma to znaczenia.

Twierdzę, że to jest O (n). używając http://www.cforcoding.com/2009/07/plain-english-explanation-of-big-o.html jako odniesienia.

Co to jest Big O?

Notacja Big O ma na celu opisanie względnej złożoności algorytmu poprzez zmniejszenie tempa wzrostu do kluczowych czynników, gdy kluczowy czynnik zmierza w kierunku nieskończoności.

i

Najlepszym przykładem Big-O, jaki przychodzi mi do głowy, jest arytmetyka. Podstawowe operacje arytmetyczne, których nauczyliśmy się w szkole, to:

dodanie; odejmowanie; mnożenie; i podział. Każdy z nich to operacja lub problem. Metodę ich rozwiązania nazywa się algorytmem.

Na przykład

biorąc pod uwagę wkład n = 20 (z jednostkami lat).

algorytm jest funkcją matematyczną f (). gdzie f () tak się składa, że ​​czeka n lat, a pomiędzy nimi znajduje się napis „debug”. Współczynnik skali wynosi 1. f () można zmniejszyć / lub zwiększyć, zmieniając ten współczynnik skali.

w tym przypadku wyjście również wynosi 20 (zmiana wejścia powoduje liniową zmianę wyjścia).

zasadniczo funkcja jest

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