Które algorytmy, których używamy codziennie, mają złożoność O (1), O (n log n) i O (log n)?

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

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ół.

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!

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”

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

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.

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

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

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

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);
}