تعقيد الزمان والمكان

Question

لدي شك فيما يتعلق بتعقيد الزمان والمكان في الحالتين التاليتين

اقتباس

الحالة الأولى:

التكرار:حساب العوامل.

int fact(int n)
{
    if(n==0)
      return 1;
    else
      return (n*fact(n-1));
}

هنا كيف يصبح التعقيد الزمني 2*n والتعقيد المكاني يتناسب مع n.

و

الحالة الثانية:

ترابطي:-

int fact(int n)
{
    int i, result = 1;
    if(n==0)
    result = 1;
    else
         {
           for(1=1;i<=n;i++)
              result*=i;
         }
     return (result);
}

يتناسب التعقيد الزمني مع n ويكون التعقيد المكاني ثابتًا.هذا يبقى دائما مربكا بالنسبة لي.

Answer 1

إذا كان تفكيري خاطئا أرجو أن يصحح لي أحد :)

بالنسبة لتعقيد المساحة، إليك شرحي:

بالنسبة للحل العودي، سيكون هناك n المكالمات العودية، لذلك سوف يكون هناك n المداخن المستخدمةواحد لكل مكالمة.ومن هنا O(n) فضاء.ليس هذا هو الحال بالنسبة للحل التكراري - هناك مكدس واحد فقط وأنت لا تستخدم حتى مصفوفة، فهناك متغير واحد فقط.لذا فإن تعقيد الفضاء هو O(1).

بالنسبة للتعقيد الزمني للحل التكراري، لديك n الضرب في for حلقة، لذلك سيكون هناك ربط فضفاض O(n).يمكن افتراض أن كل عملية أخرى هي وحدة زمنية أو وقت ثابت، دون التأثير على الكفاءة الإجمالية للخوارزمية.بالنسبة للحل العودي، لست متأكدًا من ذلك.إذا كان هناك مكالمتين متكررتين في كل خطوة، فيمكنك التفكير في مكدس الاستدعاءات بأكمله كشجرة ثنائية متوازنة، وسيكون إجمالي عدد العقد 2*n - 1, ، ولكن في هذه الحالة لست متأكدا.

Answer 2

from: https://cs.nyu.edu/~acase/FA14 / CS2 / module_extras.php

تعقيد الفضاء

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

تعقيد الفضاء= عدد مكالمات الدالة * عدد المتغيرات لكل مكالمة

Answer 3

تعقيد الوقت: عدد التعليمات (الجهاز) التي تنفذ البرنامج خلال وقت التشغيل يسمى تعقيد الوقت في علوم الكمبيوتر.

تعقيد الفضاء: هذا هو أساسا عدد خلايا الذاكرة التي يحتاجها خوارزمية.

الحالة 1: في البرنامج من حساب العامل بشكل متكرر، لذلك سيكون هناك مكالمة واحدة مباشرة إلى الوظيفة وعزل ستكون هناك تراجع، لذلك تصبح تعقيد الوقت 2 * n.

نتحدث عن تعقيد المساحة سيكون هناك مداخن ن يتم الإعلان عنها خلال نقطة تنفيذ البرنامج، لذلك هو n.

case 2: هذه القضية بسيطة للغاية هنا لديك N التكرار داخل حلقة لذا فإن التعقيد الوقت هو N

هذا ليس هو الحال بالنسبة للحل التكراري - هناك كومة واحدة فقط وأنت لا تستخدم صفيفا، فلا يوجد متغير واحد فقط.لذلك تعقيد الفضاء هو O (1)