تعقيد الوقت / نظرية الرسم البياني

Question

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

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

أنا جديد على نظرية الرسم البياني لذلك لا أعرف ما إذا كانت طريقة تفكيري صحيحة.بعض النصائح ستكون كبيرة.

شكرا

Answer 1

الشرح O (م) هو الصحيح.

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

a) لماذا insertvertex هو O (1)؟

إدراج Vertex مجرد إلغاء عقدة إلى قائمة مرتبطة (O (1)) أو 2 إذا كان الرسم البياني غير مجفف.

b) لماذا deletevertex هو O (م)؟

حذف الوسائل السيرمة:

1) حذف قائمة مرتبطة (O (1))

2) في أسوأ الحالات، سيتعين عليك إزالة قمة الرأس من جميع القوائم المرتبطة: O (م).إنه O (م) يسبب عدد العقد في جميع القوائم المرتبطة هو M، أو 2 * م إذا كان الرسم البياني غير مريض.

Answer 2

يأخذ Insertvertex س (1) لأنك تضيف عنصر جديد فقط إلى نهاية بنية البيانات الخاصة بك.

deletevertex يأخذ o (m) لأنه مقابل كل حافة، يجب عليك التحقق مما إذا كانت الحافة تشير إلى أو يشير بعيدا (إذا تم توجيه G) من Vertex. يبدو أنك حصلت على الفكرة، وقراءة المرجع الخاص بك.