هل من الممكن تقدير ذاكرة الوصول العشوائي اللازمة من تعقيد الفضاء Turing؟

Question

يمكن لآلات Turing النظر في التعقيد في كل من مساحة (مساحة الذاكرة على الأشرطة) والوقت.

هناك فصول مثل PSPACE و Expspace.

علاوة على ذلك ، يمكننا تقديم الخوارزميات التي هي بالتأكيد في PSPACE.

http://www.springerlink.com/content/3hqtq1mqjbqfj2g/

ومع ذلك ، عندما أقوم بالفعل بترميز البرامج ، تعمل بعض البرامج بشكل أسرع من غيرها ، فإن بعض البرامج لديها بصمة ذاكرة أصغر (RAM) من غيرها.

من المفترض أن أقوم بترميز خوارزمية PSPace لحل المشكلة X وكذلك خوارزمية Expspace لحل نفس المشكلة ، يجب أن يستخدم برنامج Expspace أكثر بكثير من رمز PSPACE.

هل هناك أي طريقة لتقدير كمية ذاكرة الوصول العشوائي التي ستشارك ، بناءً على التصنيف النظري لخوارزمية البداية؟

Answer 1

من حيث المبدأ لا. في الممارسة العملية ، في بعض الأحيان.

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

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

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

Answer 2

من المفترض أن أقوم بترميز خوارزمية PSPace لحل المشكلة X وكذلك خوارزمية Expspace لحل نفس المشكلة ، يجب أن يستخدم برنامج Expspace أكثر بكثير من رمز PSPACE.

أنت تفترض خطأ.

تصف فئات التعقيد هذه النمو المقارب للذاكرة المطلوبة لأداء الخوارزمية. إنهم يخبرونك بأي شيء على الإطلاق عن الكمية الفعلية للذاكرة المطلوبة.

في الأساس ، لبعض الحجم من المشكلة ن, ، فوق هذا الحجم سوف يستخدم Expspace ذاكرة أكثر من PSPACE ، ولكن لأي شيء أدناه ن, ، لا يمكنك حقًا قول أي شيء (تمامًا مثل O (n²) قد تعمل الخوارزميات أسرع من خوارزميات O (N) ن).