Czy są jakieś algorytmy O (1 / n)?

Czy są jakieś algorytmy O (1 / n)?

Lub cokolwiek innego, co jest mniejsze niż O (1)?

To pytanie nie jest tak głupie, jak mogłoby się wydawać. Przynajmniej teoretycznie coś takiego jak O (1 / n ) jest całkowicie sensowne, gdy weźmiemy matematyczną definicję notacji Big O :

Teraz możesz łatwo podstawić g ( x ) na 1 / x … to oczywiste, że powyższa definicja wciąż obowiązuje dla niektórych f .

W celu oszacowania asymptotycznego wzrostu czasu pracy jest to mniej realne… znaczący algorytm nie może przyspieszyć w miarę wzrostu nakładów. Jasne, możesz zbudować dowolny algorytm, aby to spełnić, np. Następujący:

def get_faster(list):
    how_long = (1 / len(list)) * 100000
    sleep(how_long)

Oczywiście funkcja ta spędza mniej czasu, gdy rozmiar wejściowy rośnie… przynajmniej do pewnego limitu, narzuconego przez sprzęt (precyzja liczb, minimalny czas sleepoczekiwania, czas na przetwarzanie argumentów itp.): Limit ten byłby wtedy stała dolna granica, więc w rzeczywistości powyższa funkcja nadal ma czas działania O (1).

Ale nie są w rzeczywistości algorytmów w rzeczywistym świecie, gdzie czas pracy może zmniejszyć (przynajmniej częściowo), kiedy wzrostem wielkości wejściowych. Zauważ jednak, że te algorytmy nie będą wykazywać zachowania w czasie wykonywania poniżej O (1). Mimo to są interesujące. Weźmy na przykład bardzo prosty algorytm wyszukiwania tekstu autorstwa Horspool . Tutaj oczekiwany czas działania zmniejsza się wraz ze wzrostem długości wzorca wyszukiwania (ale zwiększenie długości stogu siana ponownie zwiększy czas działania).

Tak.

Istnieje dokładnie jeden algorytm z czasem wykonania O (1 / n), czyli algorytm „pusty”.

Algorytm oznaczony jako O (1 / n) oznacza, że ​​wykonuje się asymptotycznie w mniejszej liczbie kroków niż algorytm składający się z pojedynczej instrukcji. Jeśli wykonuje się mniej niż jeden krok dla wszystkich n> n0, musi składać się z dokładnie żadnej instrukcji dla tych n. Ponieważ sprawdzenie „jeśli n> n0” kosztuje co najmniej 1 instrukcję, nie może składać się z żadnej instrukcji dla wszystkich n.

Podsumowując: jedynym algorytmem, którym jest O (1 / n), jest algorytm pusty, składający się z braku instrukcji.

sharptooth jest poprawny, O (1) to najlepsza możliwa wydajność. Nie oznacza to jednak szybkiego rozwiązania, a jedynie rozwiązanie o ustalonym czasie.

Ciekawym wariantem i być może tak naprawdę sugerowanym jest to, które problemy stają się łatwiejsze w miarę wzrostu populacji. Mogę wymyślić 1, choć wymyśloną i wymowną odpowiedź:

Czy jakieś dwie osoby w zestawie mają te same urodziny? Gdy n przekroczy 365, zwróć true. Chociaż dla mniej niż 365, jest to O (n ln n). Być może nie jest to świetna odpowiedź, ponieważ problem nie powoli staje się łatwiejszy, ale staje się O (1) dla n> 365.

To nie jest możliwe. Definicja Big-O jest nie większa niż nierówność:

A(n) = O(B(n))
<=>
exists constants C and n0, C > 0, n0 > 0 such that
for all n > n0, A(n) <= C * B(n)

Tak więc B (n) jest w rzeczywistości wartością maksymalną, dlatego jeśli zmniejsza się wraz ze wzrostem n, oszacowanie się nie zmienia.

Z mojej poprzedniej nauki o dużej notacji O, nawet jeśli potrzebujesz 1 kroku (takiego jak sprawdzenie zmiennej, wykonanie przypisania), to znaczy O (1).

Zauważ, że O (1) jest takie samo jak O (6), ponieważ „stała” nie ma znaczenia. Dlatego mówimy, że O (n) jest takie samo jak O (3n).

