Cad is ionanáil fhadaithe ann, ag úsáid athmhéadarú suíomh dinimiciúil mar shampla?

Question

Accepted Answer

**Anailís ionanáil** tomhaisíonn an **meánchostas in aghaidh an oibríochta thar sheicheamh**, fiú nuair a bhíonn costas i bhfad níos airde ar oibríochtaí aonair ó am go ham. Míníonn sí cén fáth go bhfuil `append` i suíomh dinimiciúil "**O(1) ionanáil**" in ainneoin athmhéadaruithe O(n) ó am go ham.

## An sampla suíomh dinimiciúil

Nuair a bhíonn suíomh dinimiciúil líofa, asraithíonn sé suíomh nua (de ghnáth **2×**) agus déanann sé cóipeanna ar bhonneagair na n-eilimintí — céim O(n). Ach toisc go bhfuil an acmhainneacht **ag dúblú**, beireann suíomh na gcóipeanna costasacha ar dhóigh a bhíonn i bhfad níos fánach.

```text
Appending into a doubling array (cap shown):
ops:   1  2  3  4  5  6  7  8  9
cap:   1  2  4  4  8  8  8  8  16
copy:  *  *  *     *           *      <- copies at 1,2,4,8,16...
```

## An mhatamaitic

```text
To insert n elements, total copy work =
  1 + 2 + 4 + ... + n  ≈  2n   (geometric series)
Total cost for n inserts = O(n)
Amortized cost per insert = O(n)/n = O(1)
```

```python
arr = []
for i in range(1_000_000):
    arr.append(i)   # almost always O(1); rarely O(n) during a resize
```

| Oibríocht | Drochchás aonair | Ionanáil |
|---|---|---|
| append (dúblú) | O(n) | **O(1)** |

## Cén fáth dúblú (ní +1)

Dá bhfásfadh ar bhonn de **fhad seasmhach**, bheadh cóip á bhrú ar gach ionsá, rud a thabharfadh ionanáil O(n). Is an fás iolraitheach atá ina chúis go bhfuil an costas scaipthe amach.

## Cén fáth a bhíonn sé tábhachtach

Tugann anailís ionanáil pictiúr cothrom, réalúsach ar dhul chun cinn — gan í, bheadh eagla ort go mícheart go bhfuil gach `append` nó ionsá table hais i O(n).

Dlúthaíonn sí freisin riail dhearaidh bhunúsach: **acmhainneacht a fhás ar bhonn iolraitheach**, ar a bhunúíonn suímh dinimiciúla, táblaí hash agus tógálaithe teangabhair ar fud an domhain.