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

335

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

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

Peter Mortensen
źródło
Większość pytań zakłada, że ​​masz na myśli „Czy są jakieś algorytmy o złożoności czasowej O (1 / n)?” Czy możemy założyć, że tak jest? Big-O (i Big-Theta itp.) Opisują funkcje, a nie algorytmy. (Nie znam równoważności funkcji i algorytmów).
jyoungdev,
4
Jest to powszechnie rozumiana definicja „algorytmu O (X)” w informatyce: algorytm, którego złożoność czasowa wynosi O (X) (dla niektórych wyrażeń X).
David Z
2
Słyszałem o takim powiązaniu w przypadku wydajnego algorytmu kolejki priorytetowej we / wy korzystającego z drzewa buforów. W drzewie buforów każda operacja wymaga operacji we / wy O (1 / B); gdzie B jest rozmiarem bloku. Łączna liczba operacji we / wy dla n operacji wynosi O (n / B.log (podstawa M / B) (n / B)), gdzie część logu jest wysokością drzewa buforów.
CODError
Istnieje wiele algorytmów z prawdopodobieństwem błędu O (1 / n). Na przykład filtr Bloom z O (n log n) wiaderkami.
Thomas Ahle
Nie możesz złożyć jaja szybciej, dodając kurczaki.
Wyck

Odpowiedzi:

310

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

Konrad Rudolph
źródło
22
„Egzekwowane przez sprzęt” dotyczy także maszyny Turinga. W przypadku O (1 / n) zawsze będzie wielkość wejściowa, dla której algorytm nie powinien wykonywać żadnej operacji. Dlatego sądzę, że złożoność czasowa O (1 / n) jest rzeczywiście niemożliwa do osiągnięcia.
Roland Ewald
28
Mehrdad, nie rozumiesz. Notacja O jest czymś na temat granicy (technicznie lim sup) jako n -> ∞. Czas działania algorytmu / programu to liczba kroków na niektórych komputerach, dlatego też jest dyskretny - istnieje niezerowa dolna granica czasu, który może zająć algorytm („jeden krok”). Możliwe jest , że do pewnej skończonej liczby N program wykonuje szereg kroków zmniejszających się za pomocą n, ale jedynym sposobem, w którym algorytmem może być O (1 / n), a nawet o (1), jest to, że zajmuje czas 0 dla wszystkich wystarczająco duże n - co nie jest możliwe.
ShreevatsaR
28
Nie zgadzamy się, że istnieją funkcje O (1 / n) (w sensie matematycznym). Oczywiście, że tak. Ale obliczenia są z natury dyskretne. Coś, co ma dolną granicę, takie jak czas działania programu - na architekturze von Neumanna lub na czysto abstrakcyjnej maszynie Turinga - nie może być O (1 / n). Odpowiednio coś, co jest O (1 / n), nie może mieć dolnej granicy. (Należy wywołać funkcję „uśpienia” lub zbadać zmienną „listę” - lub taśmę wejściową należy zbadać na maszynie Turinga. Tak więc czas zmieniłby się przy n jako pewnym ε + 1 / n, co nie jest O (1 / n))
ShreevatsaR
16
Jeśli T (0) = ∞, nie zatrzymuje się. Nie ma czegoś takiego jak „T (0) = ∞, ale nadal się zatrzymuje”. Ponadto, nawet jeśli pracujesz w R∪ {∞} i zdefiniujesz T (0) = ∞, a T (n + 1) = T (n) / 2, to T (n) = ∞ dla wszystkich n. Powtórzę: jeśli funkcją o wartościach dyskretnych jest O (1 / n), to dla wszystkich wystarczająco dużych n wynosi 0. [Dowód: T (n) = O (1 / n) oznacza, że ​​istnieje stała c taka, że dla n> N0, T (n) <c (1 / n), co oznacza, że ​​dla dowolnego n> max (N0,1 / c), T (n) <1, co oznacza T (n) = 0.] Żadna maszyna, rzeczywista ani abstrakcyjna, nie może zająć 0 czasu: musi patrzeć na dane wejściowe. Poza maszyną, która nigdy nic nie robi i dla której T (n) = 0 dla wszystkich n.
ShreevatsaR
43
Musisz polubić każdą odpowiedź, która się zaczyna: „To pytanie nie jest tak głupie, jak mogłoby się wydawać”.
Telemachus
138

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.

