تعقيد الوقت للإدراج في قائمة مرتبطة

Question

الاعتذار إذا كان هذا السؤال يشعر وكأنه التحقق من الحل، ولكن تم طرح هذا السؤال في اختبار القبول في الخريجين وهناك الكثير من الركوب على هذا:

ما هو أسوأ حالة تعقيد وقت الإدراج عناصر $ N في قائمة مرتبطة فارغة، إذا كانت القائمة المرتبطة يجب الحفاظ عليها في الترتيب الفرز؟

في رأيي، يجب أن تكون الإجابة $ O (n ^ 2) $ لأنه في كل إدخال، سيتعين علينا إدراج العنصر في المكان المناسب و من الممكن إدراج كل عنصر في المكان الأخير، مما أتاح لي تعقيدا وقتا من $ 1 + 2 + ... (N-1) + N= O (N ^) 2) $

ومع ذلك، فإن الحل الذي أقوله أنه يمكننا فقط فرز العناصر في $ O (n \ log n) $ ثم، يمكننا إدراجها بواسطة واحد في $ O (n) $ (n) $ ، مع إعطا لنا تعقيدا بشكل عام من $ O (n \ log n) $ < / span>.

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

Answer 1

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

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

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

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

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

لاحظ أنه حتى في ظل هذا الافتراض، فإن التفكير الخاص بك خطأ، أو على الأقل غير دقيقة. إذا حدثت معرفة أن العناصر يتم تقديمها بالترتيب الصحيح، فيمكنك الحفاظ على مؤشر إلى ذيل القائمة، والحفاظ على إدراج هناك، والتي ستأخذ $ O (n) $ . أسوأ الحالات ليست إذا كان يجب إدخال كل عنصر في الموضع الأخير في القائمة المستهدفة، ولكن عند آخر موضع تم التوصل إليه عند تعبير القائمة بطريقة ما. أسوأ الحالات هي بالفعل $ \ theta (n ^ 2) $ ، ولكن لإثبات ذلك، عليك إثبات أن العثور على نقطة الإدراج في القائمة يأخذ $ \ theta (n) $ الوقت، وهذا يتطلب إثبات أن المسافة من أي مؤشر لديك في القائمة يحدها أدناه بواسطة $ \ أوميغا (ن) $ . هذا هو الحال إذا كان لديك رقم ثابت $ $ من المؤشرات (قمت بالفائدة الضمنيا $ A= 1 $ مع مؤشر واحد في بداية القائمة)، بحيث تحتاج إلى اجتياز $ K $ الإدراج في أسوأ الحالات.

Answer 2

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

Answer 3

هو حقا سؤال صعب.بادئ ذي بدء، ينطبق تعقيد O (NLGON) فقط على الخوارزميات التي تستخدم المقارنة بين عناصرها (خوارزمية مقارنة).توجد أيضا خوارزميات غير مقارنة مثل راديكس ترتيب تعتمد تعقيدها على الحجم في البتات التي تحتاج إلى تخزين الأرقام في الذاكرة.لذلك إذا افترضنا أننا نستطيع فرز الأرقام مسبقا بأي خوارزمية، فيمكننا أيضا أن نفترض أن الأرقام من الناطور الطبيعية والحد الأقصى هو M <10، لذلك مع راديكس فرز سوف تحصل على أسوأ الحالات O (10N)= Oن).إذا لم نتمكن من تقديم أي افتراض، فأنت على حق.إذا سمح لك فقط باستخدام قوائم مرتبطة ولا شيء أكثر (بدون فهرسة من أي نوع)، فإن التعقيد هو O (N ^ 2) (فرز الفقاعة).

Answer 4

يجب أن يكون o (n). اتبع الخوارزمية كما -

1) إذا كانت القائمة المرتبطة فارغة ثم اجعل العقدة رأس وإعادته.

2) إذا كانت قيمة العقدة للإدراج أصغر من قيمة عقدة الرأس، ثم أدخل العقدة في البداية وجعلها رأسها.

3) في حلقة، ابحث عن العقدة المناسبة بعد التي تكون عقدة المدخلات التي سيتم إدراجها.

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

4) أدخل العقدة بعد العقدة المناسبة وجدت في الخطوة 3