Array ni nini na kompleksiteti ya operesheni zake ni zipi?

Question

Accepted Answer

**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".

## Mpangilio wa kumbukumbu

```text
index:    0     1     2     3     4
        +-----+-----+-----+-----+-----+
arr =   | 10  | 20  | 30  | 40  | 50  |
        +-----+-----+-----+-----+-----+
address: base  +4    +8    +12   +16   (4-byte ints)
```

## Mfano

```python
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
```

## Kompleksiteti

| Operesheni | Muda |
|---|---|
| Kufikia kwa index | O(1) |
| Kutafuta (haijapangwa) | O(n) |
| Kuongeza (inayobadilika) | O(1) iliyoboreswa |
| Kuingiza/kufuta mwanzoni/katikati | O(n) |

## Matatizo

- **Mimi na wenzi:** kuindeksa kwa kasi, sawa na cache (data inalingana), kuzuia kumbukumbu kidogo.
- **Udhaifu:** kuingiza/kufuta katikati ni O(n); arrays ya saizi isiyobadilika inahitaji kunakili ili kukua.

## Kwa nini inakweza

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.

Operesheni	Muda
Kufikia kwa index	O(1)
Kutafuta (haijapangwa)	O(n)
Kuongeza (inayobadilika)	O(1) iliyoboreswa
Kuingiza/kufuta mwanzoni/katikati	O(n)