Słyszałem kilka razy, że dla wystarczająco małych wartości n, O (n) można myśleć / traktować tak, jakby to był O (1).

Przykład :

Motywacja do tego jest oparta na błędnym założeniu, że O (1) jest zawsze lepsze niż O (lg n), zawsze jest lepsze niż O (n). Asymptotyczna kolejność operacji jest istotna tylko wtedy, gdy w realistycznych warunkach rozmiar problemu staje się naprawdę duży. Jeśli n pozostaje małe, to każdy problem to O (1)!

Co jest wystarczająco małe? 10? 100? 1000? W którym momencie mówisz „nie możemy już traktować tego jak operacji bezpłatnej”? Czy istnieje reguła praktyczna?

Wydaje się, że może to dotyczyć konkretnej domeny lub przypadku, ale czy istnieją jakieś ogólne zasady dotyczące tego, jak o tym myśleć?

Wszystkie rzędy wielkości obejmują stałą , a kilka z nich faktycznie. Gdy liczba elementów jest wystarczająco duża, stała nie ma znaczenia. Pytanie brzmi, czy liczba przedmiotów jest wystarczająco mała, aby ta stała mogła dominować.$C$

Oto wizualny sposób myślenia o tym.

Wszystkie mają stałą uruchamiania, która określa ich punkt początkowy na osi Y. Każdy z nich ma również stałą krytyczną dominującą, jak szybko będą wzrastać.$C$

• Do , oznacza czas.$O(1)$$C$
• C × n $O(n)$ to tak naprawdę , gdzie określa kąt.$C \times n$$C$
• ( C × n ) 2$O(n^2)$ to tak naprawdę , gdzie określa ostrość krzywej.$(C \times n)^2$$C$

Aby ustalić, którego algorytmu należy użyć, należy oszacować miejsce przecięcia środowiska wykonawczego. Na przykład rozwiązanie o wysokim czasie rozruchu lub wysokiej spowoduje utratę rozwiązania o niskim czasie uruchamiania i niskiej przy dość dużej liczbie elementów.C O ( n ) $O(1)$$C$$O(n)$$C$

Oto przykład z prawdziwego świata. Musisz przenieść kilka cegieł po podwórku. Możesz przesuwać je kilka naraz, lub iść po wielką, powolną koparko-ładowarkę, aby podnieść i przejechać je podczas jednej podróży. Jaka jest twoja odpowiedź, jeśli są trzy cegły? Jaka jest twoja odpowiedź, jeśli są trzy tysiące?

