Re: [問題] 2的次方演算法-時間複雜度 log
※ 引述《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)
推
12/03 08:34, , 1F
12/03 08:34, 1F
→
12/03 13:17, , 2F
12/03 13:17, 2F
推
12/03 18:05, , 3F
12/03 18:05, 3F
討論串 (同標題文章)
完整討論串 (本文為第 2 之 2 篇)：