تعقيد الزمن

في علم الحاسوب، فإن تعقيد زمان خوارزمية هو تحديد الزمن الذي تستغرقه تلك الخوارزمية لتعمل كتابع لحجم مدخلات المسألة. غالباً ما يعبر عن تعقيد زمن خوارزمية بإستخدام تدوين أوه الكبيرة، الذي يستبعد الثوابت المضروبة والحدود الأقل رتبة. وعندمايستخدم التدوين السابق لوصف تعقيد زمن خوارزمية ما فإن ذلك الوصف يكون بشكل مقارب asymptotically، أي عندما يسعى حجم المدخلات إلى اللانهاية. على سبيل المثال ، إذا كان أقصى زمن تستغرقه خوارزمية من أجل جميع المدخلات من حجم n هو $3n+5n^{3}\,$ ،فإن تعقيد الزمن المقارب هو $(N^{3})O\,$ .

ويقدر عادة تعقيد وقت خوارزمية من خلال إحصاء عدد العمليات الأولية التي تؤديها الخوارزمية، باعتبار أن تنفيذ كل عملية ابتدائية يأخذ مقداراً محدداً من الزمن. لذلك فإن الوقت الذي تستغرقه الخوارزمية وعدد العمليات الأولية المنفذة فيها يختلف بمقدار معامل ثابت على الأكثر.

وبما أنه يمكن للخوارزمية أن تستغرق مقداراً مختلفاً من الوقت بالنسبة لمدخلات من الحجم نفسه، فإن المقياس الأكثر استخداما في تعقيد الزمن، هو تعقيد زمن أسوأ الحالات للخوارزمية، والذي يعبر عنه باستخدام $T(n)\,$ ، وهو الحد الأعظمي من الوقت الذي يمكن أن يستهلكه أي دخل من الحجم n. تصنف تعقيدات زمن الخوارزميات وفقاً لطبيعة التابع $T(n)\,$ . فعلى سبيل المثال، تسمى خوارزمية بتابع $T(n)=O(n)\,$ خوارزمية زمن خطي ، وخوارزمية بتابعو $T(n)=O(2^{n})\,$ خوارزمية زمن أسي.

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

جدول بأشهر تعقيدات الزمن

يلخص الجدول التالي أهم أصناف تعقيدات الزمن The following table summarises some classes of commonly encountered time complexities. In the table, poly(x) = x^O(1), i.e., polynomial in x.

quasi-polynomial time || QP || 2^poly(log n) || n^log log n, n^log n || Best-known O(log²n)-approximation algorithm for the directed Steiner tree problem.

الاسم	صنف التعقيد	وقت التشغيل $T(n)\,$	أمثلة على أوقات التشغيل	أمثلة على الخوارزميات
وقت ثابت		$O(1)$	10	تحديد ما إذا كان عدد ما زوجياً أو فردياً
آكيرمان العكسي		$O(\alpha (n))\,$		Amortized time per operation using a disjoint set
لوغاريتمي تكراري		$O(log^{}(n))\,$*		Distributed coloring of cycles
لوغاريتمي لوغاريتمي		$O(loglog(n))$		Amortized time per operation using a bounded priority queue^[1]
زمن لوغاريتمي	DLOGTIME	$O(log(n))\,$	$log(n)\,$ , $log(n^{2})\,$	Binary search
زمن كثير-لوغاريتمي		poly(log (n))	$(log(n))^{2}\,$ >
قوة كسرية		$O(n^{c})\,$ , $0<c<1\,$	$n^{1/2}\,$ , $n^{2/3}\,$	Searching in a kd-tree
زمن خطي		O(n)	n	Finding the smallest item in an unsorted array
"n لوغاريتم نجمة n"		O(n قالب:Log-star n)		Seidel's polygon triangulation algorithm.
زمن خطي-حسابي		O(n log n)	n log n, log n!	Fastest possible comparison sort
quadratic time		O(n²)	n²	Bubble sort; Insertion sort
زمن تكعيبي		O(n³)	n³	Naive multiplication of two n×n matrices. Calculating partial correlation.
زمن كثير حدودي	P	2^O(log n) = poly(n)	n, n log n, n¹⁰	Karmarkar's algorithm for linear programming; AKS primality test
sub-exponential time (first definition)	SUBEXP	O(2^{n^ε}) for all ε > 0	O(2^{log n^{log log n}})	Assuming complexity theoretic conjectures, BPP is contained in SUBEXP.
sub-exponential time (second definition)		2^o(n)	2^{n^1/3}	Best-known algorithm for integer factorization and graph isomorphism
زمن أسي	E	2^O(n)	1.1ⁿ, 10ⁿ	Solving the traveling salesman problem using dynamic programming
زمن أسي	EXPTIME	2^poly(n)	n!, nⁿ, 2^n²
زمن عاملي		O(n!)	n!	Solving the traveling salesman problem via brute-force search
زمن أسي مزدوج	2-EXPTIME	2^{2^poly(n)}	2^3ⁿ	Deciding the truth of a given statement in Presburger arithmetic

مراجع

^ Mehlhorn, Kurt; Naher, Stefan (1990). "Bounded ordered dictionaries in O(log log N) time and O(n) space". Information Processing Letters.

[1] Mehlhorn, Kurt; Naher, Stefan (1990). "Bounded ordered dictionaries in O(log log N) time and O(n) space". Information Processing Letters.

[1]