خوارزمية في الوقت المناسب التعقيد

Question

كنت أنظر إلى دخول ويكيبيديا بالنسبة لخوارزمية PRIM ولاحظت أن تعقيد الوقت الخاص به مع مصفوفة مجاورة هو O (v ^ 2) ووقت تعقيدها مع قائمة كومة من كومة ومجاكة هو O (E LG (V)) حيث E هو عدد الحواف و V عدد القمم في الرسم البياني.

نظرا لاستخدام خوارزمية PRIM في الرسوم البيانية بأكثر كثافة، فيمكنه الاتصال v ^ 2، ولكن عندما يفعل ذلك، يصبح التعقيد الزمني مع كومة كومة O (V ^ 2 LG (V)) وهو أكبر من O (V ^ 2). من الواضح أن كومة كومة ستحسن الأداء على مجرد البحث في المجموعة، لكن تعقيد الوقت يقول خلاف ذلك.

كيف تتلاشى الخوارزمية في الواقع مع تحسن؟

Answer 1

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

في جوهرها، تتجادل السرعة في جزء واحد من خوارزمية السرعة في آخر.

بغض النظر عن ما، سيكون عليك البحث في مرات N. ومع ذلك، في الرسوم البيانية الكثيفة، ستحتاج إلى تحديث الكثير (~ v ^ 2)، وفي الرسوم البيانية المتنزعة، أنت لا تفعل ذلك.

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

Answer 2

من مقدمة الخوارزميات (كارمن)

الوقت = θ (v) · T (استخراج دقيقة) + θ (E) · T (النقص المفتاح)

 T (Extract-min) T (النقص - مفتاح) المجموع 1. صفيف O (v) O (1) O (v ^ 2) 2. Binary Heap O (LGV) O (LGV) O (LGV) O (E LGV) 3. فيبوناتشي كومة O (LGV) O (1) O (E + VLGV)

باستخدام هياكل البيانات المختلفة تسبب تعقيدات وقت مختلف.

Answer 3

أعتقد أنك تقرأ ذلك خطأ في حد ما. بالنسبة للرسوم البيانية الكثيفة، يتحدث المقال عن استخدام أكوام Fibonacci مع تعقيد الوقت O (سجل E + V)، وهو أفضل بكثير.