كتب complexity measurement
اذا لم تجد ما تبحث عنه يمكنك استخدام كلمات أكثر دقة.
قياس التعقيد (معلومة)
ولكي يكون قياس التعقيد، والذي هو استخدام كمية مُعينة من الموارد مثل : الوقت أو المكان، دقيقا ومُعرفا بشكل رياضياتي سليم كانت الحاجة للنماذج الحاسوبية مثال : آلة تيورنج، وقد نعرف الوقت اللازم لحل مسألة بواسطة آلة تيورنج ,M , مع المدخل للالة ,x, هو عدد الخطوات أو التحول من وضعية لوضعية اللازمة للالة حتى التوقف والاتيان بالنتيجة ( مثل : نعم أو لا ) . ونقول أنَّ آلة تيورنج , M , وقت عملها هو (f(n إذا كان الوقت اللازم للالة M على كل مُدخل طولة n هو (f(n . ونقول أنَّ مسألة يمكن حلها بوقت (f(n إذا يوجد آلة تيورنج M الوقت الذي تحتاجه لحل مُدخل طوله n هو (f(n . وبما أنَّ نظرية التعقيد اهتمامها بتصنيف المسائل حسب صعوبتها لذا فالمرئ يمكنه تعريف مجموعة مسائل تحقق معيار مُعين مثال ذلك المجموعة ((DTIME(f(n وهي مجموعة المسائل التي يوجد آلة تيورنج قطعية التي تحلها بوقت (f(n .
هنالك عدة مقاييس للتعقيد ولعل اهمها هو الوقت والمكان، ولعل بديهيات بلم (Blum axioms) في نظرية التعقيد تُعرف هذه المقاييس . مقاييس اخرى مُستخدمة في نظرية التعقيد هي تعقيد الاتصال وتعقيد الدارات المنطقية وتعقيد شجرة التقرير . وبشكل عام في قياس تعقيد الخوارزميات شاع استخدام رمز O الكبير .
