Array ni kamba ya kumbukumbu inayoendelea inayoshikilia vipengele vya aina moja, inayohesabiwwa kuanzia 0. Kwa sababu vipengele viko karibu na kila kimoja, anwani ya kipengele i inakokotolewa moja kwa moja kama base + i * elementSize, ikiwa na **O(1) mfumo wa kufikia".
index: 0 1 2 3 4
+-----+-----+-----+-----+-----+
arr = | 10 | 20 | 30 | 40 | 50 |
+-----+-----+-----+-----+-----+
address: base +4 +8 +12 +16 (4-byte ints)
arr = [10, 20, 30, 40, 50]
x = arr[3] # O(1) — direct index math
arr.append(60) # amortized O(1) (dynamic array)
arr.insert(0, 5) # O(n) — shift every element right
arr.pop(0) # O(n) — shift every element left
| Operesheni | Muda |
|---|---|
| Kufikia kwa index | O(1) |
| Kutafuta (haijapangwa) | O(n) |
| Kuongeza (inayobadilika) | O(1) iliyoboreswa |
| Kuingiza/kufuta mwanzoni/katikati | O(n) |
Arrays ndio msingi chini ya miundo mingi - kamba, meza za hash, heaps, na orodha zinazobadilika zote zimejengwa juu yao.
Uwazi wa cache-yao mara nyingi hurahisisha array "polepole" ya Big-O kushinda muundo wa "kasi" unaozingatia usajili katika marekebisha halisi.
Maktaba ya maswali ya mahojiano ya IT yenye majibu ya kina — kutoka Junior hadi Senior.
Changia