تعقيد الوقت

في علوم الكمبيوتر ، يعتبر تعقيد الوقت هو التعقيد الحسابي الذي يقيس أو يقدر الوقت المستغرق لتشغيل خوارزمية . عادةً ما يتم تقدير تعقيد الوقت من خلال حساب عدد العمليات الأولية التي تقوم بها الخوارزمية ، بافتراض أن العملية الأولية تستغرق وقتًا ثابتًا لأداءها. وبالتالي ، فإن مقدار الوقت المستغرق وعدد العمليات الأولية التي تقوم بها الخوارزمية يختلفان على الأكثر بعامل ثابت .
نظرًا لأن وقت تشغيل الخوارزمية قد يختلف باختلاف مدخلات من نفس الحجم ، فيحسب المرء عادة تعقيد وقت الحالة الأسوأ ، وهو أقصى مقدار من الوقت المستغرق في مدخلات حجم معين. أقل شيوعا ، وعادة ما يتم تحديده بشكل صريح ، هو تعقيد الحالة المتوسطة ، وهو متوسط الوقت المستغرق على مدخلات حجم معين (وهذا منطقي ، حيث لا يوجد سوى عدد محدود من المدخلات الممكنة من حجم معين).

في كلتا الحالتين ، يتم التعبير عن تعقيد الوقت بشكل عام كدالة لحجم المدخلات. 
بما أن هذه الوظيفة يصعب بشكل عام حسابها بالضبط ، ووقت التشغيل عادة لا يكون حرجًا بالنسبة إلى المدخلات الصغيرة ، فإن أحدهما يركز عادة على سلوك التعقيد عندما يزيد حجم المدخلات ؛ وهذا هو ، على السلوك المقارب للتعقيد. لذلك ، يتم التعبير عن تعقيد الوقت بشكل شائع باستخدام تدوين O الكبير ، عادةً ، إلخ ، حيث n هو حجم الإدخال المقاس بعدد البتات المطلوبة لتمثيله.
  بت
يتم تصنيف تعقيدات الخوارزمية بواسطة الدالة التي تظهر في تدوين O الكبير. على سبيل المثال ، خوارزمية ذات تعقيد زمني هي خوارزمية زمنية خطية ، خوارزمية مع تعقيد زمني لبعض الثابت هي خوارزمية زمن متعددة الحدود .''

وقت ثابت

ويقال أن الخوارزمية هي وقت ثابت (مكتوب أيضًا باسم O (1) ) إذا كانت قيمة T ( n ) محددة بقيمة لا تعتمد على حجم المدخلات. على سبيل المثال ، يستغرق الوصول إلى أي عنصر مفرد في صفيف وقتًا ثابتًا حيث يجب إجراء عملية واحدة فقط لتحديد موقعه. بطريقة مشابهة ، يتم العثور على القيمة الأدنى في مصفوفة مرتبة بترتيب تصاعدي ؛ هذا هو العنصر الأول. ومع ذلك ، فإن العثور على الحد الأدنى من القيمة في صفيف غير مرتبة ليس عملية زمنية ثابتة حيث يلزم إجراء مسح ضوئي فوق كل عنصر في الصفيف من أجل تحديد القيمة الأدنى.ومن ثم فهي عملية زمنية خطية تأخذ زمن O (n). إذا كان عدد العناصر معروفًا مسبقًا ولا يتغير ، فإن مثل هذه الخوارزمية يمكن أن يقال إنها تعمل في وقت ثابت.
على الرغم من الاسم "وقت ثابت" ، لا يجب أن يكون وقت التشغيل مستقلة عن حجم المشكلة ولكن يجب تقييد حد الأعلى وقت التشغيل بشكل مستقل عن حجم المشكلة. على سبيل المثال، فإن مهمة "تبادل قيم و و ب إذا لزم الأمر بحيث ل ≤ ب " ويسمى وقت ثابت على الرغم من أن الوقت قد يعتمد على ما إذا كان صحيحا أن بالفعل على ≤ ب . ومع ذلك ، هناك بعض t مثل ثابت أن الوقت المطلوب هو دائما على الأكثر  t .
int index = 5؛
int item = list [index]؛
إذا (شرط صحيح) ثم
   تنفيذ بعض العمليات التي تعمل في وقت ثابت
آخر
   تنفيذ بعض العمليات الأخرى التي تعمل في وقت ثابت
ل i = 1 إلى 100
    لـ j = 1 to 200
      تنفيذ بعض العمليات التي تعمل في وقت ثابت
إذا كانت T ( n ) هي O ( أي قيمة ثابتة ) ، فهذا يعادل ويقال في الترميز القياسي على أنه T ( n ) يجري O (1).

وقت لوغاريتمي

