Czy jest to technicznie algorytm O (1) dla „Hello World”?

117

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?

Subpar Web Dev
źródło
15
To nie jest O(N)złożonośćO(1)
Fabjan
19
@SubparWebDev Nie, nie wiesz, ile razy przejdzie pętlę, nawet jeśli znasz dokładną różnicę czasu między uruchomieniem programu a określoną datą. Zależy to od tego, jak szybko działa komputer, co jeszcze na nim działa, jak procesor planuje zadanie itp.
Servy
131
@Fabjan Nie istnieje Nalgorytm, od którego jest zależny, więc nie można powiedzieć, że jest to algorytm O (N).
Servy
29
Technicznie nie ma wejścia, więc Nnawet nie ma sensu. Ale możesz wziąć pod uwagę DateTime.Nowdane wejściowe, które nadal uzależniają to od wyniku. Jeśli możesz przyjąć realistyczną wartość for DateTime.Now, to tak, program zapętla stałą ilość razy.
poke
43
Opis problemu musi określać, czym jest N.
Yacoub Massad

Odpowiedzi:

406

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ę

Servy
źródło
6
O co chodzi O(max(1, 2035 - yearTheProgramIsStarted))?
Bergi
19
@Bergi [Właściwie nie [( stackoverflow.com/questions/34048740/… ), nie możesz po prostu opisać liczby iteracji pętli wyłącznie na podstawie czasu uruchomienia zadania. I oczywiście łączysz to z faktem, że zegar systemowy może zostać zmieniony w dowolnym momencie przez użytkownika na dowolny czas itp., A nadal nie masz dobrze sformułowanych danych wejściowych, które można dokładnie powiązać z wieloma operacje potrzebne do wytworzenia wyniku. Heck, nawet sam wynik nie jest spójny.
Servy
23
Można by argumentować, że stan systemu (w tym zegara) jest częścią danych wejściowych programu. W tym sensie możesz użyć daty jako parametru wejściowego, choć nie jest to jawne. Ale to dziwne.
Connor Clark
9
Aby być bardziej zrozumiałym, „niejawne” dane wejściowe to delta między 1 stycznia 2035 r. A dniem dzisiejszym.
Connor Clark
6
@Hoten Ale czas systemowy nie jest wartością stałą. Ta funkcja to nie to samo, co zwykłe przyjmowanie DateTimejako wejścia czasu rozpoczęcia. Jak powiedziałem wcześniej, zegar systemowy może się zmieniać w czasie . I znowu, nie możesz bezpośrednio odwzorować wejścia quazi, który opisujesz, na ustalone wyjście. Nie ma znanej liczby operacji wykonywanych dla danego czasu rozpoczęcia, ani nawet dla dwóch programów, które zawsze uzyskują sensowną wartość DateTime.Now, więc nie możesz ich powiązać, gdy czas się zmienia, ponieważ nie możesz ich nawet powiązać, gdy czas się nie zmienia.
Servy
88

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ń

Steve Cooper
źródło
Nie musi to być sekwencja. To tylko niektóre dane wejściowe, a notacja landau opisuje czas działania w odniesieniu do niektórych wskaźników tych danych - zazwyczaj jest to coś związanego z rozmiarem.
Bergi
@Bergi - tak, rozumiem! Robię tylko przybliżenie, tak naprawdę, ale tak - jeśli możesz zmierzyć ilość pracy do wykonania i liczbę kroków potrzebnych do osiągnięcia tego celu, big-o odzwierciedla związek tych dwóch miar. Bliższy?
Steve Cooper
@kapep - to nie jest czysta funkcja, ponieważ jest to metoda void, ale jeśli policzymy wyjście konsoli, nadal jest losowa; może wypisać dowolne z {"Hello, World!", "Nadal nie czas drukować hello ... \ nHello, World!", "Nadal nie czas drukować hello ... Nadal nie czas na drukowanie cześć ... \ nHello, świecie! ", ...}
Steve Cooper
1
Drukowanie na standardowe wyjście nie jest wyjściem?
rpax
4
@rpax Nie matematycznie, nie. Funkcja to niezmienne przekształcenie danych wejściowych na wyjściowe; np. „square” to funkcja, która zawsze zwraca 9, jeśli wprowadzisz 3. Metoda c # jest funkcją matematyczną tylko wtedy, gdy wywołanie z tymi samymi parametrami zawsze zwraca tę samą wartość zwracaną. W przeciwnym razie - jeśli ma efekty uboczne, takie jak pisanie do konsoli, wyświetlanie grafiki, alokowanie pamięci - nie są to funkcje matematyczne. (Dodam link do mojej odpowiedzi, który zawiera dręczące szczegóły :))
Steve Cooper,
41

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 1 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 2 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 3 .

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 5 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ść 4 .

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 ^ _ ^


1 Wyjaśnia to również potrzebę podejścia asymptotycznego, ponieważ każdy przypadek ma inną, ale nie arbitralną długość.
2 Mam nadzieję, że używam tutaj prawidłowego angielskiego terminu.
3 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.
5 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.

Yuni Mj
źródło
3
„Więc twój wielki czas wykonania O to tylko” .. Jestem pewien, że miałeś na myśli „dużą złożoność O”? Ponadto, nadal możemy po prostu nazwać „deltaTime” naszym „n”, tak więc powiedzenie O (2 ^ N) przypomina złożoność algorytmu Fibonacciego. Jak doszedłeś do „2 ^”?
Ross
@ Ross, dzięki za punkt. Przyszedłem z 2 przyzwyczajeniem do pracy z liczbami binarnymi. Chodzi o to, że kroki są liniowe z długością reprezentacji liczby. Rzeczywista podstawa nie jest naprawdę ważna i różni się w zależności od konkretnego kodowania. Jest pseudoliniowy .
Yuni Mj
Przykro mi, ale czy mógłbyś szerzej wyjaśnić w swojej odpowiedzi, skąd wywnioskowałeś, że złożoność jest taka O(2^n)? Nie jest to jasne dla początkujących.
Arturo Torres Sánchez
2
@YuniMj Podczas gdy rozumowanie nie jest technicznie źle, myślę, że nalegając, aby zmierzyć rozmiar z DeltaTimezamiast jej wartości , jesteś po prostu dodając dodatkowe zamieszanie. Na przykład, ale to rozumowanie żaden optymalny algorytm sortowania nie ma złożoności czasowej $ O (n \ cdot log n) $. Czemu? Ponieważ możesz sortować tylko skończoną liczbę rozróżnialnych obiektów, w takim przypadku zawsze możesz użyć sortowania kubełkowego do sortowania według $ O (n) $. Lub rozmiar twojego obiektu jest nieograniczony, w takim przypadku $ O (n \ cdot log n) $ nie będzie się utrzymywać, ponieważ pojedyncze porównanie nie będzie już miało stałego czasu ...
fgp
1
FWIW O (2 ^ n)! = O (10 ^ n) stackoverflow.com/questions/19081673/…
Nathan FD
29

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) !

KT.
źródło
+1. Uważam, że "strumień odpowiedzi udzielonych przez system operacyjny na sekwencję DateTime.Nowwywołań" jest prawdziwym wejściem tutaj. Ale myślę, że wniosek nie powinien być taki, że jest to O (n), ale to O (k), gdzie k to długość aż do pierwszego TwentyYearsLaterelementu.
justhalf
7
Jak dotąd jest to najlepsza odpowiedź - aby Wielkie O miało sens, musisz zastosować semantykę / założenia matematyczne do fizycznej implementacji (zasadniczo definiując model matematyczny programu ze znaczącą definicją „wejścia”). W tym sensie złożoność „programu” zależy od zastosowanej semantyki - jeśli przyjmiemy, że N to różnica czasu skalowana liniowo wraz z liczbą operacji, to O (n). Jeśli założysz stałą liczbę operacji w wyniku ustalonego okresu czasu, to jest O (1).
Ant P
21

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).

