26

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

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

asymptotics

— rianjs
źródło

4

Zasada praktyczna zależy od tego, który problem chcesz rozwiązać. Być szybki w systemach wbudowanych z ? Publikować w teorii złożoności?

n \leq 100

$n \leq 100$

— Raphael

3

Myśląc o tym więcej, wydaje się, że nie ma jednej praktycznej zasady, ponieważ wymagania dotyczące wydajności zależą od domeny i wymagań biznesowych. W środowiskach nieobsługujących zasobów n może być dość duże. W mocno ograniczonych środowiskach może być dość mały. Z perspektywy czasu wydaje się to oczywiste.

— rianjs

12

@rianjs Wydaje się, że mylisz się O(1)za darmo . Uzasadnienie kilku pierwszych zdań O(1)jest stałe , co czasem może być niesamowicie powolne. Obliczenie, które trwa tysiąc miliardów lat bez względu na wkład, jest O(1)obliczeniem.

— Mooing Duck,

1

Podobne pytanie dotyczące tego, dlaczego przede wszystkim używamy asymptotyków.

— Raphael

3

@rianjs: bądź świadomy żartów w stylu „pięciokąt jest w przybliżeniu kołem, dla wystarczająco dużych wartości 5”. Zdanie, o które pytasz, ma sens, ale ponieważ spowodowało to pewne zamieszanie, warto poświęcić chwilę pytając Erica Lipperta, w jakim stopniu ten dokładny wybór frazowania miał humorystyczny efekt. Mógłby powiedzieć: „jeśli istnieje górna granica wówczas każdy problem ma wartość ” i nadal jest matematycznie poprawny. „Mały” nie jest częścią matematyki.

n

$n$

O (1)

$O(1)$

— Steve Jessop,

21

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.

wprowadź opis zdjęcia tutaj

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$
$O(n)$ to tak naprawdę , gdzie określa kąt. $C \times n$ $C$
$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. $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(\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.

— Schwern
źródło

Nie ma sensu mówić . To, co naprawdę masz na myśli, to to, że jeśli czas działania wynosi to (w wielu przypadkach) .Jeśli to w wielu przypadkach lub bardziej formalnie . I tak dalej. Należy jednak zauważyć, że w innych przypadkach stała zmienia się w granicach , w pewnych granicach.

O (1) = O (C)

$O(1) = O(C)$

T = O (1)

$T = O(1)$

T \approx C

$T \approx C$

T = O (n)

$T = O(n)$

T \approx C n

$T \approx Cn$

T = C n + o (n)

$T = Cn + o(n)$

C

$C$

n

$n$

— Yuval Filmus

@YuvalFilmus Właśnie dlatego lubię wykresy.

— Schwern

To jak dotąd najlepsza odpowiedź, chodzi o to, jak szybko rośnie funkcja.

— Ricardo

1

Niezły wykres, ale oś naprawdę powinna być oznaczona jako „czas”, a nie „prędkość”.

y

$y$

— Ilmari Karonen,

1

Czy linia naprawdę parabolą? Wygląda bardzo płasko dla małych i bardzo strome dla dużych .

O (n^{2})

$O(n^2)$

n

$n$

n

$n$

— David Richerby,

44

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.

— Eric Hughes
źródło

5

„W przypadku małej liczby n korzystaj z wszystkiego, co jest wygodne.” - jeśli często wykonujesz operację , wybierz najszybszą (dla twojego ). Zobacz także tutaj .

n

$n$

— Raphael

4

Wielka metafora!

— Evorlor,

1

Z czysto matematycznego punktu widzenia asymptotyczna złożoność nic nie mówi, kiedy n < infinity.

— Gordon Gustafson,

15

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 etapy, na pewnej stałej . Oznacza to, że istnieje pewna stała taka, że dla wszystkich algorytm wykonuje z grubsza kroków. Ale może $\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 , 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 ), 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, a nawet 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$ $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.

— David Richerby
źródło

4

O (n)

$O(n)$

O (1)

$O(1)$

n

$n$

10 n + 50

$10n + 50$

100000

$100000$

n

$n$

O (n)

$O(n)$

@RanG. Czy to nie wchodzi w zakres mojej drugiej sprawy? (Zwłaszcza jeśli go edytuję, aby powiedzieć coś więcej jak „Algorytm liniowy z dobrymi stałymi może pobić algorytm stały / logarytmiczny ze złymi stałymi”?)

— David Richerby,

1

Dobrze byłoby wyraźnie wspomnieć o znaczeniu stałych, gdy n jest małe. Jest to coś, co prawdopodobnie nie przydarzy się komuś, kto wcześniej tego nie słyszał.

— Rob Watts

9

$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”.

— gnasher729
źródło

5

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.

— Nathan Long
źródło

1

To wszystko brzmi poprawnie, z wyjątkiem tego: „Jeśli twój algorytm wykonuje dokładnie N ^ 3 kroków i wiesz, że N nie może być większy niż 5, nigdy nie może zająć więcej niż 125 kroków, więc jest to O (1).” . Ponownie, jeśli algorytm przyjmuje liczbę całkowitą, a moja maksymalna obsługa liczb całkowitych wynosi 32767, to czy jest to O (1)? Oczywiście, że nie. Big-O nie zmienia się w zależności od limitów parametrów. Jest to O (n), nawet jeśli wiesz, że 0 <n <3, ponieważ n = 2 zajmuje dwa razy więcej niż n = 1.

— JSobell,

3