ويقال إن الخوارزمية تأخذ وقت لوغاريتمي إذا كانت T ( n ) = O (log n ) . نظرًا لاستخدام نظام الأرقام الثنائي بواسطة أجهزة الكمبيوتر ، فإن اللوغاريتم يكون في الغالب أساسًا 2 (أي log ₂  n ، وأحيانًا مكتوبة lg n ). ومع ذلك، من خلال تغيير قاعدة لوغاريتمات، تسجيل و  ن وتسجيل ب  ن تختلف فقط من قبل مضاعف المستمر، والتي كبير-O يتم تجاهل التدوين. وهكذا يا (سجل ن) هو الترميز القياسي لخوارزميات الوقت اللوغاريتية بغض النظر عن أساس اللوغاريتم.
الخوارزميات التي تأخذ الوقت اللوغاريتمي موجودة بشكل شائع في العمليات على الأشجار الثنائية أو عند استخدام البحث الثنائي .
تعتبر خوارزمية O (log n) عالية الكفاءة ، حيث تقل نسبة عدد العمليات إلى حجم المدخلات وتميل إلى الصفر عندما تزيد n . الخوارزمية التي يجب أن تصل إلى كل عناصر مدخلاتها لا يمكن أن تستغرق وقت لوغاريتمي ، لأن الوقت المستغرق لقراءة مدخلات بالحجم n يكون بترتيب n .

يتم إعطاء مثال على الوقت اللوغاريتمي عن طريق البحث في القاموس. دعنا نفكر في قاموس يحتوي على مداخل n ، مرتبة حسب الترتيب الأبجدي . نحن نفترض أنه ، بالنسبة لـ 1 ≤ k ≤ n
1 ≤ k ≤ n، يمكن للمرء الوصول إلى دخول ال k من القاموس في وقت ثابت. دعونا D[k] دلالة هذا ك دخول عشر. بموجب هذه الفرضيات ، يمكن إجراء الاختبار إذا كانت الكلمة D في القاموس في زمن لوغاريتمي: فكر في المكان الذي يشير إلى دالة الكلمة . إذا تم الانتهاء من ذلك. عدا ذلك ، إذا استمر البحث بنفس الطريقة في النصف الأيسر من القاموس ، وإلا استمر بالمثل مع النصف الأيمن من القاموس. تشبه هذه الخوارزمية الطريقة المستخدمة غالبًا للعثور على إدخال في قاموس ورقي.دالتا الجزء الصحيح و السقف

الوقت polylogarithmic

ويقال إن الخوارزمية تعمل في زمن 'polylogarithmic' إذا كانت T ( n ) = O ((log n ) ᵏ ) ، لبعض k الثابت . على سبيل المثال ، يمكن حل ترتيب سلسلة المصفوفات في وقت polylogarithmic على جهاز الوصول العشوائي الموازي .

الوقت الفرعي الخطي

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

الوقت الخطي

يقال أن الخوارزمية تأخذ الزمن الخطي ، أو زمن O ( n ) ، إذا كان تعقيد وقتها O ( n ). بشكل غير رسمي ، هذا يعني أنه بالنسبة لأحجام الإدخال الكبيرة الكافية ، يزيد وقت التشغيل بشكل خطي مع حجم الإدخال. على سبيل المثال ، يتطلب الإجراء الذي يضيف جميع عناصر القائمة وقتًا يتناسب مع طول القائمة. هذا الوصف غير دقيق بعض الشيء ، نظرًا لأن وقت التشغيل يمكن أن يحيد بشكل كبير عن التناسب الدقيق ، خاصة بالنسبة للقيم الصغيرة لـ n .
الوقت الخطي هو أفضل تعقيد زمني ممكن في الحالات التي تكون فيها الخوارزمية بحاجة إلى قراءة مدخلاتها بالكامل بشكل تسلسلي. لذلك ، تم استثمار الكثير من الأبحاث في اكتشاف الخوارزميات التي تعرض زمنًا خطيًا ، أو على الأقل ، زمنًا تقريبيًا تقريبًا. يتضمن هذا البحث كلاً من أساليب البرمجيات والأجهزة. هناك العديد من تقنيات الأجهزة التي تستغل التوازي لتقديم هذا. على سبيل المثال هو الذاكرة المحتوى - عنونة . ويستخدم هذا مفهوم الزمن الخطي في خوارزميات مطابقة السلسلة مثل بوير مور خوارزمية و خوارزمية Ukkonen ل .

الوقت شبه التربيعي

على سبيل المثال ، تكون خوارزميات الفرز البسيطة القائمة على المقارنة عبارة عن تربيعية (مثل فرز الإدراج ) ، ولكن يمكن العثور على خوارزميات أكثر تقدمًا وهي خوارزمية فرعية (مثل تصنيف Shell ). لا يتم تشغيل أي نوع من الأغراض العامة في وقت خطي ، ولكن التغيير من التربيعي إلى شبه التربيعي له أهمية عملية كبيرة.