Shaz
źródło
7
Czas nie jest wejściem do funkcji, jest to stale zmieniający się stan, który jest obserwowany podczas wykonywania metody. Zegar systemowy można zmienić nawet podczas działania funkcji . Aby Big O miało znaczenie, musiałbyś również mieć każde wejście odpowiadające 1-1 z wartością wyjściową, a także pewną liczbą operacji niezbędnych do jej obliczenia. W przypadku tej operacji dane wyjściowe nie są nawet spójne dla tego samego wejścia (w rzeczywistości jest bardzo różne ), oprócz liczby wykonanych operacji również zmienia się dziko.
Servy
When working with big-O notation, we don't consider the speed of the processor or the exact number of operations.To jest fałszywe stwierdzenie. Prawie każda rozsądna operacja, którą spróbujesz obliczyć wartość Big O, nie zmieni liczby operacji wykonywanych na sprzęcie, ale ta jest . Wielkie O to tylko sposób na powiązanie liczby operacji z rozmiarem danych wejściowych. W przypadku większości operacji niezależnych od sprzętu systemowego. W tym przypadku tak nie jest .
Servy
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.To także fałszywe stwierdzenie. Środowisko niekoniecznie zmieni liniowo liczbę operacji w pętli. Mogą na przykład istnieć inne programy na komputerze, które zużywają mniej lub więcej czasu procesora w różnych punktach w czasie, zmieniając czas nadawany tej aplikacji w sposób ciągły w czasie.
Servy
Jestem z @Servy w tej sprawie, ale z nieco innego powodu. Funkcja główna nie przyjmuje parametrów i nie zwraca danych wejściowych. Jest to funkcja nil => nil, jeśli wolisz. Nie ma znaczenia, która jest godzina, nadal nic nie zwraca.
Steve Cooper
1
Jeśli używamy tej definicji - „W matematyce funkcja to relacja między zbiorem danych wejściowych a zbiorem dopuszczalnych wyników z właściwością, że każde wejście jest powiązane z dokładnie jednym wyjściem”. (wikipedia) - i liczymy wynik konsoli jako 'wyjście funkcji', to się zmienia, wydłuża się na szybszym komputerze, ponieważ napisze "" Nadal nie czas na wydrukowanie hello ... "" częściej.
Steve Cooper
13

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.

