Big o notacja w strukturze danych: Wszystko, co trzeba wiedzieć

Notacja Big O w strukturze danych służy do określania wydajności algorytmu, czasu potrzebnego do uruchomienia funkcji wraz ze wzrostem danych wejściowych oraz tego, jak dobrze funkcja skaluje się. Pomiar tej wydajności można podzielić na dwie części, a mianowicie złożoność przestrzenną i czasową.

Notacja Big O odnosi się do zapisu matematycznego, który działa jako czynnik ograniczający dowolną funkcję, gdy argument jest bardziej podatny na skłanianie się w kierunku określonej wartości lub nieskończoności. Należy do kategorii notacji matematycznych wymyślonych przez Edmunda Landaua, Paula Bachmanna i innych. Stąd jest to zbiorczo określane jako notacja Bachmanna-Landaua lub notacja asymptotyczna.

Zgodnie z dedukcją matematyczną dwie funkcje, f(n) i g(n) są zdefiniowane na zbiorze liczb dodatnich lub rzeczywistych, które nie są związane. Tutaj g(n) jest ściśle dodatnie dla każdej dużej wartości n. Można to napisać w następujący sposób:

f(n) = O(g(n)) w którym n dąży do nieskończoności (n → ∞)

Jednak w tym przypadku przypuszczenie n do nieskończoności nie jest wyłącznie zdefiniowane, a zatem powyższe wyrażenie można zapisać jako:

f(n) = O(g(n))

Tutaj f i g są niezbędnymi funkcjami, które zaczynają się od dodatnich liczb całkowitych do liczb rzeczywistych, które nie są nieujemne.

Stąd duże wartości n są oznaczane asymptotyką Big O.

Właściwości notacji Big O w strukturze danych

Algorytm Big O w strukturze danych ma sporo obowiązkowo wymaganych właściwości. Wspomniane podstawowe właściwości notacji Big O są następujące:

• Funkcja sumowania:
  Jeśli f(n) = f 1 (n) + f 2 (n) + — + f m (n) oraz f i (n)≤ f i +1(n) ∀ i=1, 2,–, m,
  wtedy O(f(n)) = O(max(f1(n), f2(n), –, fm(n))).
• Funkcja logarytmiczna:
  Jeśli f(n) = logan i g(n)=logbn,
  wtedy O(f(n))=O(g(n))
• Stałe mnożenie:
  Jeśli f(n) = cg(n), to O(f(n)) = O(g(n)) gdzie c jest niezerową stałą.
• Funkcja wielomianu:
  Jeśli f(n) = a0 + a1.n + a2.n2 + — + am.nm,
  wtedy O(f(n)) = O(nm).

Ucz się kursów rozwoju oprogramowania online z najlepszych światowych uniwersytetów. Zdobywaj programy Executive PG, Advanced Certificate Programs lub Masters Programs, aby przyspieszyć swoją karierę.

Poznaj nasze popularne kursy inżynierii oprogramowania

Tutaj, podczas adresowania Big O, każda pojedyncza funkcja dziennika wzrasta podobnie.

Znaczenie notacji Big O w analizie algorytmów w czasie wykonywania

Złożoność najgorszego przypadku czasu działania algorytmu jest wykorzystywana do dokonywania porównań i obliczeń, szczególnie w przypadku analizy wydajności algorytmu. Kolejność O(1), przedstawiona jako Stały czas działania, to najkrótszy czas działania algorytmu – czas, jaki zajmuje algorytm, jest taki sam dla różnych rozmiarów danych wejściowych. Należy zauważyć, że idealnym czasem działania algorytmu jest stały czas działania, co jest bardzo rzadko osiągane, ponieważ czas działania algorytmu zależy od wielkości wejściowej n.

Na przykład:

Jak wspomniano powyżej, wydajność algorytmu w czasie wykonywania zależy głównie od wielkości wejściowej n. Wyjaśnijmy ten fakt za pomocą kilku matematycznych przykładów, aby przeprowadzić analizę runtime algorytmu dla różnych wielkości n:

• n = 20
  log (20) = 2,996;
  20 = 20;
  20 log (20) = 59,9;
  20 2 = 400;
  2 20 = 1084576;
  20! = 2,432902 + 18 18 ;
• n = 10
  log (10) = 1;
  10 = 10;
  10 log (10) = 10;
  10 2 = 100;
  2 10 = 1024;
  10! = 3628800;

Podobnie obliczana jest wydajność algorytmu w czasie wykonywania.

Oto kilka innych algorytmicznych przykładów analizy środowiska uruchomieniowego –

• Jeśli chodzi o wyszukiwanie liniowe, złożoność środowiska wykonawczego wynosi O(n).
• Złożoność środowiska wykonawczego wynosi O(log n) dla wyszukiwania binarnego.
• W przypadku sortowania przez wybór, sortowania bąbelkowego, sortowania kubełkowego, sortowania przez wstawianie złożoność środowiska wykonawczego wynosi O(n^c).
• Jeśli chodzi o algorytmy wykładnicze, takie jak Wieża Hanoi, złożoność środowiska wykonawczego wynosi O(c^n).
• W przypadku Merge SortSort i Heap Sort złożoność środowiska uruchomieniowego wynosi O (n log n).

Jak Big O analizuje złożoność przestrzeni?