Tobiasz
źródło
2
Więc jeśli ktoś zapyta, jaka jest złożoność czasowa pustego algorytmu, odpowiedziałbyś O (1 / n) ??? Jakoś w to wątpię.
phkahler
24
To jest jedyna poprawna odpowiedź w tym wątku i (pomimo mojego poparcia) ma zero głosów. Taki jest StackOverflow, w którym odpowiedzi „poprawne” są głosowane wyżej niż faktycznie poprawne.
ShreevatsaR
5
Nie, ma ocenę 0, ponieważ jest niepoprawna. Wyrażanie wartości dużego Oh w stosunku do N, gdy jest ona niezależna od N, jest niepoprawna. Po drugie, uruchomienie dowolnego programu, nawet takiego, który właśnie istnieje, zajmuje co najmniej stałą ilość czasu, O (1). Nawet gdyby tak nie było, byłoby to O (0), a nie O (1 / n).
kenj0418
32
Każda funkcja, która jest O (0), jest również O (1 / n), a także O (n), także O (n ^ 2), również O (2 ^ n). Westchnienie, czy nikt nie rozumie prostych definicji? O () to górna granica.
ShreevatsaR
16
@ kenj0418 Udało ci się pomylić w każdym zdaniu. „Wyrażanie dużej wartości Oh w stosunku do N, gdy jest ono niezależne od N, jest nieprawidłowe”. Stała funkcja jest funkcją idealnie idiotyczną. „Po drugie, uruchomienie dowolnego programu, nawet takiego, który właśnie istnieje, zajmuje co najmniej stałą ilość czasu, O (1).” Definicja złożoności nie mówi nic o faktycznym uruchamianiu jakichkolwiek programów. „byłoby O (0), a nie O (1 / n)”. Zobacz komentarz @ ShreevatsaR.
Aleksiej Romanow
25

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.

Adrian
źródło
7
366. Nie zapomnij o latach przestępnych!
Nick Johnson
1
Masz rację. Podobnie jak komputery, czasami mam błędy zaokrąglania :-)
Adrian
10
+1. Istnieje wiele problemów z uzupełnieniem NP, które przechodzą „przejście fazowe” wraz ze wzrostem liczby n, tzn. Szybko stają się znacznie łatwiejsze lub trudniejsze, gdy przekroczysz pewną wartość progową n. Jednym z przykładów jest problem z partycjonowaniem liczb: biorąc pod uwagę zbiór n nieujemnych liczb całkowitych, podziel je na dwie części, aby suma każdej części była równa. Staje się to znacznie łatwiejsze przy pewnej wartości progowej n.
j_random_hacker
23

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.

sharptooth
źródło
42
Podejrzewam, że ta odpowiedź jest „właściwa”, ale niestety brakuje mi rozumu, aby ją zrozumieć.
wolna przestrzeń
12
AFAIK ten warunek nie musi być spełniony dla wszystkich n, ale dla wszystkich n> n_0 (tj. Tylko wtedy, gdy wielkość danych wejściowych osiągnie określony próg).
Roland Ewald
30
Nie rozumiem, w jaki sposób definicja (nawet poprawiona) stoi w sprzeczności z kwestią PO. Definicja dotyczy całkowicie dowolnych funkcji! 1 / n jest całkowicie sensowną funkcją dla B i w rzeczywistości twoje równanie temu nie zaprzecza (po prostu wykonaj matematykę). Więc nie, pomimo dużego konsensusu, ta odpowiedź jest w rzeczywistości błędna . Przepraszam.
Konrad Rudolph
10
Źle! Nie lubię głosować z góry, ale twierdzisz, że jest to niemożliwe, gdy nie ma wyraźnego konsensusu. W praktyce masz rację, jeśli zbudujesz funkcję z czasem działania 1 / n (łatwym), w końcu osiągnie pewien minimalny czas, skutecznie czyniąc go algorytmem O (1), gdy zostanie zaimplementowany. Jednak nic nie stoi na przeszkodzie, aby algorytm stał się O (1 / n) na papierze.
jheriko
3
@Jason: Tak, teraz, kiedy to mówisz ... :) @jheriko: Złożoność czasowa O (1 / n) nie działa na papierze IMHO. Charakteryzujemy funkcję wzrostu f (wielkość wejściowa) = #ops dla maszyny Turinga. Jeśli zatrzyma się dla danych wejściowych o długości n = 1 po x krokach, wówczas wybiorę rozmiar wejściowy n >> x, tj. Wystarczająco duży, aby jeśli algorytm rzeczywiście był w O (1 / n), żadna operacja nie powinna być wykonana gotowy. Jak maszyna Turinga powinna to zauważyć (nie wolno czytać raz z taśmy)?
Roland Ewald
16

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

