Złożoność czasowa, a pamięciowa

Question

Wie ktos moze, czy duza zlozonosc pamieciowa moze wplynac na zlozonosc czasowa? np jak potrzebne mi jest do programu 1000 zmiennych w tablicy, a ja utworze milion to czy moze to wplynac na czas dzialania programu? mam na mysli zadanka na szkopule

Answer 1

Nie ma bezpośredniego powiązania między złożonością obliczeniową a pamięciową. Często używa się dodatkowej pamięci aby zapisać wyniki częściowe i zredukować złożoność obliczeniową.

Answer 2

Po 1, musisz uważać z pamięcią, żeby nie przekroczyć limitu pamięci.

Po 2, jeśli zrobisz, np int dp[N][N] i powstawiasz tam zera 2 forami, to złożonnośc z automatu robi się przynajmniej O(N^2), no ale bez sensu robić taką tablicę, jęsli jej nie potrzebujesz. Tak samo bez sensu robić tablicę o rozmiarze 1e6, jak wystarcza Ci tablica o rozmiarze 1e4.

Wszystko zależy od przypadku. Opisz dokładnie o jaki przypadek ci chodzi.

Comments

nie mam jakiegos konkretnego przypadku, tylko pytam sie na przyszlosc, czy np. jak potrzebne mi jest np 1e4 elem. w tablicy, a ja np. zadeklaruje 1e6, to czy program moze dzialac wolniej.

Answer 3

Co do teorii, powiązania nie ma. W praktyce jednak... alokowanie i wypełnienie danymi zabiera czas (co można znów pomijać bo narzut jest niewielki jeśli dane nie wymagają skomplikowanych obliczeń). Zwalnianie tych danych także zabiera czas (wpływ... jak wyżej).

Sytuacja zmienia się diametralnie gdy rzeczywiście przekraczasz zasoby pamięciowe platformy. Konieczność stronnicowania pamięci (swap), wpływa mocno na wydajność aplikacji. Znów w "sprawdzarkach", daleko Ci do takich mechanizmów.

No i jeszcze są ustawienia obszarów pamięci z użyciem mechanizmów systemowych (współdzielenie, atomowość, dostęp odczyt/zapis, cache, transakcje na szynach). Ale w kontekście systemów sprawdzających algorytmy, to jest temat nieistniejący.