Przykłady algorytmów o złożoności O (1), O (n log n) i O (log n)


Odpowiedzi:


234

Jeśli potrzebujesz przykładów algorytmów / grup instrukcji ze złożonością czasową, jak podano w pytaniu, oto mała lista -

O(1) czas

  • Dostęp do indeksu tablicy (int a = ARR [5];)
  • Wstawianie węzła na liście połączonej
  • Pushing and Poping on Stack
  • Wstawianie i usuwanie z kolejki
  • Znalezienie rodzica lub lewego / prawego dziecka węzła w drzewie przechowywanym w Array
  • Przejście do następnego / poprzedniego elementu na liście podwójnie połączonej

O(n) czas

W skrócie, wszystkie algorytmy Brute Force lub Noob, które wymagają liniowości, są oparte na złożoności czasowej O (n)

  • Przechodzenie przez tablicę
  • Przechodzenie przez połączoną listę
  • Wyszukiwanie liniowe
  • Usunięcie określonego elementu z listy połączonej (niesortowane)
  • Porównanie dwóch strun
  • Sprawdzam palindrom
  • Liczenie / Sortowanie kubełkowe i tutaj również można znaleźć milion innych takich przykładów ...

O(log n) czas

  • Wyszukiwanie binarne
  • Znajdowanie największej / najmniejszej liczby w drzewie wyszukiwania binarnego
  • Pewne algorytmy dzielenia i zwyciężania oparte na funkcjonalności liniowej
  • Obliczanie liczb Fibonacciego - najlepsza metoda Podstawowym założeniem tutaj jest NIEUŻYWANIE pełnych danych i zmniejszanie rozmiaru problemu z każdą iteracją

O(n log n) czas

Współczynnik „log n” jest wprowadzany poprzez uwzględnienie Dziel i rządź. Niektóre z tych algorytmów są najlepiej zoptymalizowane i często używane.

  • Merge Sort
  • Sortowanie na stosie
  • Szybkie sortowanie
  • Pewne algorytmy dzielenia i zwyciężania oparte na algorytmach optymalizacji O (n ^ 2)

O(n^2) czas

Te algorytmy mają być mniej wydajnymi algorytmami, jeśli ich odpowiedniki O (nlogn) są obecne. Ogólnym zastosowaniem może być tutaj Brute Force.

  • Sortowanie bąbelkowe
  • Sortowanie przez wstawianie
  • Sortowanie przez wybór
  • Przechodzenie przez prostą tablicę 2D

5
A co z n !? Zastanawiałem się, jaki typowy algorytm używa n !?
Y_Y

Dostęp do wartości HashMap, a także bardziej złożonych algorytmów, takich jak implementacja LRU, która osiąga O (1) za pomocą HashMap i podwójnie połączonej listy lub implementując stos z funkcjonalnością PUSH / POP / MIN. Również rekurencyjna implementacja Fibonacciego należy do N !.
ruralcoder

11
Mój OCD chce, abyś zmienił O(log n)listę tak, aby znajdowała się przed O(n)listą, aby lista była uporządkowana od najlepszej do najgorszej. haha :)
Sam Eaton

4
Przechodzenie przez tablicę 2D to w rzeczywistości O (nxm), chyba że jest to macierz kwadratowa.
Simon Peck

1
Problem „komiwojażera” jest przykładem n! (silnia n) również
Ju66ernaut

28

Prostym przykładem O(1)może być return 23;- niezależnie od danych wejściowych, to powróci w ustalonym, skończonym czasie.

Typowym przykładem O(N log N)byłoby sortowanie tablicy wejściowej za pomocą dobrego algorytmu (np. Scalanie).

Typowy przykład, jeśli O(log N)szukałby wartości w posortowanej tablicy wejściowej przez podział na pół.


28

O (1) - większość procedur gotowania to O (1), co oznacza, że ​​zajmuje to stałą ilość czasu, nawet jeśli jest więcej osób do gotowania (do pewnego stopnia, ponieważ może zabraknąć miejsca w garnku / patelniach) i trzeba podzielić gotowanie)

O (logn) - znajdowanie czegoś w książce telefonicznej. Pomyśl o wyszukiwaniu binarnym.

O (n) - czytanie książki, gdzie n to liczba stron. Jest to minimalny czas potrzebny na przeczytanie książki.

O (nlogn) - nie mogę od razu pomyśleć o czymś, co można by zrobić codziennie, czyli o nlogn ... chyba że posortujesz karty za pomocą scalania lub szybkiego sortowania!


2
Pieczeń trwa o wiele dłużej niż mini pieczeń :-)
paxdiablo

4
ale zazwyczaj gotowanie dwóch małych pieczeni w porównaniu z jedną małą pieczeńką zajmuje tyle samo czasu, pod warunkiem, że piekarnik jest wystarczająco duży, aby się w nim zmieścić!
Chii

1
Bardzo wnikliwy! Przypuszczam zadanie sporządzania książkę telefoniczną lub adres z listy nazw / numerów może być O (n log n)
squashed.bugaboo

