অ্যামর্টাইজড অ্যানালাইসিস কী, ডায়নামিক অ্যারে রিসাইজিংকে উদাহরণ হিসেবে ব্যবহার করে?

Question

Accepted Answer

**অ্যামর্টাইজড অ্যানালাইসিস** **একটি ক্রম জুড়ে প্রতিটি অপারেশনের গড় খরচ** পরিমাপ করে, এমনকি যখন পৃথক অপারেশনগুলি কখনও কখনও অনেক বেশি খরচ করে। এটি ব্যাখ্যা করে যে কেন ডায়নামিক অ্যারের `append` "**O(1) amortized**" অ্যাওয়ে মুহূর্তকার O(n) রিসাইজ থাকা সত্ত্বেও।

## ডায়নামিক অ্যারে উদাহরণ

যখন একটি ডায়নামিক অ্যারে পূর্ণ হয়ে যায়, এটি একটি নতুন অ্যারে (সাধারণত **2×**) বরাদ্দ করে এবং সমস্ত উপাদান কপি করে — এটি একটি O(n) ধাপ। কিন্তু কারণ ক্ষমতা **দ্বিগুণ হয়**, ব্যয়বহুল কপিগুলি সূচকভাবে বিরল হয়ে ওঠে।

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

## গণিত

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

| অপারেশন | সবচেয়ে খারাপ একক | অ্যামর্টাইজড |
|---|---|---|
| append (doubling) | O(n) | **O(1)** |

## কেন দ্বিগুণ (এবং +1 নয়)

**ধ্রুবক পরিমাণ** দ্বারা বৃদ্ধি করলে প্রতিটি প্রবেশে একটি কপি ট্রিগার হবে, যা O(n) অ্যামর্টাইজড দেয়। গুণক বৃদ্ধি হল যা খরচটি ছড়িয়ে দেয়।

## কেন এটি গুরুত্বপূর্ণ

অ্যামর্টাইজড অ্যানালাইসিস একটি ন্যায্য, বাস্তবসম্মত পারফরম্যান্স চিত্র দেয় — এটি ছাড়া, আপনি ভুলভাবে ভয় পাবেন যে প্রতিটি `append` বা hash-table insert হল O(n)।

এটি একটি মূল ডিজাইন নিয়মও ন্যায্যতা দেয়: **ক্ষমতা গুণকীয়ভাবে বৃদ্ধি করুন**, যা ডায়নামিক অ্যারে, hash টেবিল এবং স্ট্রিং বিল্ডারের মেরুদণ্ড সর্বত্র।