Efektywność algorytmu zależy od dwóch parametrów:
- Złożoność czasu
- Złożoność przestrzeni
Złożoność czasowa:
Złożoność czasową definiuje się jako liczbę wykonań określonego zestawu instrukcji, a nie całkowity czas. Dzieje się tak dlatego, że całkowity czas zależy również od czynników zewnętrznych, takich jak używany kompilator, szybkość procesora itp.
Złożoność przestrzeni:
Złożoność przestrzeni to całkowita przestrzeń pamięci wymagana przez program do jego wykonania.
Obydwa są obliczane jako funkcja rozmiaru wejściowego (n). Ważną rzeczą jest to, że pomimo tych parametrów wydajność algorytmu zależy również od Natura I rozmiar the wejście.
Rodzaje złożoności czasowej:
- Najlepsza złożoność czasowa: Zdefiniuj wejście, dla którego algorytm zajmie mniej czasu lub czas minimalny. W najlepszym przypadku oblicz dolną granicę algorytmu. Przykład: W przypadku wyszukiwania liniowego, gdy dane wyszukiwania znajdują się w pierwszej lokalizacji dużych danych, występuje najlepszy przypadek.
- Średnia złożoność czasowa: W przeciętnym przypadku weź wszystkie losowe dane wejściowe i oblicz czas obliczeń dla wszystkich wejść.
Następnie dzielimy to przez całkowitą liczbę wejść. - Najgorsza złożoność czasowa: Zdefiniuj wejście, dla którego algorytm zajmuje dużo czasu lub czas maksymalny. W najgorszym przypadku oblicz górną granicę algorytmu. Przykład: W przypadku wyszukiwania liniowego, gdy dane wyszukiwania znajdują się w ostatniej lokalizacji dużych danych, występuje najgorszy przypadek.
Poniżej znajduje się arkusz skróconej wersji, do którego możesz zajrzeć w ostatniej chwili:
| Algorytm | Złożoność czasu | Złożoność przestrzeni | ||
|---|---|---|---|---|
| To, co najlepsze | Przeciętny | Najgorszy | Najgorszy | |
| Sortowanie przez wybór | NA2) | NA2) | NA2) | O(1) |
| Sortowanie bąbelkowe | NA) | NA2) | NA2) | O(1) |
| Sortowanie przez wstawianie | NA) | NA2) | NA2) | O(1) |
| Sortowanie sterty | O(n log(n)) | O(n log(n)) | O(n log(n)) | O(1) |
| Szybkie sortowanie | O(n log(n)) | O(n log(n)) | NA2) | NA) |
| Sortowanie przez scalanie | O(n log(n)) | O(n log(n)) | O(n log(n)) | NA) |
| Sortowanie wiadro | O(n + k) | O(n + k) | NA2) | NA) |
| Sortuj Radix | O(nk) | O(nk) | O(nk) | O(n + k) |
| Sortowanie licznikowe | O(n + k) | O(n + k) | O(n + k) | Strzałka) |
| Sortowanie powłoki | O(n log(n)) | O(n log(n)) | NA2) | O(1) |
| Tim Sort | NA) | O(n log(n)) | O(n log (n)) | NA) |
| Sortowanie drzew | O(n log(n)) | O(n log(n)) | NA2) | NA) |
| Sortowanie kostek | NA) | O(n log(n)) | O(n log(n)) | NA) |
Zobacz także:
- Wyszukiwanie i sortowanie artykułów
- Pytania GATE z poprzedniego roku dotyczące sortowania
- Złożoność czasowo-przestrzenna sortowania przez wstawianie
- Złożoność czasowo-przestrzenna sortowania przez wybór
- Złożoność czasowo-przestrzenna sortowania bąbelkowego
- Złożoność czasowo-przestrzenna szybkiego sortowania
- Złożoność czasowa i przestrzenna sortowania przez scalanie
- Złożoność czasowo-przestrzenna algorytmu sortowania radiacyjnego