O (M + N) خوارزمية لاستيفاء خطي

Question

مشكلة

المعطى البيانات التي تتكون من $ n $ تنسق $ \ left ((x_1، y_1)، (x_2، y_2) ، \ Ldots، (x_n، y_n) \ right) $ مرتبة حسب $ x $ -Values، و $ m $ نقاط الاستعلام الفرز $ (q_1، q_2، \ ldots، q_m) $ ، ابحث عن القيم المحمولة الخطية نقاط الاستعلام وفقا ل البيانات. نحن نفترض $ q_i \ in (\ min_j x_j، \ max_j x_j) $

سمعت خارج ناحية أن هذه المشكلة يمكن حلها في $ o (m + n) $ الوقت ولكن يمكن أن تفكر فقط في $ o (m \ log n) $ الخوارزمية. لا أستطيع أن أجد هذه المشكلة بالذات في أي من كتب الخوارزمية.

الخوارزمية Linegeritmic

giveacodicetagpre.

يعطينا وقت تشغيل $ o (m \ log n) $ ، من غير الواضح بالنسبة لي كيفية الحصول على هذا إلى $ o (m + n) $ كابحث عن يجب أن تتم $ x_i $ لكل نقطة استعلام.

Answer 1

تحتاج فقط إلى إجراء بحث ثنائي عن العنصر الأول ثم تتوقع في وقت واحد من خلال نقاط البيانات ونقاط الاستعلام.

pseudocode

giveacodicetagpre.