Co oznacza „O (1) czas dostępu”?

127

Widziałem, że termin „O (1) czas dostępu” oznaczał „szybko”, ale nie rozumiem, co to znaczy. Innym terminem, który widzę z nim w tym samym kontekście, jest „czas dostępu O (n)”. Czy mógłby ktoś wyjaśnić w prosty sposób, co oznaczają te terminy?

Zobacz też

Społeczność
źródło
To może pomóc: stackoverflow.com/questions/471199/…
Mehrdad Afshari

Odpowiedzi:

161

Będziesz chciał poczytać o kolejności złożoności.

http://en.wikipedia.org/wiki/Big_O_notation

Krótko mówiąc, O (1) oznacza, że ​​zajmuje to stały czas, na przykład 14 nanosekund lub trzy minuty, niezależnie od ilości danych w zestawie.

O (n) oznacza, że ​​potrzeba czasu liniowego w stosunku do rozmiaru zbioru, więc zestaw dwukrotnie większy zajmie dwa razy więcej czasu. Prawdopodobnie nie chcesz umieszczać miliona obiektów w jednym z nich.

Karl
źródło
66
Mówiąc pedantycznie, nie oznacza to, że czas działania (lub liczba operacji itp.) Jest stały. Oznacza to, że istnieje taka stała, że ​​czas wykonania (lub liczba operacji itp.) Jest ograniczony powyżej stałą. Nadal może występować duża rozbieżność w czasie wykonywania: np . int main() { int n; cin >> n; if(n == 0) { sleep(60 * 60 * 24 * 365); } cout << n; }Jest O(1).
jason
Świetny wgląd @jason!
Chris Ruskai
35

Zasadniczo oznacza to, że wyszukanie wartości w kolekcji zajmuje tyle samo czasu, niezależnie od tego, czy masz małą liczbę elementów w swojej kolekcji, czy bardzo wiele (w ramach ograniczeń twojego sprzętu)

O (n) oznaczałoby, że czas potrzebny na wyszukanie elementu jest proporcjonalny do liczby elementów w kolekcji.

Typowymi przykładami tego typu są tablice, do których można uzyskać bezpośredni dostęp, niezależnie od ich rozmiaru, oraz połączone listy, przez które należy przejść od początku, aby uzyskać dostęp do danego elementu.

Inną zwykle omawianą operacją jest wstawianie. Zbiór może mieć wartość O (1), aby uzyskać dostęp, ale O (n), aby wstawić. W rzeczywistości tablica ma dokładnie takie zachowanie, ponieważ aby wstawić element w środku, musiałbyś przesunąć każdy element w prawo, kopiując go do następnego gniazda.

SingleNegationElimination
źródło
21

Każda odpowiedź aktualnie odpowiadająca na to pytanie mówi, że O(1)oznacza to stały czas (cokolwiek dzieje się z pomiarem; może to być czas działania, liczba operacji itp.). To nie jest dokładne.

Powiedzieć, że środowisko wykonawcze O(1)oznacza, że ​​istnieje stała ctaka, że ​​środowisko wykonawcze jest ograniczone powyżej c, niezależnie od danych wejściowych. Na przykład zwrócenie pierwszego elementu tablicy nliczb całkowitych to O(1):

int firstElement(int *a, int n) {
    return a[0];
}

Ale ta funkcja O(1)też jest :

int identity(int i) {
    if(i == 0) {
        sleep(60 * 60 * 24 * 365);
    }
    return i;
}

W tym przypadku czas wykonywania jest ograniczony powyżej 1 roku, ale w większości przypadków jest on rzędu nanosekund.

Powiedzenie, że środowisko wykonawcze O(n)oznacza, że ​​istnieje taka stała c, że czas wykonania jest ograniczony powyżej c * n, gdzie nmierzy rozmiar danych wejściowych. Na przykład znalezienie liczby wystąpień określonej liczby całkowitej w nieposortowanej tablicy nliczb całkowitych za pomocą następującego algorytmu to O(n):

