كتب الوقت الفرعي الخطي
اذا لم تجد ما تبحث عنه يمكنك استخدام كلمات أكثر دقة.
الوقت الفرعي الخطي (معلومة)
يقال أن الخوارزمية تعمل في الزمن الفرعي الخطي (في كثير من الأحيان وقت الخيط الفرعي ) إذا كانت T ( n ) = o ( n ). ويشمل ذلك على وجه الخصوص الخوارزميات مع التعقيدات الزمنية المحددة أعلاه، بالإضافة إلى خوارزميات أخرى مثل خوارزمية بحث Grover O ( n ½ ) .
تستخدم الخوارزميات النموذجية الدقيقة والتي يتم تشغيلها في وقت فرعي خطي المعالجة المتوازية (كما يفعل حساب محدد مصفوفة NC 1 ) ، والمعالجة غير الكلاسيكية (كما يفعل بحث Grover) ، أو بدلاً من ذلك لديها افتراضات مضمونة على هيكل الإدخال (مثل لوغاريتمي الوقت البحث الثنائي والعديد من خوارزميات صيانة شجرة تفعل). ومع ذلك، قد تعتمد اللغات الرسمية مثل مجموعة جميع السلاسل التي تحتوي على 1 بت في الموضع المشار إليه من البتات log (n) الأولى من السلسلة على كل جزء من المدخلات وبعد أن تكون قابلة للحساب في الزمن الفرعي الخطي.
عادةً ما يتم حجز خوارزمية الوقت تحت الخطي محددة الخوارزميات التي تختلف عن ما سبق في أنها تعمل على نماذج الآلات التسلسلية الكلاسيكية ولا يُسمح بها افتراضات مسبقة على المدخلات. ومع ذلك يسمح لهم أن تكون عشوائية، بل يجب أن تكون عشوائية للجميع ولكن أكثر المهام تافها.
على هذا النحو، يجب أن توفر الخوارزمية إجابة دون قراءة المدخلات بأكملها، وتعتمد بياناتها بشكل كبير على الوصول المسموح به إلى المدخلات. عادة للمدخلات التي يتم تمثيلها كسلسلة ثنائية b 1 ،... ، b k يفترض أن الخوارزمية يمكن في الوقت المناسب طلب O (1) والحصول على قيمة b i لأي i .
خوارزميات الوقت شبه الخطية عادة ما تكون عشوائية، وتوفر حلول تقريبية فقط. في الواقع، يمكن بسهولة إثبات خاصية الخيط الثنائي التي تحتوي على أصفار فقط (ولا توجد أصفار) على أنها غير قابلة لضبطها بواسطة خوارزمية وقتية فرعية (غير تقريبية). تنشأ خوارزميات الوقت شبه الخطية بشكل طبيعي في التحقيق في اختبار الملكية .
