Re: [問題] 2的次方演算法-時間複雜度 log

[curist (好問題..)]

※ 引述《am232456 (ken)》之銘言：
: 看過高手分享過類似的文章，但似乎不是我要的方式
: 之前某某地方看到不需遞迴，好像兩個乘法一個除法的程式碼可以設計出來
: 可是不知道怎麼推出來的
: 例如 2^13 =2^8 x 2^4 x 2^1
: 如果用一般迴圈時間複雜度應該是 O(n) 吧，我沒記錯的話
: 但是卻可以寫出 O(logn) 的複雜度
: 請問是怎麼推理出來的，不用遞迴
: 以上為目前所了解的，如果那裏不正確感謝指導
: 小弟演算法很差，請各位指導了。

int main()
{
    int base, exp;
    int ans, temp;

    printf("> ");
    while(scanf("%d %d", &base, &exp) == 2) {
        ans = 1;
        temp = base;
        while(exp) {
            if(exp % 2 == 1) {
                ans *= temp;
            }
            temp *= temp;
            exp >>= 1;
        }

        printf("%d\n", ans);
        printf("> ");
    }

    return 0;
}

/* 改成 x**n 的版本 */
※ 編輯: curist          來自: 114.25.186.137       (12/03 08:16)
推 Yshuan:推熱心 其實這是數學 不是演算法吧XD
→ bleed1979:divide and conquer是算法的一種??　我想到拿破崙。
推 cutecpu:推！