int count(int *a, int n, int item) {
    int c = 0;
    for(int i = 0; i < n; i++) {
        if(a[i] == item) c++;
    }
    return c;
}

Dzieje się tak, ponieważ musimy iterować po tablicy, sprawdzając każdy element po kolei.

Jason
źródło
19

O (1) oznacza, że ​​czas uzyskania dostępu do czegoś jest niezależny od liczby elementów w kolekcji.

O (N) oznaczałoby, że czas uzyskania dostępu do elementu jest proporcjonalny do liczby (N) elementów w kolekcji.

Rob Walker
źródło
14

O (1) niekoniecznie oznacza „szybko”. Oznacza to, że czas potrzebny jest stały i nie zależy od rozmiaru danych wejściowych do funkcji. Stała może być szybka lub wolna. O (n) oznacza, że ​​czas potrzebny funkcji zmieni się wprost proporcjonalnie do rozmiaru wejścia do funkcji, oznaczonego przez n. Ponownie, może to być szybkie lub wolne, ale będzie wolniejsze wraz ze wzrostem rozmiaru n.

Bill the Lizard
źródło
9

Nazywa się notacją Big O i opisuje czas wyszukiwania różnych algorytmów.

O (1) oznacza, że ​​czas pracy w najgorszym przypadku jest stały. W większości sytuacji oznacza to, że właściwie nie musisz przeszukiwać kolekcji, możesz od razu znaleźć to, czego szukasz.

alexn
źródło
Zamień „czas wyszukiwania” na „najgorszy czas wykonania” i jestem z tobą.
Jason Punyon
2
@Seb: Myślę, że to była po prostu błędna nazwa z jego strony, szczególnie dlatego, że OP zapytał o czas dostępu.
jkeys
6

O(1)zawsze wykonywane w tym samym czasie, niezależnie od zbioru danych n. Przykładem O (1) byłaby ArrayList uzyskująca dostęp do swojego elementu z indeksem.

O(n)znany również jako Linear Order, wydajność będzie rosnąć liniowo i wprost proporcjonalnie do rozmiaru danych wejściowych. Przykładem O (n) byłoby wstawienie i usunięcie ArrayList w losowej pozycji. Ponieważ każde kolejne wstawienie / usunięcie w losowej pozycji spowoduje przesunięcie elementów tablicy ArrayList w lewo w prawo w celu zachowania jej struktury liniowej, nie wspominając o tworzeniu nowych tablic i kopiowaniu elementów ze starej do nowej macierzy, która zajmuje kosztowny czas przetwarzania, a zatem obniża wydajność.

leCodera
źródło
4

„Notacja Big O” to sposób na wyrażenie szybkości algorytmów. nto ilość danych, z którymi pracuje algorytm. O(1)oznacza, że ​​bez względu na ilość danych będzie wykonywany w stałym czasie. O(n)oznacza, że ​​jest proporcjonalna do ilości danych.

Zifre
źródło
3

Zasadniczo O (1) oznacza, że ​​jego czas obliczeń jest stały, natomiast O (n) oznacza, że ​​będzie zależał liniowo od rozmiaru wejścia - tj. Pętla przez tablicę ma O (n) - po prostu zapętlanie - ponieważ zależy to od liczby przedmiotów, podczas obliczania maksimum między liczbami zwykłymi ma O (1).

Wikipedia też może pomóc: http://en.wikipedia.org/wiki/Computational_complexity_theory

Seb
źródło
3

Najłatwiejszym sposobem rozróżnienia O (1) i O (n) jest porównanie tablicy i listy.

W przypadku tablicy, jeśli masz odpowiednią wartość indeksu, możesz natychmiast uzyskać dostęp do danych. (Jeśli nie znasz indeksu i musisz zapętlić tablicę, to nie będzie już O (1))

W przypadku listy zawsze musisz ją przeglądać, niezależnie od tego, czy znasz indeks, czy nie.

codingbear
źródło
Szukałem przykładu O (1) i tylko ta odpowiedź ma wyjaśnienie.
neelmeg
3

