Kāda ir laika sarežģītības līmenis operācijai, pievienojot elementu masīva beigās, izmantojot slice?

Go valodā operācija, pievienojot elementu slice (append), ir amortizēta laika sarežģītība O(1).

Skaidrojums:

• Ja slice ir pietiekami liela kapacitāte (capacity), elementa pievienošana notiek vienkārši rakstot nākamajā brīvajā indeksā — tas ir operācija ar konstantu laiku.

• Ja kapacitāte nav pietiekama, tiek piešķirts jauns, lielāks masīvs, vecie elementi tiek kopēti un pievienots jauns — šī operācija aizņem O(n), kur n ir pašreizējais slice izmērs.

Tomēr, tā kā šādas pārdalīšanas nenotiek katru reizi, bet tikai periodiski, vidējā (amortizētā) pievienošanas sarežģītība paliek O(1).