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ż
Odpowiedzi:
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.
int main() { int n; cin >> n; if(n == 0) { sleep(60 * 60 * 24 * 365); } cout << n; }Jest O(1).
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.
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.
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.
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.
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.
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ść.
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
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.
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.
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.
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.
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).
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.