Oto przykład CS. Powiedzmy, że potrzebujesz listy, która jest zawsze posortowana. Możesz użyć drzewa, które zachowa się w porządku dla . Lub możesz użyć nieposortowanej listy i sortować ponownie po każdym wstawieniu lub usunięciu w . Ponieważ operacje na drzewie są skomplikowane (mają wysoką stałą), a sortowanie jest tak proste (niska stała), lista prawdopodobnie wygra do setek lub tysięcy przedmiotów.O ( n log n$O(\log{n})$$O(n \log{n})$

Możesz wpatrywać się w tego typu rzeczy, ale w końcu przeprowadzanie testów porównawczych. Musisz także sprawdzić, ile przedmiotów zwykle będziesz mieć, i zmniejszyć ryzyko, że dostaniesz więcej. Będziesz także chciał udokumentować swoje przypuszczenie, że „wydajność spadnie gwałtownie w stosunku do elementów” lub „zakładamy, że maksymalny ustawiony rozmiar ”.$X$$X$

Ponieważ wymagania te mogą ulec zmianie, ważne jest, aby tego rodzaju decyzje pozostawić za interfejsem. W powyższym przykładzie drzewa / listy nie ujawniaj drzewa ani listy. W ten sposób, jeśli twoje założenia okażą się błędne lub znajdziesz lepszy algorytm, możesz zmienić zdanie. Możesz nawet wykonać algorytmy hybrydowe i dynamicznie przełączać algorytmy wraz ze wzrostem liczby przedmiotów.

Jest to w dużej mierze poparcie dla już opublikowanych odpowiedzi, ale może oferować inną perspektywę.

Ujawnia to, że pytanie omawia „wystarczająco małe wartości n ”. Głównym celem Big-O jest opisanie wzrostu przetwarzania w zależności od tego, co jest przetwarzane. Jeśli przetwarzane dane pozostają małe, omawianie Big-O nie ma znaczenia, ponieważ nie jesteś zainteresowany wzrostem (co się nie dzieje).

Innymi słowy, jeśli idziesz bardzo blisko ulicy, spacerowanie, jazda rowerem lub jazda samochodem mogą być równie szybkie. Spacer może być nawet szybszy, jeśli znalezienie kluczyka zajęłoby trochę czasu lub samochód potrzebuje gazu itp.

W przypadku małych liter n użyj tego, co jest wygodne.

Jeśli wybierasz się na wycieczkę krajową, musisz spojrzeć na sposoby optymalizacji jazdy, zużycia paliwa itp.

Cytat jest raczej niejasny i nieprecyzyjny. Istnieją co najmniej trzy powiązane sposoby interpretacji.

Dosłowny matematyczny punkt za tym jest taki, że jeśli interesują Cię tylko przypadki wielkości do pewnego limitu, istnieje tylko wiele możliwych przypadków. Na przykład istnieje tylko skończona liczba wykresów na maksymalnie stu wierzchołkach. Jeśli istnieje tylko skończona liczba instancji, możesz w zasadzie rozwiązać problem, po prostu konstruując tabelę przeglądową wszystkich odpowiedzi na wszystkie możliwe instancje. Teraz możesz znaleźć odpowiedź, najpierw sprawdzając, czy dane wejściowe nie są zbyt duże (co zajmuje stały czas: jeśli dane wejściowe są dłuższe niż  $k$, jest niepoprawna), a następnie odszukaj odpowiedź w tabeli (co zajmuje cały czas: w tabeli jest stała liczba wpisów). Zauważ jednak, że rzeczywisty rozmiar stołu jest prawdopodobnie niemożliwie duży. Powiedziałem, że jest tylko skończona liczba wykresów na stu wierzchołkach i to prawda. Po prostu liczba skończona jest większa niż liczba atomów we obserwowalnym wszechświecie.

Bardziej praktyczne jest to, że, gdy mówimy, że czas działania algorytmu jest , że jedynym sposobem, który jest asymptotycznie c n dwa  etapy, na pewnej stałej  C . Oznacza to, że istnieje pewna stała n 0 taka, że ​​dla wszystkich n ≥ n 0 algorytm wykonuje z grubsza c n 2 kroków. Ale może n 0 = 100 , 000 , $\Theta(n^2)$ $cn^2$$C$$n_0$$n\geq n_0$$cn^2$$n_0=100,000,000$a interesują Cię tylko przypadki o wiele mniejsze niż to. Ta asymptotyczna granica kwadratowa może nawet nie dotyczyć twoich małych instancji. Możesz mieć szczęście i może być szybszy przy małych nakładach (lub możesz mieć pecha i sprawić, że będzie wolniejszy). Na przykład dla małych  , n 2 < 1000 n, więc wolisz uruchomić algorytm kwadratowy z dobrymi stałymi niż algorytm liniowy ze złymi stałymi. A Przykład prawdziwe do tego jest to, że asymptotycznie najbardziej efektywne algorytmy macierzy (warianty Coppersmith-Winograd , działa w czasie O ( n 2,3729 ) ), rzadko stosuje się w praktyce, ponieważ Strassena $n$$n^2 < 1000n$$O(n^{2.3729})$ algorytm jest szybszy, chyba że macierze są naprawdę duże.$O(n^{2.8074})$

Trzecią kwestią jest to, że jeśli  jest małe, n 2, a nawet n 3  są małe. Na przykład, jeśli chcesz posortować kilka tysięcy elementów danych i musisz je posortować tylko raz, dowolny algorytm sortowania jest wystarczający: a Θ ( n 2$n$$n^2$$n^3$$\Theta(n^2)$Algorytm nadal będzie potrzebował tylko kilkudziesięciu milionów instrukcji do sortowania danych, co wcale nie zajmuje dużo czasu na procesorze, który może wykonać miliardy instrukcji na sekundę. OK, są też dostępy do pamięci, ale nawet powolny algorytm zajmie mniej niż sekundę, więc prawdopodobnie lepiej jest użyć prostego, powolnego algorytmu i zrobić to dobrze niż użyć złożonego, szybkiego algorytmu i przekonać się, że jest błyskawiczny ale zawiera błędy i właściwie nie sortuje danych.

$f (n) = O (n^2)$$n_0$$f (n) < c n^2$$n > n_0$

$c n^2$$n^2 + 10^{18}$

Z drugiej strony, jeśli kiedykolwiek spotkasz się z wartościami n = 1, 2 i 3, to w praktyce nie ma znaczenia, co robi f (n) dla n ≥ 4, więc równie dobrze możesz rozważyć, że f ( n) = O (1), przy c = max (f (1), f (2), f (3)). I to właśnie oznacza wystarczająco małe: Jeśli twierdzenie, że f (n) = O (1) nie wprowadza cię w błąd, jeśli jedyne napotkane wartości f (n) są „wystarczająco małe”.

Jeśli nie rośnie, to jest O (1)

Oświadczenie autora jest nieco aksjomatyczne.

Porządki wzrostu opisują, co dzieje się z ilością pracy, którą należy wykonać w miarę Nwzrostu. Jeśli wiesz, że Nto się nie zwiększa, Twój problem jest skuteczny O(1).

Pamiętaj, że O(1)to nie znaczy „szybko”. Algorytm, który zawsze wymaga ukończenia 1 biliona kroków O(1). Algorytm, który zajmuje od 1 do 200 kroków, ale nigdy więcej, nie jest O(1). [1]

Jeśli twój algorytm wykonuje dokładnie N ^ 3kroki i wiesz, że Nnie może być więcej niż 5, nigdy nie może wykonać więcej niż 125 kroków, więc jest efektywny O(1).

Ale znowu O(1)niekoniecznie oznacza „wystarczająco szybko”. To osobne pytanie zależy od twojego kontekstu. Jeśli ukończenie czegoś zajmie tydzień, prawdopodobnie nie obchodzi cię, czy to technicznie O(1).

[1] Np. Wyszukiwanie w haszu ma miejsce O(1), mimo że kolizje hasza oznaczają, że będziesz musiał przejrzeć kilka przedmiotów w jednym wiadrze, o ile istnieje sztywny limit liczby przedmiotów w tym wiadrze.

Teraz mogę używać tablicy hashtable i wyszukiwać O (1) (pomijając konkretną implementację tablicy hasht), ale gdybym miał np. Listę, miałbym O (n) wyszukiwania. Biorąc pod uwagę ten aksjomat, te dwa są takie same, jeśli zbiory są wystarczająco małe. Ale w pewnym momencie się rozchodzą ... o co chodzi?

Praktycznie jest to punkt, w którym budowanie tabeli skrótów wymaga więcej niż korzyści, które zyskujesz dzięki ulepszonym przeglądom. Różni się to znacznie w zależności od tego, jak często wykonujesz wyszukiwanie, a jak często robisz inne rzeczy. O (1) vs O (10) nie jest wielką rzeczą, jeśli zrobisz to raz. Jeśli zrobisz to tysiące razy na sekundę, nawet to ma znaczenie (chociaż przynajmniej ma to znaczenie w liniowo rosnącym tempie).

Chociaż cytat jest prawdziwy (ale niejasny), istnieją również zagrożenia. Imo powinieneś spojrzeć na złożoność na każdym etapie aplikacji.

Zbyt łatwo jest powiedzieć: hej, mam tylko małą listę, jeśli chcę sprawdzić, czy pozycja A jest na liście, po prostu napiszę łatwą pętlę, aby przejrzeć listę i porównać elementy.

Wtedy twój buddyprogrammer musi użyć listy, widzi twoją funkcję i wygląda tak: hej, nie chcę żadnych duplikatów na liście, więc używa funkcji dla każdego elementu dodanego do listy.

(uwaga, wciąż jest to scenariusz z małą listą).

3 lata później przychodzę i mój szef właśnie dokonał dużej sprzedaży: nasze oprogramowanie będzie używane przez dużego krajowego sprzedawcę. Wcześniej serwisowaliśmy tylko małe sklepy. A teraz mój szef rzuca się na mnie, przeklinając i krzycząc, dlaczego oprogramowanie, które zawsze „działało dobrze”, teraz jest tak strasznie wolne.

Okazuje się, że ta lista była listą klientów, a nasi klienci mieli może około 100 klientów, więc nikt tego nie zauważył. Operacja zapełniania listy była w zasadzie operacją O (1), ponieważ zajęła mniej niż milisekundę. Cóż, nie tak bardzo, gdy można do niego dodać 10.000 klientów.

A lata po pierwotnej złej decyzji O (1) firma prawie straciła dużego klienta. Wszystko z powodu jednego małego błędu w projekcie / założeniu sprzed lat.

Motywacja do tego jest oparta na błędnym założeniu, że O (1) jest zawsze lepsze niż O (lg n), zawsze jest lepsze niż O (n). Asymptotyczna kolejność operacji jest istotna tylko wtedy, gdy w realistycznych warunkach rozmiar problemu staje się naprawdę duży.

Jeśli mam dwa algorytmy z tymi czasami:

• log (n) +10000
• n + 1

Następnie istnieje punkt, w którym krzyżują się. Dla nmniejszych algorytm „liniowy” jest szybszy, a dla nwiększych algorytm „logarytmiczny” jest szybszy. Wiele osób popełnia błąd, zakładając, że algorytm logarytmiczny jest szybszy, ale dla małych ntak nie jest.

Jeśli n pozostaje małe, to każdy problem to O (1)!

I spekulują, co oznaczało, tutaj jest to, że jeśli njest ograniczony, to każdy problem jest O (1). Na przykład, jeśli sortujemy liczby całkowite, możemy zdecydować się na użycie szybkiego sortowania. O(n*log(n))oczywiście. Ale jeśli zdecydujemy, że nie może być więcej niż 2^64=1.8446744e+19liczb całkowitych, wówczas wiemy, że n*log(n)<= 1.8446744e+19*log(1.8446744e+19)<= 1.1805916e+21. Dlatego algorytm zawsze zajmuje mniej niż 1.1805916e+21„jednostki czasu”. Ponieważ jest to stały czas, możemy powiedzieć, że algorytm można zawsze wykonać w tym stałym czasie -> O(1). (Pamiętaj, że nawet jeśli te jednostki czasu są nanosekundami, to łącznie ponad 37411 lat). Ale nadal O(1).

Podejrzewam, że w wielu z tych odpowiedzi brakuje podstawowej koncepcji. O (1): O (n) nie jest tym samym co f (1): f (n) gdzie f jest tą samą funkcją, ponieważ O nie reprezentuje pojedynczej funkcji. Nawet ładny wykres Schwern nie jest prawidłowy, ponieważ ma tę samą oś Y dla wszystkich linii. Aby wszyscy używali tej samej osi, linie musiałyby być fn1, fn2 i fn3, przy czym każda z nich była funkcją, której wydajność można bezpośrednio porównać z innymi.

Słyszałem kilka razy, że dla wystarczająco małych wartości n, O (n) można myśleć / traktować tak, jakby to było O (1)

Cóż, jeśli n = 1, czy są dokładnie takie same? Nie. Funkcja zezwalająca na zmienną liczbę iteracji nie ma nic wspólnego z tą, która tego nie robi, notacja Big-O nie ma znaczenia i my też nie powinniśmy.

Notacja Big-O jest po prostu po to, aby wyrazić, co dzieje się, gdy mamy proces iteracyjny, oraz w jaki sposób wydajność (czas lub zasoby) ulegnie pogorszeniu wraz ze wzrostem „n”.

Tak więc, aby odpowiedzieć na pytanie ... Powiedziałbym, że ci, którzy twierdzą, że twierdzą, nie rozumieją właściwie notacji Big-O, ponieważ jest to nielogiczne porównanie.

Oto podobne pytanie: jeśli przejdę przez ciąg znaków i wiem, że ogólnie moje ciągi będą miały mniej niż 10 znaków, czy mogę powiedzieć, że jest to odpowiednik O (1), ale jeśli moje ciągi byłyby dłuższe, to ja powiedziałbym, że to O (n)?

Nie, ponieważ ciąg 10 znaków zajmuje 10 razy więcej niż ciąg 1 znaku, ale 100 razy mniej niż ciąg 1000 znaków! Włączone).

Uważam, że cytowany tekst jest dość niedokładny (użycie słowa „lepiej” jest zwykle bez znaczenia, chyba że podasz kontekst: pod względem czasu, miejsca itp.) W każdym razie uważam, że najprostszym wyjaśnieniem byłoby:

$O(1)$$O(1)$

Teraz weźmy stosunkowo niewielki zestaw 10 elementów i mamy kilka algorytmów, aby go posortować (tylko przykład). Załóżmy, że utrzymujemy elementy w strukturze, która również zapewnia nam algorytm zdolny do sortowania elementów w stałym czasie. Powiedzmy, że nasze algorytmy sortowania mogą mieć następujące złożoności (z notacją big-O):

1. $O(1)$
2. $O(n)$
3. $O(nlog(n))$
4. $O(n^2)$

$O(1)$

Teraz „ujawnijmy” prawdziwe złożoności wspomnianych wyżej algorytmów sortowania (gdzie „prawda” oznacza nie ukrywanie stałej), reprezentowane przez liczbę kroków wymaganych do ukończenia (i zakładamy, że wszystkie kroki zajmują tyle samo czasu):

1. $200$
2. $11n$
3. $4nlog(n)$
4. $1n^2$

Jeśli nasze dane wejściowe mają rozmiar 10, to są to dokładne kroki dla każdego algorytmu wymienionego powyżej:

1. $200$
2. $11 \times 10 = 110$
3. $4 \times 10 \times 3.32 \approx 134$
4. $1 \times 100 = 100$

$O(n^2)$$O(1), O(n)$$O(nlog(n))$$O(n^2)$$O(1)$$O(n^2)$$O(1)$