ما الذي يعتبر تحسينًا مقاربًا لخوارزميات الرسم البياني؟

Question

لنفترض أننا نحاول حل بعض المشاكل الخوارزمية $أ$ الذي يعتمد على إدخال الحجم $ن$.نقول خوارزمية $ب$ الذي يعمل في الوقت المناسب $T(ن)$, ، أفضل من الخوارزمية بشكل مقارب $ج$ الذي يجري في الوقت المناسب $G(ن)$ اذا كان لدينا:$G(n) = O(T(n))$, ، لكن $T(ن)$ ليس $O(G(ن))$.

سؤالي يتعلق بوقت التشغيل المقارب لخوارزميات الرسم البياني، والذي يعتمد عادةً على $|الخامس|$ و $|ه|$.على وجه التحديد أريد التركيز على خوارزمية بريم.إذا قمنا بتنفيذ قائمة انتظار الأولوية باستخدام كومة ثنائية، فسيكون وقت التشغيل كذلك $O(E\log V)$.مع كومة فيبوناتشي يمكننا الحصول على وقت تشغيل $O(V\log V + E)$.

سؤالي هو هل نقول ذلك؟ $O(V\log V + E)$ هو أفضل مقارب من $O(E\log V)$?

اسمحوا لي أن أوضح:أعلم أنه إذا كان الرسم البياني كثيفًا فإن الإجابة هي نعم.لكن اذا $E=O(V)$ كلا الحلين متماثلان.أنا مهتم أكثر بما هو عادة مُعرف كتحسين مقارب في حالة وجود أكثر من متغير واحد، والأسوأ من ذلك - أن المتغيرات ليست مستقلة ($V-1\le E<V^2$, ، نظرًا لأننا نفترض أن الرسم البياني متصل بخوارزمية Prim).

شكرًا!

Answer 1

التعريف الأكثر تساهلاً هو كما يلي.

لنفترض أن $f(V,E),g(V,E)$ هما وقتان تشغيل لخوارزميات الرسم البياني لحل نفس المشكلة.

نحن نقول ذلك $و$ هو تحسن مقارب في بعض النظام على $ز$ إذا كان هناك تسلسل $V_n,E_n$ مع $V_n o \infty$ مثل ذلك$$

في بعض الأحيان لا يعتبر النظام مثيرا للاهتمام، ولكن هذا أمر أكثر ذاتية.

لاحظ أيضًا أن المشكلة تظهر بالفعل بالنسبة للوظائف ذات المتغير الواحد.يعتبر$$ f(n) = n^2, \qquad g(n) = \begin{cases} 2^n &\text{if } n = 2^m, \\ n & \text{otherwise}. \end{cases} $$يكون $و$ تحسن مقارب $ز$؟إنه مخصص للمدخلات ذات طول معين، وهو بالفعل كذلك بموجب تعريفنا المسموح به أعلاه.