Complexitatea de memorie

Pentru a calcula correct complexitatea memorie, vom proceda similartimpului de execuție, dar lucrurile nu sunt la fel de simple întrucât fiecare tip de date ocupă un anumit număr de bytes. In funcție de acest număr de bytes, vom avea o complexitatea mai mică sau mai mare. Evident, după ce știm lungimile tipurilor de date, conversia devine ușoară: $10^6$ int-uri ocupă $4\times 10^6\approx 4\text{MB}$ (vezi unități de măsură) În acest mod, la fel ca la timp, încă din faza de proiectare putem să calculăm câtă memorie ocupă programul nostru și astfel, aflăm dacă trebuie să facem sau nu optimizări.

Unități de măsură

În sistemul internațional prefixele iau ca valori puterile lui $10$ ($\text{deca}=10^1,\text{hecto}=10^2,\text{kilo}=10^3$) iar după kilo, cresc din $10^3$ în $10^3$ ($\text{mega}=10^6,\text{giga}=10^9,\text{tera}=10^{12}$, etc). Problema este că în general se face confuzie între prefixele sistemului internațional și prefixele binare care nu fac parte din SI.

Prefixele binare urcă din $2^{10}$ în $2^{10}$ și sunt formate din prima silabă a prefixului SI și bi. De exemplu $\text{kilo}$ devine $\text{kibi}$, iar simbolul este $\text{Ki}$ și $\text{mega}$ devine $\text{mebi}$ și are ca simbol $\text{Mi}$ Astfel deși este general acceptat, este eronat să spunem că $1\text{KB}=2^{10}\text{B}$ sau $1\text{MB}=2^{20}\text{B}$. În schimb corect este $1\text{MB}=10^3\text{B}$, iar $1\text{MiB}=2^{20}\text{B}$. Realist, diferența este minusculă și nesemnificativă, iar oricum majoritatea oamenilor nu o cunosc. Totuși așa se explică unele ciudățenii în sistemele de operare, de exemplu un hard disk pe care scrie $1\text{TB}$ chiar are $10^{12}B$, dar Windows va calcula folosind prefixele binare și totuși îl va afișa cu prefixe SI ca $931\text{GB}$. Mai multe detalii aici