動靜 能量
źródło
Twój żart przypomniał mi coś z Tao programowania: canonical.org/~kragen/tao-of-programming.html#book8 (8.3)
kenj0418
Algorytm składający się z zerowych kroków to O (0). To bardzo leniwy algorytm.
dokładnie 10.10.11
8

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

Ed James
źródło
7

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

SpliFF
źródło
16
To wciąż środowisko uruchomieniowe O (1).
Konrad Rudolph,
2
Racja, to wciąż O (1). Nie rozumiem, jak ktoś może to zrozumieć, a jednak twierdzą w innej odpowiedzi, że możliwe jest coś mniej niż BRAK OP.
ShreevatsaR
4
ShreevatsaR: absolutnie nie ma sprzeczności. Wydaje się, że nie rozumiesz, że duża notacja O nie ma nic wspólnego z czasem spędzonym w funkcji - raczej opisuje, jak ten czas zmienia się wraz ze zmianą danych wejściowych (powyżej pewnej wartości). Zobacz inny wątek komentarza, aby uzyskać więcej.
Konrad Rudolph,
Doskonale to rozumiem, dziękuję. Chodzi o to - jak już kilkakrotnie robiłem w drugim wątku - że jeśli czas maleje wraz z wejściem, z prędkością O (1 / n), to ostatecznie musi się zmniejszyć poniżej czasu potrzebnego NOOP. To pokazuje, że żaden algorytm nie może być O (1 / n) asymptotycznie, chociaż na pewno jego czas działania może się zmniejszyć do granicy.
ShreevatsaR
1
Tak ... jak powiedziałem gdzie indziej, każdy algorytm, który jest O (1 / n), powinien również zająć zero czasu dla wszystkich danych wejściowych, więc w zależności od tego, czy uważasz, że algorytm zerowy zajmuje 0 czasu, czy nie, istnieje O (1 / n) algorytm. Więc jeśli uważasz NOOP za O (1), to nie ma algorytmów O (1 / n).
ShreevatsaR
7

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

Dave
źródło
6
Ale to nie to, co jest duże O. Nie możesz po prostu przedefiniować go, aby odpowiedzieć na pytanie.
Zifre,
11
To nie jest redefinicja, to jest dokładnie definicja wielkiego O.
ShreevatsaR
10
Z zawodu jestem teoretycznym informatykiem. Chodzi o asymptotyczny porządek funkcji.
Dave
4
Big O jest własnością arbitralnej funkcji rzeczywistej. Złożoność czasu to tylko jedna z możliwych aplikacji. Złożoność przestrzeni (ilość pamięci roboczej wykorzystywanej przez algorytm) jest inna. To, że pytanie dotyczy algorytmów O (1 / n) , oznacza, że ​​jest to jeden z nich (chyba że istnieje inny, który dotyczy algorytmów, o których nie wiem). Inne zastosowania obejmują rzędy wzrostu populacji, np. W życiu Conwaya. Zobacz także en.wikipedia.org/wiki/Big_O_notation
Stewart
5
@Dave: Pytanie nie brzmiało, czy istnieją funkcje O (1 / n), które oczywiście istnieją. Raczej było to, czy istnieją algorytmy O (1 / n), które (z możliwym wyjątkiem funkcji zerowej) nie mogą istnieć
Casebash
6

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

LapTop006
źródło
6

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 |
Craig O'Connor
źródło
5

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

Wątpię, czy to przydatna odpowiedź.

Jeff Meatball Yang
źródło
To wciąż byłby stały czas, tj. O (1), co oznacza, że ​​uruchomienie danych o rozmiarze n zajmuje tyle samo czasu, co w przypadku danych o rozmiarze 1.
Wolna przestrzeń
2
Ale co, jeśli problemem byłoby blade piwo? (ah. hah. ha.)
Jeff Meatball Yang
7
To byłaby super pozycja.
Daniel Earwicker
1
Algorytmy kwantowe mogą wykonywać wiele obliczeń, ale można pobrać tylko jeden wynik i nie można wybrać, który wynik ma zostać uzyskany. Na szczęście możesz także wykonywać operacje na rejestrze kwantowym jako całości (na przykład QFT), więc znacznie łatwiej jest coś znaleźć :)
Gracenotes
2
być może nie jest to przydatne, ale ma tę zaletę, że jest prawdą, co stawia ją ponad niektórymi bardziej głosowanymi odpowiedziami B-)
Brian Postow
4

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.

