تحليل الخاص ديكسترا الخوارزمية (كسول) إدارة الوقت

Question

أنا في محاولة لمعرفة وقت تشغيل على الخاص ديكسترا الخوارزمية.جميع مصادر قرأت نقول أن تشغيل الوقت O(E * log (هـ)) عن كسول التنفيذ.

ولكن عندما نفعل الرياضيات نصل O(E * (Log(E)+E*Log(E))).

منذ E ليس ثابت, أنا لا أرى كيف يمكن الحد من هذا يا(E * log (E).

نحن تحليل خاطئ أو هل من الممكن للحد من ؟

        while (!minPQ.isEmpty()) { <=== O(E)
            Node min = minPQ.poll(); <=== O(log(e)

            for (Edge edge : graph.adj(min)) { <=== O(E)
                if (min.getId() == target.getId()) {
                    // Source and Target = Same edge
                    if (edgeTo.size() == 0) edgeTo.put(target, edge);

                    return;
                }

                relax(edge, min, vehicle); <=== log(e) (because of add method on PQ)
            }
      }

Answer 1

أولا, يمكنك جعل بعض حدود تشديد قليلا واستبدال بعض $E$s مع $V$s.في حين حلقة في بداية سيتم تشغيل فقط $O(|V|)$ التكرار (تزورها كل عقدة مرة واحدة فقط) ، for (Edge edge : graph.adj(min)) حلقة سيتم تشغيل فقط $O(|V|)$ التكرار في أكثر من (عقدة يمكن أن يكون على الأكثر $O(|V|)$ المتاخمة حواف).نفسه مع السجل العوامل ، على الرغم من أن في هذه الحالة لا يهم بقدر منذ $O(\log |V|) = O(\log |ه|)$ (إذا كان الرسم البياني متصل).عبر الضرب البسيط هذا يعطيك $O(|V| \cdot (\log |V| + |V| \cdot \log |V|)) = O(|V|^2 \cdot \log |V|)$.في الرسم البياني كثيفة ، وهذا هو بالفعل المطلوب التعقيد.منذ كثيفة الرسم البياني $O (V^2) = س(|ه|)$.

ومع ذلك في متفرق الرسم البياني ، على سبيل المثالعندما $O(|ه|) = O(|V|)$, ثم يمكنك لا تزال تفعل الكثير أفضل.

المشكلة التي تواجهها هو ضرب الحدود العليا يمكن أن يؤدي إلى المبالغة.أنظر إلى المثال التالي:

for (i = 1 to N) {
    limit = N if i == 1 else 1
    for (j = 1 to N) {
        constant_work()
    }
}

الحلقة الخارجية من الواضح يعمل $O(N)$ مرات, و الحلقة الداخلية يعمل أيضا $O(N)$ مرات (لأنه في أسوأ الأحوال لا).هل يمكن القول أن في المجموع التعقيد $O(N^2)$ مرات.ولكن هذا هو فقط الحد الأعلى.

معظم الوقت وظيفة الداخلية في الواقع لا يكاد أي عمل.في الواقع إذا كنت احسب عدد مرات تشغيل وظيفة constant_work(), سوف تحصل على $$N + 1 + 1 + \cdots + 1 = 2N - 1 = O(N)$$ $N$ التكرار for i == 1 وإلا فقط $1$ التكرار.حتى يتم تشغيل التعليمات البرمجية في $O(N)$ الوقت.

نفس التأثير يحدث عند حلقة على حواف المقبل إلى عقدة: for (Edge edge : graph.adj(min)).نعم, في أسوأ الأحوال لديك $O(|V|)$ الحواف, ولكن في متفرق الرسم البياني ، معظم الوقت لديك الكثير أقل.

يمكنك الاعتماد عليها من زاوية مختلفة.إذا كنت تركز على حافة $(u, v)$, كيف وغالبا ما كنت تلمس حافة والانتقال إلى الجسم من الحلقة ؟ مرتين فقط!مرة واحدة عندما min == u, و مرة واحدة عند min == v.لذلك الجزء الداخلي من الحلقة ، مع وقت التشغيل $O(\log |V|)$, ، سيتم تشغيل فقط $O(2 |ه|) = O(|ه|)$ مرات.وهو ما يعني أن كل شيء يعمل في $O(|ه| \log |V|)$.

Answer 2

تحليلك صحيح، ولكن ليس ضيقا.

بدلا من النظر في حلقة أثناء الحلقة والحلقة بشكل منفصل، فمن الأفضل أن تعتبرها معا.يعمل الهيئة الداخلية للحلقة الداخلية مرة واحدة لكل (قمة الرأس، زوج)، لإجمالي 2 دولار | E | $ Times.لذلك، فإن إجمالي وقت التشغيل من جميع عمليات الاسترخاء هو فقط $ O (| e | \ log | E | $ ).

إجمالي وقت التشغيل لجميع عمليات الاستطلاع هو أيضا $ O (| E | \ Log | E |) $ ، كما تراقب أيضا، ونحن نستنتج ذلكإجمالي وقت التشغيل هو $ O (| E | \ Log | E |) $ .