Jerry Coffin
źródło
10

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).

djechlin
źródło
Zakodowanie wejścia na sztywno nie oznacza, że ​​zniknie. Ani też quicksort i bubbleort złożoności czasowej O (1) w żadnym przypadku. bigocheatsheet.com
Theo Brinkman
@TheoBrinkman Jeśli chcesz być techniczny, w modelu maszyny Turinga, zakodowanie tego, co myślisz o danych wejściowych, do samej maszyny Turinga, sprawia, że ​​z definicji nie jest to dane wejściowe. Maszyna Turinga będzie wtedy działać w stałym czasie, niezależnie od tego, jakie rzeczywiste dane wejściowe ma. W pewnym sensie nie jest to uruchamianie „sortowania bąbelkowego”, ponieważ nie sortuje niczego, ale raczej działa na własnej reprezentacji, jednak w terminach nietechnicznych można oczywiście opisać algorytm jako sortowanie bąbelkowe.
djechlin
Równie „nietechnicznie” można opisać omawiany algorytm jako most wiszący.
Theo Brinkman
@TheoBrinkman nie, nie możesz. Dla nikogo to nie miałoby sensu.
djechlin
Ma to tyle samo sensu, co opisywanie go jako sortowania bąbelkowego O (1).
Theo Brinkman
8

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 ).

waldol1
źródło
Ale liczba operacji nie jest koniecznie spójne, nawet o tej samej godzinie rozpoczęcia i sprzętu. Na dodatek, aby ubiegać się o O (1) algorytm wyjście musiałby być zawsze na stałym poziomie, a tak nie jest, to będzie różnić się dziko na podstawie czasu rozpoczęcia i sprzętu. Może również być nieskończony, co z pewnością nie jest stałe. Nie ma związku między zdefiniowanymi danymi wejściowymi a liczbą wykonanych operacji. To nie jest stałe, to po prostu nieokreślone. Nie możesz nazwać liczby skończonej i wiedzieć, że zawsze będzie mniej operacji niż to.
Servy
Maksymalny czas rzeczywisty to 20 lat. Jeśli zaczniemy to w przyszłości, tak, potrwa to dłużej. Załóżmy, że istnieje skończona dolna granica ilości czasu potrzebnego na iterację pętli i że pracujemy na sprzęcie szeregowym. Następnie mogę ograniczyć liczbę uruchomień pętli, co oznacza, że ​​całe obliczenia mogą być ograniczone przez stałą funkcję, bez względu na rozmiar ignorowanych danych wejściowych.
waldol 1
Let's suppose that there is a finite lower bound on the amount of time a loop iteration takesTo fałszywe założenie. Program może działać wiecznie. Wszystko, co muszę zrobić, to ustawić zegar systemowy na 50 lat od teraz, uruchomić go i nigdy się nie skończy. Albo mógłbym przesunąć zegar do tyłu szybciej niż do przodu lub uruchomić go w nieokreślonym punkcie w przeszłości . Po prostu nie możesz założyć, że istnieje dolna granica czasu działania programu; może trwać wiecznie. Ale nawet jeśli przyjmiemy twoje (fałszywe) założenie jako prawdziwe, nadal nie możesz powiązać liczby wykonanych operacji z danymi wejściowymi.
Servy
Iteracja pojedynczej pętli zajmuje skończoną ilość czasu. Może być możliwe wykonanie nieskończonej liczby razy, ale każdy z nich powinien być mniej więcej stały. Nie widzę problemu z tym założeniem.
waldol 1
W tym zupełnie błędnego] [logiki każdy algorytm każdy jest zawsze O (1), ponieważ każda jednostka operacji jest zawsze stała. Po prostu pokazujesz, że nie wiesz nawet, czym jest Wielkie O. Jest to narzędzie do (w kontekście) opisu zależności między wielkością wejścia a liczbą wykonanych odpowiednich operacji. O (1) oznacza, że ​​niezależnie od danych wejściowych wykonywanych jest stała liczba operacji. Tutaj nie ma stałej liczby operacji wykonywanych niezależnie od danych wejściowych, są wykonywane potencjalnie nieskończone operacje, nieskończone! = Stała.
Servy
6

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.

Cort Ammon
źródło
2
O jest w pewnym sensie „górną granicą”, ale nie oznacza to, że można mówić tylko o „najgorszym przypadku złożoności”, używając notacji O. Oczekiwana złożoność, złożoność najlepszego przypadku, dowolna inna właściwość funkcjonalna - wszystkie z nich można omówić w kategoriach ich granic O.
KT.
@KY złożoność najlepszego przypadku nazywa się little-o, a oczekiwana złożoność to big-theta. big-o jest zawsze najgorszym przypadkiem złożoności, zgodnie z jego matematyczną definicją.
Cort Ammon
Nie, tu się mylisz. Ponownie sprawdź definicje.
KT.
@KT OK, sprawdzę je ponownie. Ty też je sprawdzasz. en.wikipedia.org/wiki/Big_O_notation Jest pod zapisami rodziny Bachmann-Landau
Cort Ammon
Przypuszczam, że mógłbyś zrobić coś szalonego, na przykład wziąć funkcję fi zadeklarować, że funkcja gjest taka sama jak f, ale z ograniczoną domeną, aby uwzględnić tylko fnajlepszy przypadek, a następnie zrobić coś szalonego g, ale zaczyna brzmieć zdegenerowana, kiedy to robisz że.
Cort Ammon
5

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!

Turing
źródło
4

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).

