Rząd złożoności to termin używany w informatyce do pomiaru wydajności algorytmu lub programu. Odnosi się do ilości czasu i zasobów wymaganych do rozwiązania problemu lub wykonania zadania. W programowaniu stopień złożoności jest zwykle wyrażany w kategoriach Duże O notacja, która określa górną granicę wymagań czasowych i przestrzennych algorytmu. W tym artykule omówimy porządek złożoności w języku programowania C i jego znaczenie.
alfabet na cyfrę
Kolejność złożoności w języku programowania C:
W programowaniu w języku C stopień złożoności algorytmu zależy od liczby operacji wykonywanych przez program. Na przykład, jeśli mamy tablicę o rozmiarze n i chcemy wyszukać konkretny element w tablicy, stopień złożoności algorytmu będzie zależał od liczby elementów w tablicy. Jeśli wykonamy a Wyszukiwanie liniowe przez tablicę, będzie porządek złożoności NA) , co oznacza, że czas potrzebny na wyszukiwanie elementu będzie rósł liniowo wraz z rozmiarem tablicy. Jeśli użyjemy A Algorytm wyszukiwania binarnego zamiast tego będzie porządek złożoności O(log n) , co oznacza, że czas potrzebny na wyszukiwanie elementu będzie rósł logarytmicznie wraz z rozmiarem tablicy.
Podobnie rząd złożoności innych algorytmów, takich jak Algorytmy sortowania , Algorytmy grafowe , I Algorytmy programowania dynamicznego zależy również od liczby operacji wykonywanych przez program. Rząd złożoności tych algorytmów można wyrazić za pomocą Duże O notacja.
Przyjrzyjmy się niektórym typowym rzędom złożoności i odpowiadającym im algorytmom:
Oznacza to, że algorytm zajmuje stałą ilość czasu, niezależnie od wielkości danych wejściowych. Na przykład dostęp do elementu w tablicy wymaga O(1) czas, ponieważ dostęp do elementu można uzyskać bezpośrednio za pomocą jego indeksu.
Oznacza to, że czas działania algorytmu rośnie logarytmicznie wraz ze wzrostem rozmiaru danych wejściowych. Często można to zobaczyć w Algorytmy dziel i zwyciężaj tak jak Wyszukiwanie binarne , które dzielą dane wejściowe na mniejsze części, aby rozwiązać problem.
oj, w Javie
Oznacza to, że czas działania algorytmu rośnie liniowo wraz z rozmiarem danych wejściowych. Przykładami takich algorytmów są Wyszukiwanie liniowe I Sortowanie bąbelkowe .
Oznacza to, że czas działania algorytmu wzrasta o n pomnożone przez logarytm z n. Przykładami takich algorytmów są Szybkie sortowanie I Sortowanie przez scalanie .
Oznacza to, że czas działania algorytmu rośnie kwadratowo wraz z rozmiarem danych wejściowych. Przykładami takich algorytmów są Sortowanie bąbelkowe I Sortowanie przez wstawianie .
Oznacza to, że czas działania algorytmu podwaja się przy każdym zwiększeniu rozmiaru danych wejściowych. Często można to zobaczyć w Algorytmy rekurencyjne jak Seria Fibonacciego .
Maszyna wirtualna Java
Ważne jest, aby wiedzieć, że stopień złożoności stanowi jedynie górną granicę czasu potrzebnego algorytmowi. Rzeczywisty czas może być znacznie krótszy niż podany, w zależności od danych wejściowych i implementacji algorytmu.
W programowaniu w języku C stopień złożoności algorytmu można określić, analizując kod i zliczając liczbę wykonanych operacji. Na przykład, jeśli mamy pętlę, która iteruje po tablicy o rozmiarze n, złożoność czasowa pętli będzie wynosić NA) . Podobnie, jeśli mamy funkcję rekurencyjną, która wywołuje samą siebie k razy, złożoność czasowa funkcji będzie wynosić O(2^k) .
Aby zoptymalizować wydajność programu, ważne jest, aby wybrać algorytmy o niższym rzędzie złożoności. Na przykład, jeśli musimy posortować tablicę, powinniśmy użyć algorytmu sortowania o niższym stopniu złożoności, np Szybkie sortowanie Lub Sortowanie przez scalanie , zamiast Sortowanie bąbelkowe , który ma wyższy stopień złożoności.
Analizowanie kolejności złożoności:
Aby przeanalizować rząd złożoności algorytmu, musimy określić, jak rośnie czas jego działania lub wykorzystanie przestrzeni wraz ze wzrostem rozmiaru danych wejściowych. Najpopularniejszą metodą jest policzenie liczby podstawowych operacji wykonanych przez algorytm.
porównaj z metodą Java
Operacja podstawowa to operacja, której wykonanie zajmuje stałą ilość czasu, taką jak dodanie dwóch liczb lub uzyskanie dostępu do elementu tablicy. Licząc liczbę podstawowych operacji wykonywanych przez algorytm w funkcji wielkości wejściowej, możemy określić jego stopień złożoności.
Rozważmy na przykład następującą funkcję C, która oblicza sumę pierwszych n liczb całkowitych:
Kod C:
int sum(int n) { int total = 0; for (int i = 1; i <= n; i++) { total +="i;" } return total; < pre> <p>In this function, the loop runs n times, and each iteration performs a constant amount of work (adding i to the total). Therefore, the number of basic operations performed by this algorithm is proportional to n, and its time complexity is <strong>O(n)</strong> .</p> <hr></=>