Więc jeśli potrzebujesz nawet 1 kroku, to jest O (1) ... a ponieważ twój program wymaga co najmniej 1 kroku, minimalnym algorytmem może być O (1). Chyba że jeśli tego nie zrobimy, to myślę, że to O (0)? Jeśli w ogóle coś robimy, to jest to O (1) i jest to minimum, które może przejść.

(Jeśli zdecydujemy się tego nie robić, może stać się pytaniem Zen lub Tao ... w dziedzinie programowania O (1) jest nadal minimum).

A może to:

programista : szefie, znalazłem sposób na zrobienie tego w czasie O (1)!
szef : nie trzeba tego robić, dziś jesteśmy bankrutem.
programista : och, wtedy staje się O (0).

Nie, nie jest to możliwe:

Ponieważ n ma tendencję do nieskończoności w 1 / n, ostatecznie osiągamy 1 / (inf), co w rzeczywistości wynosi 0.

Tak więc, duża klasa problemu to O (0) z masywnym n, ale bliższym stałemu czasowi z niskim n. Nie jest to rozsądne, ponieważ jedyne, co można zrobić w szybszym niż stały czasie, to:

void nothing() {};

I nawet to jest dyskusyjne!

Jak tylko wykonasz polecenie, jesteś w co najmniej O (1), więc nie, nie możemy mieć wielkiej klasy O (1 / n)!

A może w ogóle nie uruchamiać tej funkcji (NOOP)? lub przy użyciu stałej wartości. To się liczy?

Często używam O (1 / n) do opisania prawdopodobieństw, które stają się mniejsze w miarę powiększania się danych wejściowych - na przykład prawdopodobieństwo, że rzetelna moneta pojawi się na rewersie log2 (n), wynosi O (1 / n).

O (1) oznacza po prostu „stały czas”.

Po dodaniu wczesnego wyjścia do pętli [1] (w notacji wielkiej-O) zamieniasz algorytm O (1) na O (n), ale przyspieszasz.

Sztuczka polega na tym, że algorytm stałego czasu jest najlepszy, a liniowy jest lepszy niż wykładniczy, ale dla małych ilości n algorytm wykładniczy może być rzeczywiście szybszy.

1: Zakładając statyczną długość listy dla tego przykładu

Dla każdego, kto czyta to pytanie i chce zrozumieć, o czym jest rozmowa, może to pomóc:

|    |constant |logarithmic |linear|  N-log-N |quadratic|  cubic  |  exponential  |
|  n |  O(1)   | O(log n)   | O(n) |O(n log n)|  O(n^2) |  O(n^3) |     O(2^n)    |
|  1 |       1 |          1 |     1|         1|        1|       1 |             2 |
|  2 |       1 |          1 |     2|         2|        4|       8 |             4 |
|  4 |       1 |          2 |     4|         8|       16|      64 |            16 |
|  8 |       1 |          3 |     8|        24|       64|     512 |           256 |
| 16 |       1 |          4 |    16|        64|      256|   4,096 |         65536 |
| 32 |       1 |          5 |    32|       160|    1,024|  32,768 | 4,294,967,296 |
| 64 |       1 |          6 |    64|       384|    4,069| 262,144 |   1.8 x 10^19 |

Wierzę, że algorytmy kwantowe mogą wykonywać wiele obliczeń „naraz” za pomocą superpozycji ...

Wątpię, czy to przydatna odpowiedź.

wiele osób miało poprawną odpowiedź (Nie) Oto inny sposób, aby to udowodnić: Aby mieć funkcję, musisz wywołać tę funkcję i musisz zwrócić odpowiedź. Zajmuje to pewną stałą ilość czasu. NAWET JEŚLI reszta przetwarzania zajęła mniej czasu w przypadku większych danych wejściowych, wydrukowanie odpowiedzi (którą możemy założyć jako jeden bit) zajmuje co najmniej stały czas.

Jeśli istnieje rozwiązanie, można je przygotować i uzyskać do niego dostęp w stałym czasie = natychmiast. Na przykład przy użyciu struktury danych LIFO, jeśli wiesz, że zapytanie sortujące dotyczy odwrotnej kolejności. Następnie dane są już sortowane, biorąc pod uwagę, że wybrano odpowiedni model (LIFO).

