كتب characteristics and limits
اذا لم تجد ما تبحث عنه يمكنك استخدام كلمات أكثر دقة.
خصائص وحدود (معلومة)
ان معامل الكفاءة الخاص بخوارزمية اختبار الخاصية هو تعقيد التساؤل، وهو الحد الأقصى لعدد رموز المدخلات المعاينة على جميع المدخلات محددة الطول (وجميع الاختيارات العشوائية بواسطة الخوارزمية). وتصميم الخوارزميات ذات تعقيد التساؤل الصغير هو شيء ممتع. في كثير من الحالات يكون وقت عمل خوارزميات اختبار الخاصية فرعية الخط في طول الاقتراح. وعادة، فان الهدف الأول هو جعل تعقيد التساؤل في أصغر حجم ممكن كوظيفة اقتراح حجم n، ومن ثم دراسة الاعتماد على معامل ε.
وبعكس إعدادات التعقيدات النظرية الأخرى، يتأثر مقارب تعقيد التساؤل لخوارزميات اختبار الخاصية بشكل كبير بطريقة تمثيل الاقتراحات. فعلى سبيل المثال، عندما يكون ε= 0.01، تُدخِل مشكلة اختبار انقسام الرسوم البيانية المتراكمة (التي تمثلها المصفوفات المتصلة) خوارزمية ذات تعقيد تساؤل ثابت. وفي المقابل، تتطلب الرسوم البيانية المتناثره على القمم n (التي تمثلها قائمة متصلة) خوارزميات اختبار خاصية ذات تعقيد تساؤل .
تعقيد التساؤل في خوارزميات اختبار الخاصية ينمو كلما صغر معامل التقارب ε لجميع الخصائص الغير عادية. وهذا الاعتماد على ε ضروري حيث أن التغيير في أقل من ε من الرموز في المدخلات لا يمكن الكشف عنه مع احتمال ثابت باستخدام عدد أقل من الاستعلامات O(1/ ε). ويمكن اختبار العديد من خصائص الرسوم البيانية الكثيفة المثيرة للاهتمام عن طريق استخدام تعقيد تساؤل يعتمد فقط على ε وليس على حجم الرسم البياني n. ومع ذلك، فيمكن أن تنمو تعقيد التساؤل بسرعة هائلة كوظيفة ε. وعلى سبيل المثال، كانت أفضل خوارزمية معروفة لوقت طويل لاختبار ما إذا كان الرسم البياني لا يحتوي على مثلث كان لديه تعقيد تساؤل والذي كان في شكل دالة برجية poly(1/ε)، وفقط في عام 2010 تم تحسينه إلى دالة برجية log(1/ε).