Oto prosta analogia; Wyobraź sobie, że pobierasz filmy online, z O (1), jeśli pobranie jednego filmu zajmie 5 minut, pobranie 20 filmów będzie nadal trwać tak samo. Nie ma więc znaczenia, ile filmów pobierasz, zajmie to tyle samo czasu (5 minut), czy jest to jeden, czy 20 filmów. Normalnym przykładem tej analogii jest to, że kiedy idziesz do biblioteki filmów, niezależnie od tego, czy robisz jeden film, czy pięć, po prostu wybierzesz je na raz. Stąd spędzanie tego samego czasu.

Jednak przy O (n), jeśli pobranie jednego filmu zajmie 5 minut, pobranie 10 filmów zajmie około 50 minut. Zatem czas nie jest stały lub jest w jakiś sposób proporcjonalny do liczby pobieranych filmów.

Ambroze kweronda
źródło
1

Oznacza to, że czas dostępu jest stały. Niezależnie od tego, czy uzyskujesz dostęp ze 100, czy 100 000 rekordów, czas pobierania będzie taki sam.

Natomiast czas dostępu O (n) wskazywałby, że czas pobierania jest wprost proporcjonalny do liczby rekordów, z których uzyskujesz dostęp.

Rob Hruska
źródło
1

Oznacza to, że dostęp zajmuje stały czas, tj. Nie zależy od rozmiaru zbioru danych. O (n) oznacza, że ​​dostęp będzie zależał od rozmiaru zbioru danych w sposób liniowy.

O jest również znane jako duże O.

dirkgently
źródło
1

Wstęp do algorytmów: wydanie drugie autorstwa Cormena, Leisersona, Rivesta i Stein mówi, że na stronie 44

Ponieważ każda stała jest wielomianem stopnia-0, możemy wyrazić dowolną stałą funkcję jako Theta (n ^ 0) lub Theta (1). Ta ostatnia notacja jest jednak niewielkim nadużyciem, ponieważ nie jest jasne, jaka zmienna zmierza do nieskończoności. Będziemy często używać notacji Theta (1) do oznaczenia stałej lub stałej funkcji w odniesieniu do jakiejś zmiennej. ... oznaczymy przez O (g (n)) ... zbiór funkcji f (n) taki, że istnieją dodatnie stałe c i n0 takie, że 0 <= f (n) <= c * g (n) dla wszystkich n> = n0. ... Zauważ, że f (n) = Theta (g (n)) implikuje f (n) = O (g (n)), ponieważ notacja Theta jest silniejsza niż notacja O.

Jeśli algorytm działa w czasie O (1), oznacza to, że asymptotycznie nie zależy od żadnej zmiennej, co oznacza, że ​​istnieje co najmniej jedna dodatnia stała, która po pomnożeniu przez jeden jest większa niż asymptotyczna złożoność (~ runtime) funkcji dla wartości n powyżej określonej kwoty. Technicznie rzecz biorąc, jest to czas O (n ^ 0).

P. Myer Nore
źródło
-2

O (1) oznacza Random Access. W każdej pamięci o dostępie swobodnym czas potrzebny na dostęp do dowolnego elementu w dowolnej lokalizacji jest taki sam. Tutaj czas może być dowolną liczbą całkowitą, ale jedyną rzeczą do zapamiętania jest czas potrzebny do pobrania elementu w (n-1)-tym lub n-tym miejscu będzie taki sam (tj. Stały).

Natomiast O (n) zależy od wielkości n.

Basant
źródło
Nie ma to nic wspólnego z losowym dostępem - zobacz zaakceptowaną odpowiedź opublikowaną prawie rok przed tą odpowiedzią, aby uzyskać więcej informacji
Krease
-3

Według mojej perspektywy

O (1) oznacza, że ​​czas wykonania jednej operacji lub instrukcji na raz to jeden, w najlepszym przypadku analiza złożoności algorytmu.

amarjeet
źródło
6
Próbuj dalej. To konkretne pytanie wymaga nie tylko perspektywy, ale jasnej definicji.
Alfabravo