Które problemy stają się łatwiejsze wraz ze wzrostem populacji? Jedna odpowiedź to coś w rodzaju bittorrent, gdzie prędkość pobierania jest odwrotną funkcją liczby węzłów. W przeciwieństwie do samochodu, który spowalnia, im bardziej go ładujesz, sieć wymiany plików, taka jak bittorrent, przyspiesza, tym więcej połączonych węzłów.

Nie możesz zejść poniżej O (1), jednak możliwe jest O (k), gdzie k jest mniejsze niż N. Nazwaliśmy je sublinearnymi algorytmami czasu . W przypadku niektórych problemów algorytm czasu podliniowego może jedynie dać przybliżone rozwiązania określonego problemu. Czasami jednak przybliżone rozwiązania są w porządku, prawdopodobnie dlatego, że zestaw danych jest zbyt duży lub że jest zbyt kosztowny obliczeniowo, aby obliczyć wszystko.

A co z tym:

void FindRandomInList(list l)
{
    while(1)
    {
        int rand = Random.next();
        if (l.contains(rand))
            return;
    }
}

wraz ze wzrostem wielkości listy zmniejsza się oczekiwany czas działania programu.

O (1 / n) jest nie mniejsze niż O (1), to w zasadzie oznacza, że ​​im więcej danych masz, tym szybszy jest algorytm. Powiedzmy, że dostajesz tablicę i zawsze wypełniaj ją do 10 ¹⁰⁰ elementów, jeśli ma mniej tego, i nie rób nic, jeśli jest więcej. Oczywiście nie jest to O (1 / n), ale coś w rodzaju O (-n) :) Szkoda, że ​​notacja O-big nie pozwala na wartości ujemne.

Jak już wspomniano, oprócz możliwego wyjątku funkcji zerowej, nie może być żadnych O(1/n)funkcji, ponieważ czas będzie musiał zbliżyć się do 0.

Oczywiście istnieją pewne algorytmy, takie jak te zdefiniowane przez Konrada, które wydają się być mniej niż O(1)w jakimś sensie.

def get_faster(list):
    how_long = 1/len(list)
    sleep(how_long)

Jeśli chcesz zbadać te algorytmy, powinieneś albo zdefiniować własny pomiar asymptotyczny, albo własne pojęcie czasu. Na przykład w powyższym algorytmie mógłbym zezwolić na użycie pewnej liczby „wolnych” operacji określoną liczbę razy. W powyższym algorytmie, jeśli zdefiniuję t 'poprzez wykluczenie czasu na wszystko oprócz snu, wtedy t' = 1 / n, czyli O (1 / n). Prawdopodobnie są lepsze przykłady, ponieważ zachowanie asymptotyczne jest banalne. W rzeczywistości jestem pewien, że ktoś może wymyślić zmysły, które dają nietrywialne rezultaty.

Większość pozostałych odpowiedzi interpretuje duże-O wyłącznie na temat czasu działania algorytmu. Ale ponieważ pytanie nie wspomniało o tym, pomyślałem, że warto wspomnieć o innym zastosowaniu big-O w analizie numerycznej, które dotyczy błędu.

Wiele algorytmów może być O (h ^ p) lub O (n ^ {- p}) w zależności od tego, czy mówisz o stopniu kroku (h) czy liczbie podziałów (n). Na przykład w metodzie Eulera szukasz szacunku y (h), biorąc pod uwagę, że znasz y (0) i dy / dx (pochodna y). Twoje oszacowanie y (h) jest dokładniejsze, im bliżej h do 0. Więc aby znaleźć y (x) dla dowolnego dowolnego x, bierze się przedział od 0 do x, dzieli go na n kawałków i uruchamia metodę Eulera w każdym punkcie, aby uzyskać od y (0) do y (x / n) do y (2x / n) i tak dalej.

Zatem metoda Eulera jest wówczas algorytmem O (h) lub O (1 / n), gdzie h jest zwykle interpretowane jako wielkość kroku, a n jest interpretowane jako liczba podziałów przedziału.

