لماذا إدراج في نهاية مجموعة ديناميكية O(1) حين إدراج في منتصف O(n)?

Question

وبناء على ذلك إلى مقالة ويكيبيديا عن صفائف ديناميكية, إدراج/حذف في نهاية الصفيف O(1) حين إدراج/حذف من وسط O(n).لماذا هو بالتحديد ؟

أيضا - إذا كان لدي مجموعة ديناميكية مع 5 عناصر و أنا أدخل عنصرا جديدا في موقف 6 العملية O(n) بينما إذا كنت تستخدم وظيفة إلحاق نهاية الصفيف ومن O(1).أليس هذا نفس العملية على افتراض مجموعة لا تحتاج إلى تغيير في أي من هذه القضية ؟ أو إلحاق إلى صفيف حيوية حقا إدراج عنصر جديد في مكان ما إلى جانب موقف 6?

وذلك بفضل!

تحرير: أعتقد الرئيسية الارتباك هو الفرق بين إدخال في نهاية مجموعة وإدراج في موقف معين يعادل نهاية الصفيف.

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

Answer 1

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

Answer 2

لإدراج في نهاية صفيف ، عليك ببساطة أن وضع هذا البند هناك.

لإدراج إلى منتصف صفيف ، تحتاج إلى نقل العناصر بعد هذه النقطة من قبل.

حذف من نهاية الصفيف, كنت مجرد قطرة به عدد من جانب واحد.

حذف من وسط عليك أن تفعل ذلك و تحويل عناصر أخرى إلى أسفل.

انها تحويل أن يتحول إلى O(n).

Answer 3

انها بسيطة جدا:

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

Answer 4

إضافة إلى آدم روبنسون ملخص ممتاز:هذه ليست مجرد نظرية.رأيت أي عدد من الحالات التي صفيف حيوية شيدت من قبل مرارا وتكرارا إلحاق إلى نهاية المصفوفة.هذا يعمل بها o(N**2) الأداء, لأن مجموعة مرارا وتكرارا يحتاج إلى إعادة تخصيصها ، مما اضطر كل عضو من أعضائه إلى أن يتم نسخها إلى مجموعة جديدة الهيكل.إعادة المخصصات قد يحدث فقط 1/10 من إلحاق العمليات ، ولكن هذا سيئا بما فيه الكفاية ، و لا يزال o(N**2) الحكمة.

في المحكمة الخاصة بلبنان ، هذا الأداء عقوبة يمكن تجنبها عن طريق الاتصال vector::reserve(N) قبل الكتابة في ناقلات;ولكن هذه الخطوة غالبا ما يتم تجاهله.

Answer 5

في الواقع, انها ليست كبيرة-O لكن كبير-Theta.