ما الأمر مع (1)؟

Question

لقد لاحظت بعض الاستخدام الغريب جدًا لـ O(1) في مناقشة الخوارزميات التي تتضمن التجزئة وأنواع البحث، غالبًا في سياق استخدام نوع القاموس الذي يوفره نظام اللغة، أو استخدام أنواع القاموس أو مصفوفة التجزئة المستخدمة باستخدام المصفوفة -مؤشر التدوين.

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

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

على الرغم من أنني لاحظت ذلك من قبل، فقد ظهر مثال للتو في ملف سؤال Pandincus، "المجموعة" المناسبة "التي يجب استخدامها للحصول على العناصر في وقت O(1) في C# .NET؟".

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

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

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

السؤال:كل هذا التحضير هو في الحقيقة سؤال.ما هو العرضية المحيطة بـ O(1) ولماذا يتم قبولها بشكل أعمى؟هل من المسلم به أنه حتى O(1) يمكن أن يكون كبيرًا بشكل غير مرغوب فيه، على الرغم من أنه شبه ثابت؟أم أن O(1) مجرد الاستيلاء على فكرة التعقيد الحسابي للاستخدام غير الرسمي؟أنا في حيرة.

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

Answer 1

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

وأما العنصر الآخر من الارتباك هو أن O تدوين كبير يصف الحد من السلوك. وهكذا، فإن وظيفة و (N) للقيم صغيرة من N قد تظهر في الواقع تفاوتا كبيرا، ولكن كنت لا تزال يكون من الصحيح القول هو O (1) إذا كان الحد الأقصى مع اقتراب N اللانهاية هو ثابت فيما يتعلق N.

Answer 2

المشكلة هي أن الناس غير دقيقين حقًا في المصطلحات.هناك 3 فئات مهمة ولكنها متميزة هنا:

O(1) في أسوأ الأحوال

هذا أمر بسيط - جميع العمليات لا تستغرق أكثر من مقدار ثابت من الوقت في أسوأ الحالات، وبالتالي في جميع الحالات.الوصول إلى عنصر من مجموعة هو O(1) الحالة الأسوأ.

O(1) مطفأة في أسوأ الأحوال

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

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

O(1) حالة متوسطة

هذا هو الأصعب.هناك تعريفان محتملان للحالة المتوسطة:واحدة للخوارزميات العشوائية ذات المدخلات الثابتة، وواحدة للخوارزميات الحتمية ذات المدخلات العشوائية.

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

وفي الحالة الأخرى، نحتاج إلى توزيع احتمالي على المدخلات.على سبيل المثال، إذا أردنا قياس خوارزمية فرز، فإن أحد هذه التوزيعات الاحتمالية سيكون التوزيع الذي يحتوي على N بالكامل!التباديل المحتملة للمدخلات من المرجح على قدم المساواة.بعد ذلك، متوسط ​​وقت تشغيل الحالة هو متوسط ​​وقت التشغيل على جميع المدخلات الممكنة، مرجحًا باحتمالية كل إدخال.

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

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

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

Answer 3

<اقتباس فقرة>   

وO (1) يعني وقت ثابت والفضاء (عادة) ثابتة

وفقط لتوضيح هذه بيانين منفصلين. هل يمكن أن يكون O (1) في الوقت المناسب ولكن O (ن) في الفضاء أو أيا كان.

<اقتباس فقرة>   

هل يعترف أنه حتى O (1) يمكن أن تكون كبيرة بشكل غير مرغوب فيه، على الرغم من شبه ثابت؟

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

وO () تدوين هو مقياس لمدى تعقيد - ليست المرة سوف خوارزمية تتخذ، أو إجراء نقية من كيف "جيدة" خوارزمية معينة هي لغرض معين

Answer 4

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

• تم تصميم وظيفة التجزئة بشكل معقول لتجنب عدد كبير من الاصطدامات.
• يتم توزيع مجموعة المفاتيح بشكل عشوائي إلى حد كبير، أو على الأقل لم يتم تصميمها بشكل مقصود لجعل وظيفة التجزئة تؤدي أداءً سيئًا.

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

Answer 5

جداول التجزئة عبارة عن بنية بيانات تدعم البحث والإدراج O(1).

عادةً ما يحتوي جدول التجزئة على زوج من المفاتيح والقيمة، حيث يكون يتم استخدام المفتاح كمعلمة لوظيفة (a دالة تجزئة) والتي ستحدد موقع القيمة في بنية البيانات الداخلية الخاصة بها, ، عادة مصفوفة.

