في علم الحاسوب، يعتبر تعقيد الوقت هو التعقيد الحسابي الذي يقيس أو يقدر الوقت المستغرق لتشغيل خوارزمية. عادةً ما يتم تقدير تعقيد الوقت من خلال حساب عدد العمليات الأولية التي تقوم بها الخوارزمية، بافتراض أن العملية الأولية تستغرق وقتًا ثابتًا لأداءها. وبالتالي، فإن مقدار الوقت المستغرق وعدد العمليات الأولية التي تقوم بها الخوارزمية يختلفان على الأكثر بعامل ثابت.
نظرًا لأن وقت تشغيل الخوارزمية قد يختلف باختلاف مدخلات من نفس الحجم، فيحسب المرء عادة تعقيد وقت الحالة الأسوأ، وهو أقصى مقدار من الوقت المستغرق في مدخلات حجم معين. أقل شيوعا، وعادة ما يتم تحديده بشكل صريح، هو تعقيد الحالة المتوسطة، وهو متوسط الوقت المستغرق على مدخلات حجم معين (وهذا منطقي، حيث لا يوجد سوى عدد محدود من المدخلات الممكنة من حجم معين).
في كلتا الحالتين، يتم التعبير عن تعقيد الوقت بشكل عام كدالة لحجم المدخلات. بما أن هذه الوظيفة يصعب بشكل عام حسابها بالضبط، ووقت التشغيل عادة لا يكون حرجًا بالنسبة إلى المدخلات الصغيرة، فإن أحدهما يركز عادة على سلوك التعقيد عندما يزيد حجم المدخلات؛ وهذا هو، على السلوك المقارب للتعقيد. لذلك، يتم التعبير عن تعقيد الوقت بشكل شائع باستخدام تدوين O الكبير، عادةً، إلخ، حيث n هو حجم الإدخال المقاس بعدد البتات المطلوبة لتمثيله.
O
(
n
)
,
{\displaystyle O(n),}
O
(
n
log
n
)
,
{\displaystyle O(n\log n),}
O
(
n
α
)
,
{\displaystyle O(n^{\alpha }),}
O
(
2
n
)
,
{\displaystyle O(2^{n}),}
بت
يتم تصنيف تعقيدات الخوارزمية بواسطة الدالة التي تظهر في تدوين O الكبير. على سبيل المثال، خوارزمية ذات تعقيد زمني هي خوارزمية زمنية خطية ، خوارزمية مع تعقيد زمني لبعض الثابت هي خوارزمية زمن متعددة الحدود .
O
(
n
)
{\displaystyle O(n)}
'
O
(
n
α
)
{\displaystyle O(n^{\alpha })}
α
≥
1
{\displaystyle \alpha \geq 1}
'