מערך

נוכל לממש מערך בכמה דרכים:

1. איזור רצוף בזכרון: זמן ביצוע $store,get$ הוא $O(1)$ וזמן יצירת מערך חדש תלוי בזמן הקצאת מקום ובשאלה האם צריך למלא את כולו בערך התחלתי בעת היצירה.
2. מספר איזורים רצופים בזכרון שלכל אחד גודל קבוע $k$: לכל איזור כזה נקרא "בלוק". כדי לממש מערך בגודל $n$ יש להקצות $m$ בלוקים כאשר $m=\lceil \frac{n}{k}\rceil$ ובלוק נוסף שנקרא "מדריך". נסמן את כתובת הבסיס של המדריך ב-$base$ ואז האיבר ה-$A[i]$ נמצא בכתובת $base\left[ \lfloor \frac{i}{k} \rfloor \right]+i\pmod{k}$. זמן חישוב הכתובת במקרה זה הוא גם כן $O(1)$.
   לדוגמה, עבור $k=6,i=16$ הכתובת של $A[16]$ מחושבת ע"י: $base\left[ \lfloor \frac{16}{6} \rfloor \right]+16\pmod{6}=base[2]+4$.

מערך רב מימדי

במערך רב מימדי $A[n_{d}]\dots[n_{3}][n_{2}][n_{1}]$ הכתובת של $A[i_{d}]\dots[i_{2}][i_{1}]$ מחושבת ע"י הנוסחה:

נוכל לייעל את חישוב הכתובת באמצעות הקוד הבא:

addr = i[d];
for (j = d - 1; j >= 1; j--)
	addr = addr * n[j] + i[j];
addr = base + addr;

אתחול מערך ב-$O(1)$

נרצה לעדכן את פעולת $create$ כך שתקבל פרמטר נוסף $d$ כך שכל התאים במערך יאותחלו לערך זה.
אתחול מערך באופן זה בגודל $n$ דורש זמן של $\Theta(n)$ אך נרצה לעשות זאת בפעולת האתחול בזמן קבוע.
⟸ כדי לעשות זאת אנו נשתמש בזכרון נוסף (ללא שינוי אסימפטוטי).

בעצם, אי אפשר לאתחל מערך כזה מהר אך אנו שולטים ב-$get$ וב-$store$. נשמור מידע על אילו אינדקסים כבר נכתבו ואם נגשים לאינדקס שלא נכתב עליו כלום, נחזיר את הערך ההתחלתי.

מטריצות

• עבור מטריצה סימטרית נוכל לאחסן רק את חצי מהערכים שכן $A_{i,j}=A_{j,i}$. נחשב את המיקום כך:
  $Add(i,j)=\begin{cases} Base+i \frac{i+1}{2}+j & i\geq j \\ Addr(j,i) & else \end{cases}$
• עבור מטריצטת דלילות, כשרוב המוחלט של האיברים הוא $0$, נוכל לשמור במערך את האיברים של המטריצות בשלשות $(i,j,A_{ij})$.

כאשר נרצה לאחסן סדרה שכזו נשמש בטריק של אחסון שלשות $(i,j,A_{i})$ בסדר לקסיקוגרפי. בכך, נוותר על סיבוכיות הזמן $O(1)$ לטובת חוסך בזכרון והאצה של םעולות חיבור וכפל.