وقت حافل جدا

يقال أن الخوارزمية تأخذ وقتاً حافلاً جداً إذا لم تكن T ( n ) مقيدة أعلاه بواسطة أي متعدد الحدود. وباستخدام تدوين أوميجا قليل ، يكون الوقت ω ( n ᶜ ) لجميع الثوابت c ، حيث n هي معلمة الدخل ، وهي عادة عدد البتات في المدخلات.
على سبيل المثال ، تتطلب الخوارزمية التي يتم تشغيلها لخطوتين ⁿ عند إدخال حجم n وقتًا للسوبرى الحزبية (بشكل أكثر تحديدًا ، زمنًا أسيًا).
الخوارزمية التي تستخدم موارد أسيّة هي حُرّية فائقة بشكل واضح ، لكن بعض الخوارزميات ليست سوى مجرد خوارزميات سطحية جدًّا. على سبيل المثال ، يتم تشغيل اختبار Adleman – Pomerance – Rumely البدائي لـ n  على مدخلات n -bit ؛ هذا ينمو أسرع من أي متعدد الحدود لأكبر ما يكفي من n ، ولكن يجب أن يصبح حجم المدخلات كبيرًا بشكل غير عملي قبل أن لا يمكن السيطرة عليه بواسطة كثير الحدود بدرجة صغيرة.
خوارزمية الذي يتطلب وقتا superpolynomial تكمن خارج قسم تعقيد P . تفترض أطروحة كوبهام أن هذه الخوارزميات غير عملية ، وفي العديد من الحالات. نظرًا لأن مشكلة P vers مقابل NP لم يتم حلها ، فإنه لا توجد حاليًا أية خوارزمية لمشكلة NP-full والتي يتم تشغيلها في زمن كثير الحدود.

العلاقة مع NP- مشاكل كاملة

في نظرية التعقيد ، تسأل مشكلة P مقابل PN غير المحلولة إذا كانت جميع المشاكل في NP تحتوي على خوارزميات متعددة الحدود الزمنية. جميع خوارزميات معروفة للمشاكل كاملة NP مثل 3SAT الخ تأخذ وقتا أسي. في الواقع ، يتم تخمينه للعديد من المشاكل الطبيعية NP-complete التي لا تملك خوارزميات وقت أسي دون الألف. هنا ، يُنظر إلى "الوقت الأسى الفرعي" ليعني التعريف الثاني المعروض أدناه. (من ناحية أخرى ، فإن العديد من مشاكل الرسم البياني الممثلة بالطريقة الطبيعية من خلال المصفوفات المجاورة تكون قابلة للحل في وقت ما قبل التصنيع ببساطة لأن حجم المدخلات هو مربع عدد الرؤوس ) . هذا التخمين (لمشكلة k-SAT) معروف مثل فرضية الزمن الأسي . ولأنه من المتصور أن المشاكل الكاملة NP لا تحتوي على خوارزميات زمن متعددة الحدود ، فإن بعض نتائج inapproximability في مجال خوارزميات التقريب تجعل الافتراض بأن مشكلات NP-complete لا تحتوي على خوارزميات زمن شبه متعددة الحدود. على سبيل المثال ، راجع نتائج inapproximability المعروفة لمشكلة غطاء المجموعة .

الوقت الأسى الفرعي

يستخدم مصطلح الزمن 'الأسى الفرعي' للتعبير عن أن وقت تشغيل بعض الخوارزميات قد ينمو أسرع من أي حدود متعددة ولكنه لا يزال أصغر بكثير من الأس. وبهذا المعنى ، فإن المشكلات التي لها خوارزميات زمنية ذات أبعاد فرعية هي أكثر قابلية للتتبع إلى حد ما عن تلك الخوارزميات الأسيّة فقط. لا يتم الاتفاق بوجه عام على التعريف الدقيق لـ "الأسى الفرعي" ،  ونحن نذكر التعريفين الأكثر استخدامًا أدناه.

فرضية الزمن الأسي

على فرضية الوقت الأسي ( ETH ) هي أن 3SAT ، والمشكلة satisfiability من الصيغ المنطقية في نموذج عطف نظامي مع، على الأكثر، وثلاث الحرفية في بند ومع ن المتغيرات، لا يمكن حلها في الوقت المناسب 2  . بتعبير أدق ، فإن الفرضية هي أن هناك بعض الثابت المطلق c > 0
بحيث لا يمكن تحديد 3SAT في الوقت المناسب 2 CN من قبل أي آلة تورينج حتمية. من خلال m تشير إلى عدد الفقرات ، تعادل ETH الفرضية القائلة بأنه لا يمكن حل k SAT في الوقت 2  لأي عدد صحيح k ≥ 3 . تعني الفرضية الزمنية الأسية P ≠ NP .