لماذا إدراج في منتصف قائمة مرتبطة O(1)?
https://stackoverflow.com/questions/840648
-
20-08-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
Russianسؤال
وفقا مقالة ويكيبيديا على القوائم المرتبطة, وإدراج في منتصف قائمة مرتبطة يعتبر O(1).أعتقد أنه سيكون O(n).لن تحتاج إلى تحديد موقع العقدة التي يمكن أن تكون قرب نهاية القائمة ؟
هل هذا التحليل يتم العثور على العقدة العملية (على الرغم من أنه مطلوب) فقط الإدراج نفسها ؟
تحرير:
القوائم المرتبطة لديها العديد من المزايا أكثر من المصفوفات.إدراج عنصر في نقطة محددة من قائمة ثابت-وقت التشغيل ، بينما الإدراج في مجموعة قد تتطلب الانتقال من نصف العناصر أو أكثر.
البيان أعلاه هو قليلا مضللة لي.تصحيح لي إذا كنت مخطئا, ولكن أعتقد أن الاستنتاج يجب أن يكون:
المصفوفات:
- العثور على نقطة الإدراج/حذف O(1)
- أداء إدراج/حذف O(n)
القوائم المتصلة:
- العثور على نقطة الإدراج/حذف O(n)
- أداء إدراج/حذف O(1)
اعتقد ان الوقت لن يكون لديك للعثور على الموقف إذا حافظت على نوع من مؤشر إلى ذلك (كما هو الحال مع الرأس والذيل في بعض الحالات).لذلك نحن لا يمكن أن رفضا قاطعا القول بأن القوائم المرتبطة دائما ضرب المصفوفات إدراج/حذف الخيارات.
المحلول
كنت على صواب ، المادة تعتبر "الفهرسة" كعملية منفصلة.لذا الإدراج هو في حد ذاته O(1) ، ولكن الحصول على هذا الوسط عقدة O(n).
نصائح أخرى
الإدراج في حد ذاته هو O(1).عقدة إيجاد O(n).
لا, عندما كنت قررت أن كنت ترغب في إدراج انه يفترض كنت بالفعل في منتصف بالتكرار من خلال القائمة.
العمليات على القوائم المرتبطة في كثير من الأحيان القيام به في مثل هذه الطريقة أنها ليست حقا يعامل عامة "قائمة" ، ولكن مجموعة من العقد ... اعتقد من العقدة نفسها مكرر على حلقة الرئيسية الخاصة بك.حتى كنت بدس من خلال قائمة لاحظت كجزء من الأعمال التجارية الخاصة بك المنطق أن عقدة جديدة يحتاج إلى إضافة (أو قديمة حذف) وأنت تفعل ذلك.يمكنك إضافة 50 العقد في واحدة التكرار و كل تلك العقد هو فقط س(1) الوقت إلى ربط اثنين المتاخمة العقد إدخال واحدة جديدة..
تحرير:يا رجل اكتب فقرة ثانية وفجأة بدلا من أن يكون المستجيب الأول أنك 5 يقول نفس الشيء مثل أول 4!
لأغراض مقارنة مع مجموعة ، وهو ما يظهر على الرسم البياني ، فمن س(1) لأنه ليس لديك لنقل كافة العناصر بعد عقدة جديدة.
لذا نعم, هم على افتراض أن لديك بالفعل مؤشر إلى أن عقدة ، أو أن الحصول على المؤشر تافهة.وبعبارة أخرى, ذكر المشكلة:"نظرا عقدة في X, ما هو كود لإدراج بعد هذه العقدة?" يمكنك البدء في إدراج نقطة.
الإدراج في قائمة مرتبطة يختلف بالتكرار عبر ذلك.كنت لا تحديد البند ، يتم إعادة مؤشرات إلى وضع هذا البند في هناك.لا يهم إذا كان الذهاب إلى إدراج بالقرب من الواجهة الأمامية أو قرب نهاية الإدراج لا يزال ينطوي على مؤشرات واحدا.سوف تعتمد على كيفية تنفيذه ، بالطبع ، ولكن هذا هو قوة قوائم - يمكنك بسهولة.الوصول عن طريق المؤشر حيث مجموعة يضيء.للحصول على قائمة ، ومع ذلك ، فإنه سوف يكون عادة O(n) للعثور على أقصى البند.على الأقل هذا ما أتذكره من المدرسة.
لأنها لا تنطوي على أي حلقات.
إدراج مثل:
- إدراج عنصر
- الرابط السابق
- الرابط التالي
- به
هذا هو وقت ثابت في أي حال.
وبالتالي إدخال عناصر n واحدة بعد الأخرى O(n).
هل هذا التحليل يتم العثور على العقدة العملية (على الرغم من أنه مطلوب) فقط الإدراج نفسها ؟
كنت حصلت عليه.الإدراج في نقطة معينة يفترض أن كنت تحمل بالفعل مؤشر إلى العنصر الذي تريد إدراج بعد:
InsertItem(item * newItem, item * afterItem)
إدراج O(1) بمجرد أن تعرف أين أنت ذاهب لوضعها.
لا, لأنها لا تأخذ في الاعتبار البحث.ولكن إذا كان لديك بالفعل على عقد من مؤشر إلى عنصر في منتصف قائمة إدراج في هذه النقطة O(1).
إذا كان لديك للبحث عن ذلك ، يجب أن تضيف على الوقت للبحث ، والتي ينبغي O(n).
مقالة حول المقارنة بين المصفوفات مع القوائم.العثور على إدراج موقف كل من المصفوفات والقوائم O(N) ، وبالتالي فإن المادة يتجاهل ذلك.
س(1) اعتمادا على حقيقة أن لديك هذا البند حيث سيتم إدراج عنصر جديد.(قبل أو بعد).إذا كنت لا ، O(n) لأنه يجب أن تجد هذا البند.
اعتقد انها مجرد حالة ما اخترت عد س() التدوين.في حالة إدراج التشغيل العادي إلى عدد نسخ العمليات.مع مجموعة, إدراج في منتصف ينطوي على نسخ كل شيء فوق موقع في الذاكرة.مع قائمة مرتبطة ، يصبح هذا الإعداد اثنين من المؤشرات.تحتاج إلى العثور على الموقع بغض النظر عن ما لإدراج.
إذا كان لديك مرجع من عقدة إلى إدراج بعد العملية O(1) على قائمة مرتبطة.
على مجموعة من أنه لا يزال O(n) حيث لديك لنقل كل consequtive العقد.
الحالات الأكثر شيوعا هي على الأرجح إدراج في بداية أو في نهاية القائمة (وينتهي من القائمة قد لا تأخذ من الوقت للعثور على).
على النقيض من ذلك مع إدراج بنود في بداية أو نهاية الصفيف (الذي يتطلب تغيير حجم الصفيف إذا كان في نهاية المطاف ، أو تغيير حجم ونقل جميع العناصر إذا كان في البداية).