@JSobell Ale to jest O (1). Jeśli istnieje ograniczenie, które ogranicza twoje n dla f (n), oznacza to, że nie może rosnąć w nieskończoność. Jeśli twoje n jest ograniczone przez 2 ^ 15, twoja wielka funkcja n ^ 2 jest faktycznie g(n) = min(f(2^15), f(n))- która jest w O (1). To powiedziawszy w praktyce stałe mają duże znaczenie i wyraźnie n może stać się na tyle duże, że przydatna jest analiza asymptotyczna.

— Voo,

2

@JSobell Jest to podobne do pytania, czy komputery są naprawdę „Turing Complete”, biorąc pod uwagę, że technicznie nie mogą mieć nieskończonej przestrzeni dyskowej. Technicznie, matematycznie, komputer nie jest „prawdziwą” maszyną Turinga. W praktyce nie ma czegoś takiego jak „nieskończona taśma”, ale dyski twarde są wystarczająco blisko.

— Kyle Strand,

Kilka lat temu napisałem system ryzyka finansowego, który obejmował manipulacje matrycą n ^ 5, więc miał praktyczny limit n = 20, zanim zasoby stały się problemem.

— JSobell,

Przepraszam, nacisnąłem Enter zbyt wcześnie. Kilka lat temu napisałem system ryzyka finansowego, który obejmował manipulacje matrycą n ^ 5, więc miał praktyczny limit n = 20, zanim zasoby stały się problemem. Zgodnie z tą wadliwą logiką, utworzoną funkcją jest O (1), ponieważ mam granicę 20. Gdy klient mówi „Hmm, być może powinniśmy przenieść ją na 40 jako limit ... Tak, algorytmem jest O (1) ), więc nie ma problemu ”... To dlatego ograniczenia na wejściu są bez znaczenia. Funkcją była O (n ^ 5), a nie O (1), i jest to praktyczny przykład tego, dlaczego Big-O jest niezależny od granic.

— JSobell,

2

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

— Telastyn
źródło

Jeśli chcesz mieć pewność, wykonaj eksperymenty, aby zobaczyć, która struktura danych jest lepsza dla Twoich parametrów.

— Yuval Filmus

@Telastyn Yuval Filmus ma rację, jeśli naprawdę chcesz być pewien. Znam osobę imieniem Jim, jego parametry są w porządku. Ale nie słuchał rad takich jak Yuval. Naprawdę powinieneś słuchać Yuvala, aby mieć pewność i bezpieczeństwo.

— InformedA

2

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.

— Pieter B.
źródło

Ale ilustruje również ważną cechę wielu systemów w świecie rzeczywistym: „algorytmy”, których uczysz się jako licencjat, są tak naprawdę elementami, z których powstają prawdziwe „algorytmy”. Zazwyczaj jest to wskazane; na przykład większość ludzi wie, że szybkie sortowanie jest często zapisywane w celu powrotu do sortowania wstawianego, gdy partycje stają się wystarczająco małe, i że wyszukiwanie binarne jest często zapisywane w celu powrotu do wyszukiwania liniowego. Ale niewiele osób zdaje sobie sprawę z tego, że sortowanie scalone może skorzystać z wyszukiwania binarnego.

— pseudonim

1

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

— Mucząca Kaczka
źródło

0

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

— JSobell
źródło

O (1)

$O(1)$

f (i)

$f(i)$

i

$i$

max {f (0), \dots, f (10)}

$\max\,\{f(0), \dots, f(10)\}$

O (1)

$O(1)$

Tak, i jest to przykład, w którym notacja Big-O jest często źle rozumiana. Według twojego argumentu, jeśli wiem, że maksymalna wartość n wynosi 1 000 000, to moją funkcją jest O (1). W rzeczywistości moją funkcją może być w najlepszym wypadku O (1), aw najgorszym O (n). Notacja ta jest używana do opisania złożoności algorytmicznej, a nie konkretnej implementacji, i zawsze używamy najdroższej do opisu scenariusza, a nie najlepszej. W rzeczywistości, według twojego argumentu, każda pojedyncza funkcja, która pozwala n <2, to O (1)! :)

— JSobell,

n < 2

$n<2$

O (1)

$O(1)$

f (n) \leq f (10)

$f(n)\leq f(10)$

n

$n$

O (1)

$O(1)$

Przepraszamy, ale jeśli powiesz, że znajomość górnych granic n tworzy funkcję O (1), oznacza to, że reprezentacja notacyjna jest bezpośrednio związana z wartością n, a nie jest. Wszystko, co wspominasz, jest poprawne, ale sugerowanie, że ponieważ n ma granice, to O (1) jest niepoprawne. W praktyce są miejsca, w których można opisać to, co opisujesz, ale przyglądamy się tutaj notacji Big-O, a nie kodowaniu funkcjonalnemu. Więc ponownie, dlaczego sugerujesz, że n mając maksimum 10 sprawiłoby, że O (1)? Dlaczego 10 Dlaczego nie 65535 lub 2 ^ 64?

— JSobell,

Powiedziawszy to, jeśli napiszesz funkcję, która wypakowuje ciąg do 10 znaków, to zawsze zapętla się nad nim, to jest to O (1), ponieważ n to zawsze 10 :)

— JSobell

0

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

$O(1)$
$O(n)$
$O(nlog(n))$
$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):

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

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

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

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

— 3yakuya
źródło

„W przypadku małych wartości n, O (n) można traktować tak, jakby to było O (1)”

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