337. Computing power in logn

שבוע מתמטי טוב 2
Math

כשבאים אלינו בבקשה לכתוב פונקציה שמחשבת חזקה של מספר, הפתרון בד”כ נראה כך:

1
2
3
4
5
6
7
8
9
10
11
public static double Power(double a, int n)
{
    double result = 1;
    for (int i = 0; i < n; i++)
    {
        result *= a;
    }
    return result;
}

זה פתרון מאוד פשוט, אבל הוא בסיבוכיות $ O(n) $.

אפשר לשפר אותו ע"י חישוב חזקות שהן חזקות של 2 ולהתבסס על הייצוג הבינארי של מספר ועל חוקי החזקות:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public static double Power(double a, int n)
{
    double result = 1;
    double currentPower = a;
    while (n > 0)
    {
        if (n % 2 == 1)
        {
            result *= currentPower;
        }
        currentPower *= currentPower;
        n /= 2;
    }
    return result;
}

יש כאן רק $ \log(n) $ איטרציות.

האמת שאני מרגיש שכתבתי את זה כבר פעם, אבל אני לא הצלחתי למצוא את הטיפ המקורי.

בכל מקרה, כתבתי את זה בעיקר כדי להראות שזה אפשרי ומגניב. צריך לזכור כמובן שיש בFramework את הפונקציה Math.Pow ועדיף להשתמש בה בד"כ.

שיהיה שבוע חזק.

שתף