Kas yra masyvas ir kokie yra jo operacijų sudėtingumai?

Question

Accepted Answer

**Masyvas** yra greta vienas kito esantis atminties blokas, kuriame saugomi to paties tipo elementai, indeksuoti nuo `0`. Kadangi elementai yra vienas šalia kito, elemento `i` adresas apskaičiuojamas tiesiogiai kaip `base + i * elementSize`, todėl gaunamas **O(1) atsitiktinis prieiga**.

## Atminties išdėstymas

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

## Pavyzdys

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

## Sudėtingumas

| Operacija | Laikas |
|---|---|
| Prieiga pagal indeksą | O(1) |
| Paieška (nerūšiuota) | O(n) |
| Pridėjimas (dinaminis) | O(1) amortizuota |
| Įterpimas/ištrynimas pradžioje/viduryje | O(n) |

## Kompromisai

- **Stiprybės:** greita indeksavimas, „cache-friendly

Operacija	Laikas
Prieiga pagal indeksą	O(1)
Paieška (nerūšiuota)	O(n)
Pridėjimas (dinaminis)	O(1) amortizuota
Įterpimas/ištrynimas pradžioje/viduryje	O(n)