التعقيد الحسابي من عد الرموز

Question

النظر في وظيفة العد $ \ {x \} ^ * rawrow \ mathbb n $ يحسب عدد تكرارات الرمز $ x $ .

أنا مرتبك بشأن التعقيد (المقاهر) لحساب هذه الوظيفة، حيث يجب تمثيل الإخراج في نظام غير منطقي (مثل، ثنائي) . يقترح حدسي بشدة أن هذا يجب أن يكون خطيا، أي، $ O (n) $ (n) $ حيث $ n $ هو عدد تكرارات الرمز $ x $ في الإدخال.

بقدر ما يذهب فهمي هناك تفسيرات متعددة للحسابات - E.G.،

• آلات تورينج الفرقة واحدة، والتي أدت فكرة أفضل وجهتي $ \ omega (n ^ 2 \ log n) $ أعتقد ( $ \ Log N $ يأتي من افتراض أن وظيفة الخلف الثنائية لديها $ \ omega (n) $ وقت التشغيل، حيث $ N $ هو طول التمثيل الثنائي لرقم طبيعي، و $ n ^ 2 $ يأتي من افتراض أن آلة turing يجب أن تسافر على جميع $ x $ 's للوصول إلى عددها الحالي)،
• ماكينات تورينج متعددة النطاقات، التي أعتقد أن لدي فكرة عن وقت التشغيل $ \ أوميغا (n \ log n) $ ،
• آلات الوصول العشوائي، والتي لا أعرفها على الإطلاق.

لذلك سؤالي هو ما يلي.

ما هو التعقيد الحسابي لوظيفة العد في النماذج المختلفة للحساب؟ هل هو خطي في أي منهم؟

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

Answer 1

Turing Machines هي نموذج جميل مع العديد من المزايا، معظمها بساطتها، لكنها ليست الخيار الأول عند تحليل الخوارزميات. عادة ما يتم تحليل الخوارزميات ضمنيا على نموذج آلة ذاكرة الوصول العشوائي، وفي بعض الحالات، على نموذج BSS .

إليك بعض التعليقات على التعقيد الحسابي للعد في النماذج المختلفة:

آلة تورينج الشريط الفردي: يتم النظر فيها فقط لأنه من السهل نسبيا إثبات حدود منخفضة عليها. إنهم أقل واقعية نموذج حساب من آلات Turing متعددة الشرائط.

آلة turing متعددة الشريط: هو مثال قياسي في التعقيد المطفأة يمكن تنفيذ عداد متزايد باستخدام $ O (1) $ عمليات بت المطفأة. هذا لأن نصف الوقت، تغييرات قليلا فقط، ربع الوقت، فقط بتان، وهلم جرا، وبالنسبة إلى إجمالي عدد البتات المتغيرة التي هي $ 1/2 + 2 / 4 + 3/8 + \ CDOTS= 2 $ . تعقيد آلة تورينج خطي في ذلك، وبالتالي يمكن تنفيذ العد في $ O (n) $ .

آلة ذاكرة الوصول العشوائي: يتكون آلة الكبش من العديد من السجلات وذاكرة وصول عشوائي. السجلات هي $ o (\ log n) $ -bits، حيث $ n $ هو الحجم من المدخلات. عمليات معقولة على السجلات تأخذ وقتا ثابتا. على وجه الخصوص، زيادة عداد يمكن الاعتماد على $ \ mathit {poly} (n) $ يأخذ $ o (1 ) $ أسوأ الحالات الوقت. على وجه الخصوص، سيتم تشغيل وظيفتك في $ O (n) $ .

bss machine: يجب أن يكون المرء حذر عند إجراء حسابي على أرقام كبيرة. على آلة ذاكرة الوصول العشوائي، يأخذ الحساب وقتا ثابتا فقط إذا كان حجم المعاملات هو $ \ mathit {poly} (n) $ . كما يسمح آلة BSS بالوصول إلى سجلات خاصة تخزن القيم في بعض الحقل، كما يقول الأرقام الحقيقية. يمكنك إجراء حسابي ثابت ومقارنات ثابتة، ولكن لا يعمل مثل الأرض. كما لا يسمح لك باستخدام هذه القيم للفهرسة. (إذا لم تقصر نفسك بما فيه الكفاية، فسوف تجلس قريبا في وقت متعدد الحدود.) يمكنك التفكير في جهاز BSS لاستيعاب العمليات العائمة، والتي تتخذ في الممارسة وقتا ثابتا، مع تجاهل الدقة المحدودة المتورطة فيها .