Brian Postow
źródło
2

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

Larsson
źródło
2

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.

Niklas R.
źródło
Tak, ale liczba węzłów bittorrent jest bardziej podobna do liczby procesorów w komputerze równoległym. „N” w tym przypadku oznacza rozmiar pliku, który próbuje się pobrać. Tak jak można znaleźć element w nieposortowanej tablicy o długości N w stałym czasie, jeśli masz N komputerów, możesz pobrać plik o rozmiarze N w stałym czasie, jeśli N komputerów próbuje wysłać Ci dane.
Kibbee
2

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.

Hao Wooi Lim
źródło
1
Nie jestem pewien, czy rozumiem. Log (N) jest mniejszy niż N. Czy to oznacza, że ​​Log (N) jest algorytmem podliniowym? I istnieje wiele algorytmów Log (N). Jednym z takich przykładów jest znalezienie wartości w drzewie binarnym. Jednak wciąż różnią się one od 1 / N, ponieważ Log (N) zawsze rośnie, a 1 / n jest funkcją malejącą.
Kibbee
Patrząc na definicję, podliniowym algorytmem czasowym jest dowolny algorytm, którego czas rośnie wolniej niż rozmiar N. To obejmuje algorytm logarytmiczny czasu, którym jest Log (N).
Hao Wooi Lim
2
Uh, algorytmy czasu podliniowego mogą dać dokładne odpowiedzi, np. Wyszukiwanie binarne w uporządkowanej tablicy na maszynie RAM.
A. Rex
@ZA. Rex: Hao Wooi Lim powiedział „W niektórych problemach”.
LarsH
1

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.

Shalmanese
źródło
myślę, że nie rozumiesz znaczenia O (n)
Markus Lausberg
Jednak nie z listą, z tablicą lub skrótem gdzie constainsjest O (1)
vava
ok, funkcja losowa może być uważana za leniwą tablicę, więc zasadniczo przeszukujesz każdy element na „leniwej losowej liście” i sprawdzasz, czy jest on zawarty na liście wejściowej. Myślę, że jest to gorsze niż liniowe, a nie lepsze.
hasen
Ma trochę racji, jeśli zauważysz, że int ma ograniczony zestaw wartości. Więc kiedy l będzie zawierać 2 wartości <sup> 64 </sup>, będzie to natychmiastowe. Co czyni go gorszym niż O (1) :)
vava
1

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

vava
źródło
1
„O (1 / n) jest nie mniejsze niż O (1)” - jeśli funkcja f to O (1 / n), to również O (1). A big-oh wydaje się być relacją „mniejszą niż”: jest refleksyjna, przechodnia, a jeśli mamy symetrię między ig, to oba są równoważne, gdzie big-theta jest naszą relacją równoważności. ISTR „prawdziwe” relacje porządkowe wymagające <= b i b <= a, aby implikować a = b, a netcraft ^ W wikipedia to potwierdza. W pewnym sensie można więc powiedzieć, że rzeczywiście O (1 / n) jest „mniejsze niż” O (1).
Jonas Kölker
1

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.

Casebash
źródło
1

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

Andrew Lei
źródło
0

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.

Shalmanese
źródło
4
To jest inny rodzaj n w O (n). Dzięki tej sztuczce można powiedzieć, że każdy algorytm ma O (q), gdzie q jest liczbą osób mieszkających na przykład w Chinach.
vava
2
Boyer-Moore jest podobnego rodzaju (O (n / m)), ale to nie jest tak naprawdę „lepsze niż O (1)”, ponieważ n> = m. Myślę, że to samo dotyczy twojej „niewidzialnej TSP”.
Niki
Nawet w tym przypadku środowisko wykonawcze TSP jest NP-Complete, po prostu usuwasz węzły z wykresu, a zatem skutecznie zmniejszasz n.
Ed James
0

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

