وقت التشغيل لإدراج عناصر n في جدول تجزئة فارغ

Question

يقول الناس أن الأمر يتطلب O (1) المطفأ لوضعه في جدول التجزئة.لذلك، يجب أن يكون وضع العناصر n هو O(n).ومع ذلك، هذا ليس صحيحًا بالنسبة إلى n الكبير، لأنه كما قال أحد المجيبين، "كل ما تحتاجه لتلبية O(1) المطفأ المتوقع هو توسيع الجدول وإعادة صياغة كل شيء باستخدام دالة تجزئة عشوائية جديدة في أي وقت يحدث فيه تصادم."

لذا:ما هو متوسط ​​وقت تشغيل إدراج عناصر n في جدول التجزئة؟أدرك أن هذا ربما يعتمد على التنفيذ، لذا اذكر نوع التنفيذ الذي تتحدث عنه.

على سبيل المثال، إذا كان هناك (log n) تصادمات متباعدة بشكل متساوٍ، وكل تصادم يستغرق O(k) لحله، حيث k هو الحجم الحالي لجدول التجزئة، فستكون لديك علاقة التكرار هذه:

T(n) = T(n/2) + n/2 + n/2

(أي أنك تأخذ الوقت الكافي لإدراج عناصر n/2، ثم يكون لديك تصادم، وتستغرق n/2 لحلها، ثم تقوم بإدراج n/2 المتبقية دون تصادم).لا يزال هذا في النهاية O(n)، لذا رائع.ولكن هل هذا معقول؟

Answer 1

يعتمد الأمر تمامًا على مدى عدم كفاءة إعادة الصياغة.على وجه التحديد، إذا كان بإمكانك تقدير الحجم المتوقع لجدول التجزئة الخاص بك بشكل صحيح في المرة الثانية، فإن وقت التشغيل الخاص بك لا يزال يقترب من O(n).على نحو فعال، يجب عليك تحديد مدى عدم كفاءة حساب حجم إعادة الصياغة قبل أن تتمكن من تحديد الترتيب المتوقع.

Answer 2

يقول الناس أن الأمر يتطلب O (1) المطفأ لوضعه في جدول التجزئة.

ومن الناحية النظرية فهو كذلك مُتوقع المطفأة (1).

تعد جداول التجزئة في الأساس بنية بيانات عشوائية، بنفس المعنى الذي يعتبر فيه الفرز السريع خوارزمية عشوائية.تحتاج إلى إنشاء وظائف التجزئة الخاصة بك مع بعض العشوائية، وإلا فستكون هناك مدخلات مرضية ليست O(1).

يمكنك تحقيق الإطفاء المتوقع O(1) باستخدام التجزئة الديناميكية المثالية:

كانت الفكرة الساذجة التي نشرتها في الأصل هي إعادة صياغة دالة التجزئة العشوائية الجديدة في كل تصادم.(أنظر أيضا وظائف التجزئة المثالية) المشكلة في هذا هي أن هذا يتطلب مساحة O(n^2)، من مفارقة عيد الميلاد.

الحل هو أن يكون لديك اثنين جداول التجزئة، مع الجدول الثاني للتصادمات؛حل التصادمات على هذا الجدول الثاني عن طريق إعادة بنائه.سيحتوي هذا الجدول على عناصر O(\sqrt{n})، لذا سينمو إلى حجم O(n).

من الناحية العملية، غالبًا ما تستخدم فقط دالة تجزئة ثابتة لأنك تستطيع أن تفترض (أو لا تهتم إذا) أن مدخلاتك مرضية، مثلما تفعل غالبًا في الفرز السريع دون إجراء عشوائي مسبقًا للمدخلات.

Answer 3

كل ما يقوله O(1) هو أن العملية يتم تنفيذها في وقت ثابت، وهو كذلك لا يعتمد على عدد العناصر في بنية البيانات الخاصة بك.

بكلمات بسيطة، هذا يعني أنه سيتعين عليك دفع نفس التكلفة بغض النظر عن حجم بنية البيانات الخاصة بك.

من الناحية العملية، هذا يعني أن هياكل البيانات البسيطة مثل الأشجار موجودة عمومًا أكثر فعالية عندما لا تضطر إلى تخزين الكثير من البيانات.في تجربتي، وجدت الأشجار أسرع بما يصل إلى ألف عنصر تقريبًا (أعداد صحيحة 32 بت)، ثم تتولى جداول التجزئة المهمة.ولكن كالعادة YMMW.

Answer 4

لماذا لا تقوم فقط بإجراء بعض الاختبارات على نظامك؟ربما إذا قمت بنشر المصدر، فيمكننا العودة واختباره على أنظمتنا ويمكننا تحويل هذا إلى مناقشة مفيدة للغاية.

ليس التنفيذ فحسب، بل البيئة أيضًا هي التي تحدد مقدار الوقت الذي تستغرقه الخوارزمية فعليًا.ومع ذلك، يمكنك معرفة ما إذا كانت هناك أي عينات مرجعية متاحة أم لا.لن تكون المشكلة في نشر نتائجي ذات فائدة نظرًا لأن الأشخاص ليس لديهم أي فكرة عما يتم تشغيله على نظامي، أو مقدار ذاكرة الوصول العشوائي المجانية في الوقت الحالي، وما إلى ذلك.لا يمكنك الحصول إلا على فكرة واسعة النطاق.وهذا جيد تمامًا مثل ما يقدمه لك Big-O.