Możesz również mieć O (1 / h) w rzeczywistych aplikacjach do analizy numerycznej, z powodu błędów zaokrąglania zmiennoprzecinkowego . Im mniejszy interwał, tym więcej anulowań ma miejsce w przypadku implementacji niektórych algorytmów, większa utrata znaczących cyfr, a tym samym więcej błędów, które są propagowane przez algorytm.

W przypadku metody Eulera, jeśli używasz zmiennoprzecinkowych, użyj wystarczająco małego kroku i anuluj, a dodajesz małą liczbę do dużej liczby, pozostawiając dużą liczbę bez zmian. Dla algorytmów obliczających pochodną poprzez odejmowanie od siebie dwóch liczb od funkcji ocenianej w dwóch bardzo bliskich pozycjach, przybliżając y '(x) za pomocą (y (x + h) - y (x) / h), w funkcjach gładkich y (x + h) zbliża się do y (x), co skutkuje dużym anulowaniem i szacunkiem dla instrumentu pochodnego o mniejszej liczbie znaczących. To z kolei rozprzestrzeni się na dowolny algorytm, dla którego potrzebujesz pochodnej (np. Problem z wartością graniczną).

OK, trochę się nad tym zastanowiłem i być może istnieje algorytm, który mógłby przyjąć tę ogólną formę:

Musisz obliczyć problem podróżnego sprzedawcy dla wykresu 1000 węzłów, ale otrzymasz również listę węzłów, których nie możesz odwiedzić. W miarę powiększania się listy niewidzialnych węzłów problem staje się łatwiejszy do rozwiązania.

Widzę algorytm, który jest O (1 / n) wprawdzie w górnej granicy:

Masz dużą serię wejść, które zmieniają się z powodu czegoś zewnętrznego w stosunku do rutyny (być może odzwierciedlają sprzęt lub może to być jakiś inny rdzeń procesora.) I musisz wybrać losowe, ale prawidłowe.

Teraz, jeśli to się nie zmienia, po prostu tworzysz listę przedmiotów, wybierasz jeden losowo i dostajesz czas O (1). Jednak dynamiczny charakter danych wyklucza tworzenie listy, wystarczy sondować losowo i przetestować ważność sondy. (I pamiętaj, że z natury nie ma gwarancji, że odpowiedź jest nadal ważna po jej zwróceniu. To wciąż może mieć zastosowanie - powiedzmy, AI dla jednostki w grze. Może strzelać do celu, który wypadł z pola widzenia, gdy był pociągając za spust).

Ma to najgorszy przypadek nieskończoności, ale przeciętna wydajność spada, gdy przestrzeń danych zapełnia się.

W analizie numerycznej algorytmy aproksymacyjne powinny mieć sub-stałą asymptotyczną złożoność w tolerancji aproksymacyjnej.

class Function
{
    public double[] ApproximateSolution(double tolerance)
    {
        // if this isn't sub-constant on the parameter, it's rather useless
    }
}

