يفترض فهم تدوين Big O. الأمثلة موجودة في جافا سكريبت. مراجع المعلومات "Cracking the Coding Interview" بقلم جايل لاكمان ماكدويل

مقدمة

في بعض اللغات مثل JavaScript أو Python، يمكن تغيير حجم المصفوفات تلقائيًا، مما يعني أنها ستنمو عند إلحاق العناصر. في لغات أخرى مثل Java، تكون المصفوفات ذات أطوال ثابتة، مما يعني أن الحجم يتم تحديده عند تهيئة المصفوفة. تسمى هذه المصفوفات التي تنمو تلقائيًا المصفوفات الديناميكية.

فهم المصفوفات الديناميكية

في Java، ArrayList عبارة عن بنية بيانات تشبه المصفوفة توفر تغيير الحجم الديناميكي مع الاستمرار في توفير $(1\mathrm{)}O(1)$O(1) وصول. عندما تكون المصفوفة ممتلئة، يتضاعف حجم المصفوفة. كل مضاعفة تأخذ $ن)\mathrm{O\; (ن)}$ الوقت، ولكنه نادرًا ما يحدث لدرجة أن وقت إدخاله المطفأ لا يزال ثابتًا ($)O(1)\mathrm{}O(1)$ . من بين لغات البرمجة المختلفة، يختلف اسم بنية البيانات هذه بالإضافة إلى عامل تغيير الحجم (وهو 2 في Java). يحدد عامل تغيير الحجم حجم المصفوفة التي سيتم تغيير حجمها. لماذا هو وقت الإدراج المطفأ

( 1$\mathrm{O(1)}\mathrm{}O(1)$ عند تغيير الحجم، بافتراض أن عامل تغيير الحجم هو 2، يمكننا أن نلاحظ أننا قمنا بزيادة حجم المصفوفة N عن طريق مضاعفة المصفوفة السابقة (والتي هي نصف N). علاوة على ذلك، نحتاج أيضًا إلى النسخ N

2 N/2 $\mathrm{N/2}\mathrm{}\mathrm{عناصر\; لهذه\; المجموعة\; الجديدة.}$ 2

ن 4 ]n 8 n 16 ن ... 2 1 والتي مجموعها أقل بقليل من N. لذلك، فإن إدخال عناصر N يستغرق حوالي ( ن ) O (ن) على) العمل في المجموع. كل إدراج هو ( 1 ) O(1) O(1) $في\; المتوسط،\; على\; الرغم\; من\; أن\; بعض\; عمليات\; الإدراج\; تستغرق(ن$ O (ن) على) $الوقت\; في\; أسوأ\; الأحوال.المفاهيم\; الأساسية\; والتعقيد\; الكبيرتحتوي\; المصفوفات\; الديناميكية\; في\; JavaScript\; عادةً\; على\; عدة\; طرق\; أساسية،\; لكل\; منها\; تعقيدات\; زمنية\; مختلفة:get(i):\; تسترد\; هذه\; الطريقة\; العنصر\; الموجود\; في\; الفهرس\; i.\mathrm{}تعقيد:$ ( 1 ) O(1) $\mathrm{O(1)}set(i,\; n):\; تقوم\; هذه\; الطريقة\; بتعيين\; العنصر\; في\; الفهرس\; i\; إلى\; n.تعقيد:$ (

• O(1) $pushback(n):\; تضيف\; هذه\; الطريقة\; العنصر\; n\; إلى\; نهاية\; المصفوفة.\mathrm{}تعقيد:$( 1 ) O(1)

O(1)
• $المطفأة،\; ولكن(\mathrm{}ن)$على)
عند حدوث تغيير الحجم

• تعقيد: $(1\mathrm{})O(1)$ O(1) resize(): تعمل هذه الطريقة على مضاعفة سعة المصفوفة ونسخ جميع العناصر إلى المصفوفة الجديدة.$تعقيد:(ن$ O (ن) على)

• getSize(): تقوم هذه الطريقة بإرجاع عدد العناصر في المصفوفة. $تعقيد:(\mathrm{}1)$ O(1)

: نحن قادرون على تحقيق هذا التعقيد باستخدام متغير الحجم لتتبع عدد الفتحات المملوءة في المصفوفة.
• getCapacity(): تُرجع هذه الطريقة السعة الحالية للمصفوفة.$تعقيد:(1$O(1) O(1)

• التنفيذ في جافا سكريبت فئة DynamicArray { // الحجم هو # الفتحات المملوءة بينما السعة هي إجمالي الفتحات في المصفوفة منشئ (القدرة) { this.capacity = القدرة؛ this.arr = new Array(this.capacity); this.size = 0; } // يا(1) الحصول على (ط) { إذا (i = this.size) يُرجع غير محدد؛ إرجاع this.arr[i]; } // يا(1) اجلس هنا) { إذا (i = this.size) يُرجع غير محدد؛ this.arr[i] = n; } // O(1) مطفأة التراجع (ن) { إذا (this.size === this.capacity) { this.resize(); } this.arr[this.size] = n; هذا الحجم ؛ } // يا(1) عودة البوب() { إذا (this.size === 0) يُرجع غير محدد؛ هذا الحجم--؛ دع درجة الحرارة = this.arr[this.size]; this.arr[this.size] = غير محدد; درجة حرارة العودة؛ } // على) تغيير الحجم() { this.capacity *= 2; دع newArr = new Array(this.capacity); من أجل (دع i = 0؛ i خاتمة تعد المصفوفات الديناميكية بنية بيانات قوية تجمع بين مرونة التخزين القابل لتغيير الحجم وكفاءة الوصول في الوقت الثابت. أتمنى أن يساعدك هذا!