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

看板C_and_CPP作者 (ken)時間15年前 (2010/12/02 21:24), 編輯推噓3(3推 0噓 7→)
留言10則, 6人參與, 最新討論串1/2 (看更多)
看過高手分享過類似的文章，但似乎不是我要的方式 之前某某地方看到不需遞迴，好像兩個乘法一個除法的程式碼可以設計出來 可是不知道怎麼推出來的 例如 2^13 =2^8 x 2^4 x 2^1 如果用一般迴圈時間複雜度應該是 O(n) 吧，我沒記錯的話 但是卻可以寫出 O(logn) 的複雜度 請問是怎麼推理出來的，不用遞迴 以上為目前所了解的，如果那裏不正確感謝指導 小弟演算法很差，請各位指導了。 -- ※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 124.8.226.120
→
12/02 21:25, , 1F
2的次方可以用左移
12/02 21:25, 1F
推
12/02 21:40, , 2F
不斷用位移算出每個bit代表的值，然後把該加的就加進去
12/02 21:40, 2F
推
12/02 21:53, , 3F
2^13 = (((2^1)^2 * 2^1)^2)^2 * 2^1 我想你想講的是這個?
12/02 21:53, 3F
→
12/02 22:01, , 4F
印象中似乎用一個變數判斷，在過程中可以乘法5次就搞定了
12/02 22:01, 4F
→
12/02 22:01, , 5F
但不知道是怎麼推的
12/02 22:01, 5F
→
12/02 22:40, , 6F
big mod?
12/02 22:40, 6F
→
12/02 22:40, , 7F
底數不一定是2也能用吧
12/02 22:40, 7F
推
12/03 02:51, , 8F
啊，他沒有說到加法XD 那就是Ledia那個XD
12/03 02:51, 8F
→
12/03 02:53, , 9F
我一開始根本看錯問題了這樣XD
12/03 02:53, 9F
→
12/03 07:15, , 10F
12/03 07:15, 10F
‣ 更多 am232456 的文章
文章代碼(AID): #1Czvu7Su (C_and_CPP)
‣ 更多 am232456 的文章
文章代碼(AID): #1Czvu7Su (C_and_CPP)