Theo Brinkman
źródło
1
(2) jest całkowicie błędne. Zwykle bierze się pod uwagę „długość wejścia”. W przypadku listy lub tablicy obiektów o stałym rozmiarze (takich jak liczby całkowite) będzie to rzeczywiście rozmiar zestawu. Aby wziąć pod uwagę liczbę taką jak 1395195191600333, będzie to długość jej reprezentacji binarnej (lub dziesiętnej itp.), Tj. Liczba cyfr. Jak stwierdzono w twojej definicji w (2), zabrania się używania big-O do omawiania złożoności "findPrimeFactors (int num)", czemu sprzeciwi się większość kryptologów.
djechlin
4

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

Davislor
źródło
Gdzie mamy N = 13.
djechlin
Ale nie tylko wypisuje „Witaj świecie”, ale także nieznaną liczbę wierszy „Jeszcze nie czas”. Ponadto Big O nie jest tak naprawdę używane do porównywania rozmiaru wejścia z rozmiarem wyjścia, jest zwykle używane do porównywania rozmiaru wejścia z liczbą operacji lub ilością wykorzystanej pamięci.
Servy
@Servy To stała pamięć, ale pośrednio ograniczałem czas wykonywania. Rozmiar wyniku to również O ( N ), dla dowolnego ciągu: ciąg, który drukujemy, gdy nadejdzie czas, może być dowolnie duży, nawet w porównaniu do dwudziestu lat wiadomości proszę czekać.
Davislor,
@Servy Edytowałem, aby wyjaśnić, że nie, N tutaj nie jest rozmiarem wyniku. Nie jestem pewien, jak zrobiłem to wrażenie, ale usunę wszelkie niejasności.
Davislor,
1
Więc jeśli założymy, że program przyjmuje dane wejściowe, a gdy nie, to wyjście może być dowolnie duże, kiedy nie może, że pętla nic nie robi, kiedy robi, i że wyjście jest powiązane z wejście, jeśli nie jest, to tak, program jest liniowy. Oczywiście każde z tych założeń jest całkowicie fałszywe, więc wniosek, który z nich wyciągnąłeś, nie jest prawdziwy. Jeśli jesteś w stanie zademonstrować swój punkt widzenia bez robienia fałszywych założeń, to by coś znaczyło.
Servy
4

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).

Nathan FD
źródło
2

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 2 . Można więc powiedzieć, że czas działania wynosi O(max(2035 - start year, 1))3 . 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);4

1 Dotyczy to bardziej technicznego sensu czasu wykonania mierzonego jako liczba operacji, ponieważ istnieje maksymalna liczba operacji na jednostkę czasu.
2 Zakładając, że pobieranie DateTime.Nowjest operacją ciągłą, co jest rozsądne.
3 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.
4 Wtedy algorytm nie zależy już od niejawnych danych wejściowych czasu rozpoczęcia, ale nie ma to znaczenia.

Nathan FD
źródło
1

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 
Angel Koh
źródło