نظرًا لأن الإدراج والبحث يعتمد فقط على نتيجة دالة التجزئة وليس على حجم جدول التجزئة أو عدد العناصر المخزنة، فإن جدول التجزئة يحتوي على إدراج وبحث O(1).

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

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

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

---

دعونا نلقي نظرة على مثال.دعونا نستخدم جدول التجزئة لتخزين ما يلي (key, value) أزواج:

• (Name, Bob)
• (Occupation, Student)
• (Location, Earth)

سنقوم بتنفيذ الواجهة الخلفية القابلة للتجزئة مع مجموعة من 100 عنصر.

ال key سيتم استخدامه لتحديد عنصر من المصفوفة لتخزين (key, value) زوج.ومن أجل تحديد العنصر، hash_function سوف يستخدم:

• hash_function("Name") عائدات 18
• hash_function("Occupation") عائدات 32
• hash_function("Location") عائدات 74.

من النتيجة أعلاه، سنقوم بتعيين (key, value) أزواج في عناصر المصفوفة.

array[18] = ("Name", "Bob")
array[32] = ("Occupation", "Student")
array[74] = ("Location", "Earth")

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

وبالمثل، فإن البحث عن عنصر يستخدم وظيفة التجزئة.

إذا أردنا البحث عن المفتاح "Name", ، سنقوم بإجراء hash_function("Name") لمعرفة العنصر الذي توجد به القيمة المطلوبة في المصفوفة.

كما أن البحث لا يعتمد على حجم جدول التجزئة ولا على عدد العناصر المخزنة، وبالتالي عملية O(1).

كل شيء على ما يرام.دعونا نحاول إضافة إدخال إضافي لـ ("Pet", "Dog").ومع ذلك، هناك مشكلة، كما hash_function("Pet") عائدات 18, ، وهو نفس التجزئة لـ "Name" مفتاح.

لذلك، سنحتاج إلى حل تضارب التجزئة هذا.لنفترض أن وظيفة حل تصادم التجزئة التي استخدمناها وجدت أن العنصر الفارغ الجديد هو 29:

array[29] = ("Pet", "Dog")

نظرًا لوجود تصادم تجزئة في هذا الإدراج، لم يكن أدائنا تمامًا O(1).

ستظهر هذه المشكلة أيضًا عندما نحاول البحث عن ملف "Pet" المفتاح، كمحاولة العثور على العنصر الذي يحتوي على "Pet" المفتاح عن طريق الأداء hash_function("Pet") سيعود دائمًا 18 في البداية.

عندما نبحث عن العنصر 18، سنجد المفتاح "Name" بدلا من "Pet".عندما نجد هذا التعارض، سنحتاج إلى حل التصادم من أجل استرداد العنصر الصحيح الذي يحتوي على العنصر الفعلي "Pet" مفتاح.يعد حل تصادم التجزئة عملية إضافية تجعل جدول التجزئة لا يعمل في وقت O(1).

Answer 6

لا أستطيع أن أتكلم لمناقشات أخرى كنت قد رأيت، ولكن هناك واحد على الأقل خوارزمية التجزئة أن <م> هو يضمن أن تكون O (1).

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

والعقل لك، هذا على افتراض calcuation التجزئة هو O (1) كذلك. هل يمكن القول أن سلاسل طول-K، أي تجزئة لO إلى حد أدنى (K). في الواقع، يمكنك ملزمة K بسهولة جدا، ويقول K <1000. O (K) ~ = O (1) لK <1000.

Answer 7

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

وعندما يقول أحد أن خوارزمية يأخذ O (ن) الوقت، فهذا يعني أن وقت التشغيل لأسوأ حالة خوارزمية يعتمد خطيا على حجم المدخلات المحددة.

