books الوقت الخطي
If you do not find what you're looking for, you can use more accurate words.
الوقت الخطي (Info)
يقال أن الخوارزمية تأخذ الزمن الخطي ، أو زمن O ( n ) ، إذا كان تعقيد وقتها O ( n ). بشكل غير رسمي، هذا يعني أنه بالنسبة لأحجام الإدخال الكبيرة الكافية، يزيد وقت التشغيل بشكل خطي مع حجم الإدخال. على سبيل المثال، يتطلب الإجراء الذي يضيف جميع عناصر القائمة وقتًا يتناسب مع طول القائمة. هذا الوصف غير دقيق بعض الشيء، نظرًا لأن وقت التشغيل يمكن أن يحيد بشكل كبير عن التناسب الدقيق، خاصة بالنسبة للقيم الصغيرة لـ n .
الوقت الخطي هو أفضل تعقيد زمني ممكن في الحالات التي تكون فيها الخوارزمية بحاجة إلى قراءة مدخلاتها بالكامل بشكل تسلسلي. لذلك، تم استثمار الكثير من الأبحاث في اكتشاف الخوارزميات التي تعرض زمنًا خطيًا، أو على الأقل، زمنًا تقريبيًا تقريبًا. يتضمن هذا البحث كلاً من أساليب البرمجيات والأجهزة. هناك العديد من تقنيات الأجهزة التي تستغل التوازي لتقديم هذا. على سبيل المثال هو الذاكرة المحتوى - عنونة . ويستخدم هذا مفهوم الزمن الخطي في خوارزميات مطابقة السلسلة مثل بوير مور خوارزمية وخوارزمية Ukkonen ل.