10

Mogę zaoferować kilka ogólnych algorytmów ...

  • O (1): Dostęp do elementu w tablicy (tj. Int i = a [9])
  • O (n log n): szybkie lub łączone (średnio)
  • O (log n): wyszukiwanie binarne

To byłyby intuicyjne odpowiedzi, ponieważ brzmi to jak zadanie domowe / pytanie typu wywiad. Jeśli szukasz czegoś bardziej konkretnego, jest to trochę trudniejsze, ponieważ ogół społeczeństwa nie miałby pojęcia o podstawowej implementacji (oczywiście oszczędzającej otwarte oprogramowanie) popularnej aplikacji, ani też pojęcie to nie odnosi się ogólnie do „aplikacji”


4

O (1): znalezienie najlepszego następnego ruchu w szachach (lub Go w tej kwestii). Ponieważ liczba stanów gry jest skończona, to tylko O ​​(1) :-)


5
Tak, zwykle można zamienić czas na miejsce. Zrobiłem to dla gry w kółko i krzyżyk, ponieważ są tylko 3 ^ 9 stanów (mniej, jeśli inteligentnie obsługujesz obroty). Szachy mają jednak nieco większą liczbę stanów :-)
paxdiablo

1
Problem w tym, że będę żył tylko O(1)nanosekundy, a ty na pewno wiesz, co O(1)wydarzy się pierwsze ...
zardav

3

Złożoność aplikacji nie jest mierzona i nie jest zapisywana w notacji duże-O. Przydatne jest tylko mierzenie złożoności algorytmów i porównywanie algorytmów w tej samej dziedzinie. Najprawdopodobniej gdy mówimy O (n), mamy na myśli „O (n) porównań ” lub „O (n) operacje arytmetyczne”. Oznacza to, że nie można porównywać żadnej pary algorytmów ani aplikacji.


1
To nie do końca prawda. Jeśli algorytm ma złożoność czasową O (N), oznacza to, że jego czas wykonania jest ograniczony k * N kroków dla pewnej stałej k. Nie jest naprawdę ważne, czy „kroki” są cyklami procesora, instrukcjami asemblacji czy (prostymi) operacjami w C. Te szczegóły ukrywa stała k.
Igor Ostrovsky

Nie wspominając już o tym, że w wielu praktycznych przypadkach algorytm „c” algorytmu O (logN) czyni go gorszym niż prostszy algorytm O (N).
Zed

Haha, tak, a przez N mamy na myśli długość danych wejściowych na taśmie maszyny Turinga - co sprawia, że ​​pionowa forma podziału wymaga czasu wykładniczego. :-) Każda domena ma własne wymagania i własny obszar abstrakcji.
P Shved

3

O (1) - Usuwanie elementu z podwójnie połączonej listy. na przykład

typedef struct _node {
    struct _node *next;
    struct _node *prev;
    int data;
} node;


void delete(node **head, node *to_delete)
{
    .
    .
    .
}

2

Do swojej listy możesz dodać następujące algorytmy:

O(1)- Określanie, czy liczba jest parzysta czy nieparzysta; Praca z HashMap

O(logN) - obliczanie x ^ N,

O(N Log N) - Najdłuższy ciąg narastający


1

O (n log n) jest słynnym górnym ograniczeniem szybkości sortowania dowolnego zbioru (przy założeniu standardowego i niezbyt równoległego modelu obliczeniowego).


0

0 (logn) -Wyszukiwanie binarne, element szczytowy w tablicy (może być więcej niż jeden pik) 0 (1) -in python obliczający długość listy lub łańcucha. Funkcja len () zajmuje 0 (1) czasu. Dostęp do elementu w tablicy zajmuje 0 (1) czasu. Operacja wypychania na stosie zajmuje 0 (1) czasu. 0 (nlogn) -Merge sort. sortowanie w Pythonie zajmuje nlogn czasu. więc kiedy używasz listname.sort (), zajmuje to nlogn czasu.

Uwaga - wyszukiwanie w tablicy skrótów czasami zajmuje więcej niż stały czas z powodu kolizji.


0

O (2 N )

O (2 N ) oznacza algorytm, którego wzrost podwaja się z każdym dodatkiem do zbioru danych wejściowych. Krzywa wzrostu funkcji O (2 N ) jest wykładnicza - zaczyna się bardzo płytko, a następnie rośnie błyskawicznie. Przykładem funkcji O (2 N ) jest rekurencyjne obliczanie liczb Fibonacciego:

int Fibonacci (int number)
{
if (number <= 1) return number;
return Fibonacci(number - 2) + Fibonacci(number - 1);
}

Tower of Hanoibyłby lepszym przykładem.
Ashish Duklan
Korzystając z naszej strony potwierdzasz, że przeczytałeś(-aś) i rozumiesz nasze zasady używania plików cookie i zasady ochrony prywatności.
Licensed under cc by-sa 3.0 with attribution required.