Pamięć komputerów osobistych jest dość ograniczona jak i szybkość przeprowadzanych operacji. Z powodu braku wystarczającej wielkości pamięci przy bardzo dużych liczbach dostałbyś chyba overflow (przepełnienie).
Chcemy wypisać elementy tej listy w takiej kolejności, żeby każda część występowała wcześniej niż dowolna część, która ją wykorzystuje.
Przyjmijmy, że sokowirówka (będzie ich kilka typów oznaczone numerami) to część, która występuje wcześniej (ponieważ wykorzystuje jakiś owoc), a elementy listy to owoce.
(list :juicer1 'apple :juicer3 'pear :juicer2 'orange :juicer4 'cherry :juicer5 'lemon)
Dla pięciu różnych rodzajów sokowirówek i owoców mamy 5! możliwości, czyli 120. Dla 6!=720, 7!=5040; itd..
Dla 7! możliwości mamy np. wprawić w ruch pętlę, która wykona aż 5040 obrotów, przecież to nie optymalne. Korzystając chociażby ze struktury danych - listy pozbywamy się tego problemu.
gigamonkeys.com/.../Common_Lisp
Poniższa lista może być uporządkowana na 3! możliwości.
[1][]->[2][]->[3][NIL]
1 2 3
1 3 2
2 3 1
2 1 3
3 2 1
3 1 2
Kolejność obojętna, ważne żeby juicer+ był przed (owoc)*.
juicer - sokowirówka
Jeśli się nie mylę, to ten problem to jest po prostu sortowanie. Poniżej przedstawię sortowanie listy jednokierunkowej przez scalanie.
(1 3 2) ; input
(1 3 2 nil) ; input, but with append element nil, that was even number of elements
((1 2) (3 nil))
((1) (2) (3) (nil))
((1 2) (3 nil))
(1 2 3 nil) ; output
Złożoność algorytmu merge sort.
Czasowa: O(n * log (n))
Pamięciowa: O(n)
wikipedia.org
;;; Helper function to tell us if a given sequence has just one element.
(defun single (sequence)
(if (consp sequence)
(not (cdr sequence))
(= (length sequence) 1)))
;;; Sequence can be a vector or a list. Note that this means that this
;;; code isn't optimized for any of those.
(defun merge-sort (sequence)
(if (or (null sequence) (single sequence))
sequence
(let ((half (truncate (/ (length sequence) 2))))
;; MERGE is a standard common-lisp function, which does just
;; what we want.
(merge (type-of sequence)
(merge-sort (subseq sequence 0 half))
(merge-sort (subseq sequence half))
#'<))))
Implementacja algorytmu merge sort - licencja GFDL
Cechy Algorytmu Sortowania Przez Scalanie
| klasa złożoności obliczeniowej optymistyczna |
O(n log n) |
| klasa złożoności obliczeniowej typowa |
O(n log n) |
| klasa złożoności obliczeniowej pesymistyczna |
O(n log n) |
| Sortowanie w miejscu |
NIE |
| Stabilność |
TAK |
źródło
Jeśliby założono, że pojedyncza instrukcja wykonuje się jedną nanosekundę (czyli na komputerze działającym z częstotliwością 1 GHz) wtedy czasy wykonania względem rozmiaru danych wyglądałyby następująco:
Złożoność obliczeniowa względem rozmiaru danych wejściowych
| Rozmiar danych |
10 |
20 |
50 |
100 |
| n |
10 ns |
20 ns |
50 ns |
100 ns |
| n! |
3.6 ms |
77 lat |
9.6 * 10^44 lat |
3 * 10^141 lat |
W tabeli n - O(n); n! O(n!).
Jeśli więc jesteśmy w stanie rozwiązać postawione zadanie algorytmem o złożoności nie większej niż wielomianowej, wtedy mamy szansę na rozwiązanie zadania w realnym/rozsądnym czasie. Jeśli zaś algorytm posiada złożoność ponadwielomianową, wtedy w praktyce wykonywanie algorytmu dla większej ilości danych, nigdy się ne zakończy,gdyż często rozwiązanie trwałoby dłużej niż szacowany wiek Wszechświata (ok. 1010 lat)! Warto więc rozważać złożoność obliczeniową algorytmów, gdyż bez niej nawet dokładny i poprawny algorytm może się dla nas realnie nigdy nie zakończyć!
źródło
Widać już chyba dlaczego przy złożoności O(n!) niemozliwe jest doczekanie się na sensowny rezultat w sensownym czasie. Zgodnie z przykładem, już przy rozmiarze danych wejściowych 10 widać, że przy tej złożoności czas wykonania to 3.6 milisekundy, czyli 0.0036 sekundy, gdzie przy złożoności O(n) jest to zaledwie 10 nanosekund - 0.000000010 sekundy.
sortowanie przez scalanie złożoność obliczeniowa złożoność obliczeniowa