Loren Pechtel
źródło
0

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
    }
}
Sam Harwell
źródło
czy naprawdę masz na myśli sub-stałą czy podliniową? Dlaczego algorytmy aproksymacyjne powinny być substałe? A co to w ogóle oznacza?
LarsH
@LarsH, błąd algorytmów aproksymacyjnych jest proporcjonalny do wielkości kroku (lub jego dodatniej mocy), więc im mniejszy rozmiar kroku, tym mniejszy błąd. Ale innym powszechnym sposobem badania problemu aproksymacji jest błąd w porównaniu do tego, ile razy przedział jest dzielony. Liczba partycji przedziału jest odwrotnie proporcjonalna do wielkości kroku, więc błąd jest odwrotnie proporcjonalny do pewnej dodatniej mocy liczby partycji - wraz ze wzrostem liczby partycji błąd maleje.
Andrew Lei,
@AndrewLei: Wow, odpowiedź prawie 7 lat później! Rozumiem odpowiedź Sama teraz lepiej niż wtedy. Dziękuję za odpowiedź.
LarsH
0

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)

użytkownik1953366
źródło
-1

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

Greg
źródło
Twoja pętla wymaga sprawdzenia, które zajmuje co najmniej stały czas, więc wynikowy algorytm ma co najmniej złożoność O (1).
Stefan Reich,
-1

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

A. Mashreghi
źródło
-2

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)

pro
źródło
Naprawdę? Nadal będziesz musiał zwrócić wartość, więc czy nadal nie będzie to O (1)?
Joachim Sauer,
7
nie, O (0) oznaczałoby, że zabiera zero czasu dla wszystkich danych wejściowych. O (1) to stały czas.
Pete Kirkham
-2

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)

Lawrence Barsanti
źródło
Nie: Notacja Big O jest również używana do mówienia o scenariuszach średniej wielkości i oczekiwanym czasie (a nawet najlepszym przypadku). Reszta następuje.
Konrad Rudolph,
Notacja „O” z pewnością określa górną granicę (pod względem złożoności algorytmu byłby to najgorszy przypadek). Omega i Theta są używane do oznaczenia odpowiednio najlepszego i średniego przypadku.
Roland Ewald
2
Roland: To nieporozumienie; górna granica nie jest tym samym, co najgorszy przypadek, oba są niezależnymi koncepcjami. Rozważ oczekiwany (i średni) czas działania hashtable-containsalgorytmu, który można określić jako O (1) - a najgorszy przypadek można podać bardzo dokładnie jako Theta (n)! Omega i Theta mogą być po prostu używane do oznaczania innych granic, ale mówiąc to jeszcze raz : nie mają nic wspólnego ze średnią lub najlepszym przypadkiem.
Konrad Rudolph,
Konrad: Prawda. Mimo to, Omega, Theata i O są zwykle używane do wyrażenia granic, a jeśli wszystkie możliwe wejścia są uważane, O reprezentuje górne, itp
Roland Ewald
1
Fakt, że O (1 / n) jest podzbiorem O (1), jest trywialny i wynika bezpośrednio z definicji. W rzeczywistości, jeśli funkcja g jest O (h), to każda funkcja f, która jest O (g), jest również O (h).
Tobias
-2

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ść

użytkownik112831
źródło
-2
inline void O0Algorithm() {}
sth
źródło
1
Byłby to algorytm O (1).
Lasse V. Karlsen
2
To też, ale chodzi o to, że nie jest to Ω (1). I dlaczego moja odpowiedź została obniżona? Jeśli uważasz, że się mylę, to może wyjaśnienie?
Stewart
Zapytałem gdzie indziej, czy w zasadzie ta sama odpowiedź jest poprawna, czy nie, i wydaje się być kwestionowana: stackoverflow.com/questions/3209139/…
jyoungdev
Cóż, jest wbudowany, więc możesz rozważyć O (0). Jednak wszystkie algorytmy O (0) są trywialne (nic nie robią), więc ... niezbyt interesująca odpowiedź.
Stefan Reich
@StefanReich To prawda, nie jest to bardzo ciekawe rozwiązanie, ale to odpowiedź.
Stewart
-2

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.

ejspencer
źródło
1
Ponieważ O (1 / n) spadnie poniżej linii poziomej = 1, a gdy n osiągnie nieskończoność, twój kod będzie nadal wykonywał określoną liczbę kroków, ten algorytm jest algorytmem O (1). Notacja Big-O jest funkcją wszystkich różnych części algorytmu i wybiera największą. Ponieważ metoda zawsze uruchamia niektóre instrukcje, gdy n osiągnie nieskończoność, pozostaną ci te same instrukcje, które będą wykonywane za każdym razem, a zatem metoda będzie działać w stałym czasie. To prawda, że ​​nie będzie to dużo czasu, ale to nie dotyczy notacji Big-O.
Lasse V. Karlsen