• Najnowsze pytania
  • Bez odpowiedzi
  • Zadaj pytanie
  • Kategorie
  • Tagi
  • Zdobyte punkty
  • Ekipa ninja
  • IRC
  • FAQ
  • Regulamin
  • Książki warte uwagi

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

Object Storage Arubacloud
0 głosów
260 wizyt
pytanie zadane 24 lutego 2023 w C i C++ przez polandonion Mądrala (7,140 p.)
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

3 odpowiedzi

0 głosów
odpowiedź 24 lutego 2023 przez tangarr Mędrzec (154,860 p.)
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ą.
0 głosów
odpowiedź 24 lutego 2023 przez pasjonat_algorytmiki Pasjonat (19,540 p.)
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.
komentarz 24 lutego 2023 przez polandonion Mądrala (7,140 p.)
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.
0 głosów
odpowiedź 24 lutego 2023 przez mokrowski Mędrzec (156,140 p.)
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.

Podobne pytania

+1 głos
0 odpowiedzi 334 wizyt
0 głosów
1 odpowiedź 941 wizyt

92,660 zapytań

141,553 odpowiedzi

319,993 komentarzy

62,028 pasjonatów

Motyw:

Akcja Pajacyk

Pajacyk od wielu lat dożywia dzieci. Pomóż klikając w zielony brzuszek na stronie. Dziękujemy! ♡

Oto polecana książka warta uwagi.
Pełną listę książek znajdziesz tutaj.

Akademia Sekuraka

Kolejna edycja największej imprezy hakerskiej w Polsce, czyli Mega Sekurak Hacking Party odbędzie się już 20 maja 2024r. Z tej okazji mamy dla Was kod: pasjamshp - jeżeli wpiszecie go w koszyku, to wówczas otrzymacie 40% zniżki na bilet w wersji standard!

Więcej informacji na temat imprezy znajdziecie tutaj. Dziękujemy ekipie Sekuraka za taką fajną zniżkę dla wszystkich Pasjonatów!

Akademia Sekuraka

Niedawno wystartował dodruk tej świetnej, rozchwytywanej książki (około 940 stron). Mamy dla Was kod: pasja (wpiszcie go w koszyku), dzięki któremu otrzymujemy 10% zniżki - dziękujemy zaprzyjaźnionej ekipie Sekuraka za taki bonus dla Pasjonatów! Książka to pierwszy tom z serii o ITsec, który łagodnie wprowadzi w świat bezpieczeństwa IT każdą osobę - warto, polecamy!

...