Chyba mniej niż O (1) nie jest możliwe. Każdy czas zajęty przez algo jest określany jako O (1). Ale w przypadku O (1 / n) co powiesz na poniższą funkcję. (Wiem, że w tym rozwiązaniu jest już wiele wariantów, ale wydaje mi się, że wszystkie mają pewne wady (nie poważne, dobrze wyjaśniają koncepcję). Oto jeden, tylko ze względu na argument:

def 1_by_n(n, C = 10):   #n could be float. C could be any positive number
  if n <= 0.0:           #If input is actually 0, infinite loop.
    while True:
      sleep(1)           #or pass
    return               #This line is not needed and is unreachable
  delta = 0.0001
  itr = delta
  while delta < C/n:
    itr += delta

Zatem wraz ze wzrostem liczby n funkcja ta zajmuje coraz mniej czasu. Zapewnione jest również, że jeśli wejście faktycznie wynosi 0, to funkcja zajmie wieczność.

Można argumentować, że będzie ograniczona precyzją maszyny. tak więc sinc eit ma górną granicę, to O (1). Ale możemy to również obejść, przyjmując wartości wejściowe n i C w ciągu. Dodawanie i porównywanie odbywa się na łańcuchu. Chodzi o to, że dzięki temu możemy zmniejszyć n dowolnie małe. Zatem górna granica funkcji nie jest ograniczona, nawet jeśli zignorujemy n = 0.

Uważam również, że nie możemy po prostu powiedzieć, że czas działania wynosi O (1 / n). Ale powinniśmy powiedzieć coś takiego jak O (1 + 1 / n)

Może być możliwe skonstruowanie algorytmu, który jest O (1 / n). Przykładem może być pętla, która iteruje pewną wielokrotność f (n) -n razy, gdzie f (n) jest jakąś funkcją, której wartość jest gwarantowana większa niż n, a granica f (n) -n, gdy n zbliża się do nieskończoności, wynosi zero. Obliczenie f (n) również musiałoby być stałe dla wszystkich n. Nie wiem od razu, jak wyglądałby f (n) lub jaką aplikację miałby taki algorytm, jednak moim zdaniem taka funkcja mogłaby istnieć, ale wynikowy algorytm nie miałby innego celu niż udowodnienie możliwości algorytmu z O (1 / n).

Nie wiem o algorytmach, ale w algorytmach losowych występują złożoności mniejsze niż O (1). W rzeczywistości o (1) (małe o) jest mniejsze niż O (1). Ten rodzaj złożoności zwykle pojawia się w algorytmach losowych. Na przykład, jak powiedziałeś, gdy prawdopodobieństwo jakiegoś zdarzenia jest rzędu 1 / n, oznacza to je o (1). Lub gdy chcą powiedzieć, że coś dzieje się z dużym prawdopodobieństwem (np. 1 - 1 / n), oznaczają to 1 - o (1).

Jeśli odpowiedź jest taka sama niezależnie od danych wejściowych, oznacza to, że masz algorytm O (0).

lub innymi słowy - odpowiedź jest znana przed przesłaniem danych wejściowych - funkcja może zostać zoptymalizowana - więc O (0)

Notacja Big-O reprezentuje najgorszy scenariusz dla algorytmu, który nie jest tym samym, co jego typowy czas działania. Łatwo jest udowodnić, że algorytm O (1 / n) jest algorytmem O (1). Z definicji
O (1 / n) -> T (n) <= 1 / n, dla wszystkich n> = C> 0
O (1 / n) -> T (n) <= 1 / C, ponieważ 1 / n <= 1 / C dla wszystkich n> = C
O (1 / n) -> O (1), ponieważ notacja Big-O ignoruje stałe (tzn. Wartość C nie ma znaczenia)

Nic nie jest mniejsze niż O (1) Notacja Big-O implikuje największą kolejność złożoności algorytmu

Jeśli czas działania algorytmu wynosi n ^ 3 + n ^ 2 + n + 5, to jest to O (n ^ 3) Mniejsze moce nie mają tu żadnego znaczenia, ponieważ jako n -> Inf, n ^ 2 będzie nieistotne w porównaniu z n ^ 3

Podobnie, jak n -> Inf, O (1 / n) będzie nieistotne w porównaniu z O (1), stąd 3 + O (1 / n) będzie takie samo jak O (1), dzięki czemu O (1) będzie najmniejszym możliwym obliczeniem złożoność

inline void O0Algorithm() {}

Oto prosty algorytm O (1 / n). I robi nawet coś ciekawego!

function foo(list input) {
  int m;
  double output;

  m = (1/ input.size) * max_value;  
  output = 0;
  for (int i = 0; i < m; i++)
    output+= random(0,1);

  return output;
}

O (1 / n) jest możliwe, ponieważ opisuje, jak zmienia się wyjście funkcji, biorąc pod uwagę rosnący rozmiar danych wejściowych. Jeśli używamy funkcji 1 / n do opisania liczby instrukcji wykonywanych przez funkcję, nie ma wymogu, aby funkcja przyjmowała instrukcje zerowe dla dowolnego rozmiaru wejściowego. Raczej chodzi o to, że dla każdego rozmiaru wejściowego, n powyżej pewnego progu, liczba wymaganych instrukcji jest ograniczona przez dodatnią stałą pomnożoną przez 1 / n. Ponieważ nie ma rzeczywistej liczby, dla której 1 / n wynosi 0, a stała jest dodatnia, nie ma powodu, dla którego funkcja musiałaby przyjmować 0 lub mniej instrukcji.