الوقت تعقيد تحليل التعليمات البرمجية

Question

int foo(int n) 
{
    int x=2;
    while (x<n)
    {
        x = x*x*x;
    }

    return x;
}

أنا بحاجة إلى تحليل تعقيد الوقت.لاحظت أن تصل إلى n أسرع بكثير من مجرد log(n).أعني أنه لا أقل من O(log(n)) أن تفعل.قرأت الجواب ولكن ليس لدى أي فكرة كيف حصلت عليه:فمن O(log(log(n)).الآن كيف يمكنك معالجة هذا السؤال ؟

Answer 1

السماح

L3 = تسجيل الدخول إلى قاعدة 3 L2 = تسجيل الدخول إلى قاعدة 2

ثم الجواب الصحيح هو O(L3(L2(n)) وليس O(L2(L2(n)).

نبدأ مع x = x * 2.x سوف تزيد أضعافا مضاعفة حتى يصل إلى n ، مما يجعل الوقت تعقيد O(L2(n))

تنظر الآن x = x * x.× زيادة أسرع مما سبق.في كل التكرار قيمة x يقفز إلى مربع قيمتها السابقة.القيام ببعض الرياضيات بسيطة, هنا هو ما نحصل على:

من أجل x = 2 n = 4, تكرار اتخاذها = 1 ن = 16, تكرار اتخاذها = 2 n = 256, تكرار اتخاذها = 3 n = 65536, تكرار اتخاذها = 4

وبالتالي تعقيد الوقت O(L2(L2(n)).يمكنك التحقق من ذلك عن طريق وضع القيم أعلاه قيم n.

يأتي الآن إلى مشكلتك ، x = x * x * x.سيؤدي هذا إلى زيادة أسرع مما x = x * x.هنا هو الجدول:

من أجل x = 2 n = 8, تكرار اتخاذها = 1 n = 512, تكرار اتخاذها = 2 ن = (512*512*512), التكرار اتخذت = 3 وهكذا

إذا نظرتم إلى هذه بعناية ، تبين أن هذا O(L3(L2(n)).L2(ن) سوف تحصل على الطاقة من اثنين ، ولكن منذ كنت تأخذ مكعب x في كل التكرار ، عليك أن تأخذ السجل إلى قاعدة 3 من معرفة العدد الصحيح من التكرار المتخذة.

لذلك أعتقد أن الجواب الصحيح هو O(log-إلى-قاعدة-3(سجل إلى قاعدة-2(n))

تعميم هذا ، إذا x = x * x * x * x * ..(ك مرات), ثم تعقيد الوقت O(log-إلى-قاعدة-k(سجل إلى قاعدة-2(ن)

Answer 2

والتفكير في ذلك بوصفها وظيفة العودية:

f(i) = f(i-1)^3

وإذا كنت توسيعه:

f(i) = ((f(i-k)^3)^3)[...k times] = f(i-k)^(3^k) = f(0)^(3^i)

وظيفة تنمو كقوة من السلطة ... وبالتالي فإن الوقت (التكرار) للوصول إلى عدد معين (أي، حساب معكوس دالة) هو لوغاريتم اللوغاريتم.

وكما هو الحال في المثال f(0) = 2 الخاص بك، ونحن نريد أن نعرف متى f(i) >= n يجري n معلمة الإدخال (وi عدد التكرارات):

f(i) = 2^(3^i) >= n
           3^i >= log_2(n)
             i >= log_3(log_2(n))

وهكذا للوصول إلى قيمة n، فإنه takes log_3(log_2(n)) التكرار (محاصرة في التعامل مع الأعداد الصحيحة لتجاوز ذلك).

وإذا كانت وظيفة ستكون كما يلي:

f(i) = 2*f(i-1) //e.g. x=2*x

وبعد ذلك النمط على النحو التالي:

f(i) = 2*2*[...k times]*f(i-k) = f(i-k)*(2^k) = f(0)*(2^i)

وفي هذه الحالة، ثم معكوس دالة سيكون وغاريتم واحد في قاعدة 2.

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

Answer 3

التفكير في كيفية x التغييرات مع عدد من التكرارات خلال الحلقة.في كل مرة كنت المكعب ذلك.حتى بعد أن التكرار قيمة 2 مكعبة ، مكعبة مرة أخرى...حتى انا مرات.دعونا نستخدم x(ط) دلالة هذا التعبير.دعونا نقول × (0)=2 x(1)=23 ، الخ (أنا باستخدامب يعني رفع إلى bth السلطة).

نحن القيام به عندما x(i)>=n.كم من الوقت يستغرق ؟ دعونا حل أنا.

First, we take a log on both sides: ln(x(i))>=ln(n)

ln(x(i)) = ln(x(i-1))*3 = ln(x(i-2))*(3**2) = ... = ln(x(0))*(3**i)

(the above uses [this property][1]: ln(x**b)==ln(x)*b)

so, 3**i * 2 >=ln(n). Let's take another logarithm:

ln(3**i * 2) = ln(2) + ln(3)*i 

so ln(2) + ln(3)* i >= ln(ln(n))

Now we can solve for i: i >= ( ln(ln(n))-ln(2) ) / ln(3)

يمكننا تجاهل عوامل ثابتة و نحن مع اليسار استنتاج أننا سوف تأخذ تسجيل الدخول(log(n)) الخطوات.هذا تعقيد الخوارزمية.

نأمل, كسر جميع الخطوات مثل أن يساعد.

Answer 4

إذا كان رمز داخل الحلقة في حين

x = 2*x;

س ن ستصل في O (سجل (ن)) تكرارات. منذ كنت التكعيب س بدلا من مجرد ضرب من قبل ثابت، سوف تصل ن أسرع.

Answer 5

ونظرا

log ( A * x )     == log ( A ) + log ( x )
log ( x * x * x ) == 3 * log ( x )

وهكذا

log ( log ( x * x * x ) ) == log ( 3 * log ( x ) )
                          == log ( 3 ) + log ( log ( x ) )

وكيف أسرع أو أبطأ بكثير (تقاس حسب عدد التكرارات من الحلقة) سوف تكون هذه الوظيفة من وظيفة الخاص بك؟

int log_foo ( int n ) 
{
    double          log_x = log ( 2 );
    const double    log_n = log ( n );

    while ( log_x < log_n )
    {
        log_x = 3 * log_x;
    }

    return exp ( log_x );
}

وكيف أسرع أو أبطأ بكثير سوف تكون هذه الوظيفة من وظيفة الخاص بك؟

int log_log_foo ( int n ) 
{
    double          log_log_x = log ( log ( 2 ) );
    const double    log_log_n = log ( log ( n ) );
    const double    log_3     = log ( 3 );

    while ( log_log_x < log_log_n )
    {
        log_log_x += log_3;
    }

    return exp ( exp ( log_log_x ) );
}

ولكن هذه الوظيفة بزيادة فقط log_log_x بواسطة ثابت، لذلك فمن السهل للعمل على كيفية العديد من التكرارات يفعل.

Answer 6

واسمحوا i يكون عدد من الخطوات التكرار وx(i) قيمة x بعد خطوات i. لدينا

x(0) = 2
x(i) = x(i-1)³

وبلغ عدد من الخطوات هو أكبر i بحيث x(i) < n.

لدينا

log x(i) = log x(i-1)³
         = 3·log x(i-1)
         = 3·log x(i-2)³
         = 3²·log x(i-2)
         = 3^i·log x(0)
         = 3^i·log 2

⇒  log log x(i) = log (3^i·log 2)
                 = log 3^i + log log 2
                 = i·log 3 + log log 2

ولوغاريتم يتزايد بشكل صارم، لذلك

x(i) < n ⇔        log log x(i) < log log n
         ⇔ i·log 3 + log log 2 < log log n
         ⇔                   i < (log log n - log log 2) / log 3 ∈ O(log log n)

Answer 7

لماذا لا تضيف متغير عداد لحساب عدد التكرارات من الحلقة. طباعته قبل ترجع الدالة.

وثم استدعاء الدالة لمجموعة من القيم، على سبيل المثال 3 إلى 1،000،000 لتبدأ. ثم رسم نتيجة باستخدام شيء من هذا القبيل GNUPlot .

وبعد ذلك معرفة ما إذا كان الرسم البياني يطابق منحنى المعروفة.