عند يأخذ خوارزمية O (1) وقت، والشيء الوحيد الذي يعني أنه، نظرا لوظيفة T) و (الذي يحسب وقت التشغيل من الدالة f (ن)، ويوجد الطبيعي عدد ك إيجابي بحيث T (و) <ك عن أي مساهمة ن. أساسا، وهو ما يعني أن الحد الأعلى لوقت التشغيل خوارزمية لا تعتمد على حجمها، ولها، حد ثابت محدود.

والآن، وهذا لا يعني بأي حال من الأحوال أن الحد الأقصى هو صغير، أن مجرد انها مستقلة عن حجم المدخلات المحددة. حتى لو كنت مصطنع تحديد ك المنضم لحجم مجموعة البيانات، ثم تعقيدها يكون O (ك) == O (1).

وعلى سبيل المثال، والبحث عن مثيل قيمة على قائمة مرتبطة هو O (ن) عملية. ولكن إذا قلت أن قائمة يحتوي على 8 عناصر على الأكثر، ثم O (ن) يصبح O (8) لتصبح O (1).

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

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

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

Answer 8

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

Answer 9

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

---

لإجابة لماذا هذا هو ذات الصلة: وOP سئل عن السبب O (1) يبدو أن القيت حول ذلك عرضا عندما تكون في ذهنه أنه من الواضح أنه لا يمكن أن تطبق في كثير من الظروف. هذه الإجابة ويوضح ان O (1) الوقت من الممكن حقا في تلك الظروف.

Answer 10

إن تطبيقات جدول التجزئة ليست قيد الاستخدام "بالضبط" O(1)، إذا قمت باختبار واحدة فستجد أنها في المتوسط ​​حوالي 1.5 عملية بحث للعثور على مفتاح معين عبر مجموعة بيانات كبيرة

(بسبب حقيقة الاصطدامات يفعل تحدث، وعند الاصطدام، يجب تعيين موقع مختلف)

أيضًا، من الناحية العملية، يتم دعم HashMaps بمصفوفات ذات حجم أولي، يتم "تنميته" لمضاعفة الحجم عندما يصل إلى 70% من الامتلاء في المتوسط، مما يوفر مساحة معالجة جيدة نسبيًا.بعد الامتلاء بنسبة 70%، تنمو معدلات الاصطدام بشكل أسرع.

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

في الواقع، هناك طريقة واحدة فقط للحصول على "جدول تجزئة مثالي" باستخدام O(1)، وهذا يتطلب:

1. مولد مفتاح التجزئة المثالي العالمي
2. مساحة معالجة غير محدودة.

( حالة استثناء:إذا كان بإمكانك حساب جميع التباديلات للمفاتيح المسموح بها للنظام مسبقًا، وتم تحديد مساحة عنوان مخزن الدعم المستهدف الخاص بك على أنها الحجم الذي يمكنه الاحتفاظ بجميع المفاتيح المسموح بها، فيمكنك الحصول على تجزئة مثالية، ولكنها الكمال "المجال المحدود")

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

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

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

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

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

Answer 11

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

Answer 12

نعم، يؤثر جمع البيانات المهملة على التعقيد المقارب للخوارزميات التي تعمل في ساحة تجميع البيانات المهملة.ولا يخلو الأمر من التكلفة، ولكن من الصعب جدًا تحليله بدون الأساليب التجريبية، لأن تكاليف التفاعل ليست تركيبية.

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

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

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

علاوة على ذلك، ما هو أبعد من النسخ مقابل النسخ.المدمجة مقابلفي حالة وضع علامة واكتساح، يمكن أن تؤثر تفاصيل التنفيذ بشكل كبير على التعقيدات الناتجة:

1. جامعو القمامة المتزايدون الذين يتتبعون الأجزاء القذرة، وما إلى ذلك.يمكن أن يؤدي ذلك إلى اختفاء عمليات إعادة الاجتياز الكبيرة هذه.
2. يعتمد ذلك على ما إذا كان GC الخاص بك يعمل بشكل دوري بناءً على وقت ساعة الحائط أو يعمل بما يتناسب مع عدد التخصيصات.
3. ما إذا كانت خوارزمية نمط العلامة والاجتياح متزامنة أو توقف العالم
4. سواء أكان يميز المخصصات الطازجة باللون الأسود إذا تركها بيضاء حتى يسقطها في وعاء أسود.
5. ما إذا كانت لغتك تقبل تعديلات المؤشرات أم لا، فهذا قد يسمح لبعض جامعي البيانات المهملة بالعمل في مسار واحد.

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

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

Answer 13

واعتقد انه عندما رمي كثير من الناس في جميع أنحاء مصطلح "O (1)" لديهم ضمنا في الاعتبار "صغيرة" ثابت، بأي وسيلة كانت "صغيرة" في سياقها.

وعليك أن تأخذ كل هذا التحليل كبير-O مع السياق والحس السليم. ويمكن أن يكون أداة مفيدة للغاية أو أنه يمكن أن يكون مثير للسخرية، اعتمادا على كيفية استخدامه.