Istotnym krokiem jest określenie złożoności zarówno przestrzeni, jak i środowiska wykonawczego dla algorytmu. Dzieje się tak, ponieważ możemy określić czas wykonania algorytmu, analizując wydajność algorytmu w czasie wykonywania i przestrzeń pamięci, którą algorytm zajmuje, analizując złożoność przestrzeni algorytmu. Dlatego, aby zmierzyć złożoność przestrzenną algorytmu, musimy porównać najgorszy przypadek wydajności złożoności przestrzennej algorytmu.

Aby określić złożoność przestrzenną algorytmu, musimy wykonać te dwa zadania:

Zadanie 1: Niezbędne jest zaimplementowanie programu dla konkretnego algorytmu.

Zadanie 2: Niezbędne jest poznanie rozmiaru wejścia n w celu określenia pamięci, jaką każdy element będzie przechowywał.

Te dwa podstawowe zadania muszą zostać wykonane przed obliczeniem złożoności przestrzeni dla algorytmu.

Przykłady algorytmów złożoności przestrzeni

Istnieje wiele przykładów algorytmów o złożoności przestrzennej, niektóre z nich zostały wymienione poniżej w celu lepszego zrozumienia tego typu algorytmu:

• W przypadku sortowania bąbelkowego, liniowego, selekcji, przez wstawianie, sterty i binarnego złożoność przestrzeni wynosi O(1) .
• Złożoność przestrzenna wynosi O(n+k), jeśli chodzi o sortowanie radix .
• Złożoność przestrzeni to O(n) dla szybkiego sortowania.
• Złożoność przestrzenna wynosi O(log n) dla sortowania przez scalanie.

Przykład notacji Big O w C

Faktem jest, że notacja Big O jest używana głównie w informatyce do określania złożoności lub wydajności algorytmu. Ta notacja daje nam możliwość klasyfikowania zachowania algorytmów na podstawie wzrostu wymagań dotyczących przestrzeni pamięci lub czasu wykonania, gdy zakres danych wejściowych staje się duży. Nie jest przeznaczony do przewidywania rzeczywistego użycia pamięci lub czasu wykonania, ale do porównywania algorytmów, a następnie wybierania najlepszego z nich do zadania. Nie jest specyficzny dla języka, ale jest również zaimplementowany w C.

Poniżej znajdziesz algorytm sortowania przez wybór w C, w którym obliczono złożoność najgorszego przypadku (notacja Big O) algorytmu:-

for(int i=0; i<n; i++)

{

int min = i;

for(int j=i; j<n; j++)

{

if(tablica[j]<tablica[min])

min=j;

}

int temp = tablica[i];

tablica[i] = tablica[min];

tablica[min] = temp;

}

Aby przeanalizować algorytm:

• Można już zauważyć, że zakres pętli zewnętrznej for wynosi i < n , co oznacza, że ​​kolejność pętli to O(n).
• Następnie możemy zidentyfikować, że jest to również O(n), ponieważ j < n dla wewnętrznej pętli for.
• Stała jest ignorowana, nawet jeśli średnia wydajność jest znaleziona n/2 dla stałej c. Tak więc kolejność to O(n).
• Po pomnożeniu kolejności pętli wewnętrznej i pętli zewnętrznej uzyskana złożoność środowiska wykonawczego wynosi O(n^2).

Inne algorytmy w C można łatwo zaimplementować, gdzie złożoność można łatwo analizować i określać w podobny sposób.

Wykorzystanie notacji Big O

Istnieją dwa główne obszary, w których stosowana jest notacja Big O:-

• Matematyka : Notacja Big O jest dość powszechnie używana w dziedzinie matematyki do opisania, w jaki sposób szereg skończony ściśle przybliża funkcję, zwłaszcza jeśli chodzi o przypadki rozwinięcia asymptotycznego lub skróconego szeregu Taylora.
• Informatyka: Powszechnie wiadomo, że notacja Big O jest najczęściej używana w dziedzinie informatyki ze względu na jej przydatność w analizie algorytmów

Jednak w obu zastosowaniach funkcja g ( x ) występująca w O (·) jest często wybierana jako możliwie najprostsza, jeśli pominięto warunki niższego rzędu i czynniki stałe.

Istnieją dwa inne zastosowania tej notacji, które są formalnie bliskie, ale stosunkowo różne. Oni są:-

• Nieskończona asymptotyka
• Asymptotyki nieskończenie małe.

Jednak to rozróżnienie nie jest w zasadzie stosowane, tylko w przypadku formalnej definicji „Wielkiego O” jest dokładnie taka sama w obu przypadkach. Jedyną różnicą są granice argumentu funkcji.

Przeczytaj nasze popularne artykuły związane z tworzeniem oprogramowania

Wniosek

Podsumowując, możemy powiedzieć, że Big Data odgrywa integralną rolę w strukturach danych, a posiadanie dogłębnej, wszechstronnej wiedzy na temat notacji Big O to doskonały zestaw umiejętności. Jest bardzo poszukiwany w sektorze pracy i może być potencjalnie doskonałym wyborem na ścieżkę kariery. Zaawansowany program certyfikatów upGrad w Big Data zapewni Ci dźwignię, której potrzebujesz, aby przyspieszyć swoją karierę. Wprowadzi Cię w najwyższe umiejętności zawodowe, takie jak przetwarzanie danych za pomocą PySpark, magazynowanie danych, MapReduce, przetwarzanie Big Data w chmurze AWS, przetwarzanie w czasie rzeczywistym itp.