zdj2 (3)

Praktyczne metody obniżania złożoności

pamięciowej algorytmów

3. Komprymowanie danych umożliwiające ograniczanie pamięci przez stosowanie kompresji danych pochodzą z teorii informacji. Jeżeli elementy macierzy rzadkiej przyjmują tylko dwie wartości, jak na przykład w teorii grafów, to można zapamiętać je w postaci upakowanej na bitach. Podobnie dwie cyfry dziesiętne a i można zapisać w jednym bajcie za pomocą liczby n = 10a+b. Do odkodowania informacji służą wówczas dwie instrukcje:

:= n div 10;

b := n mod 10;

ma istotne

W ten sposób osiągamy oszczędność 50%. znaczenie, gdy takich liczb jest bardzo dużo.

Wykład 6 Programowanie komputerów I > —