Re: [中學] 能證明所有次方最快的算法是D&C嗎?
※ 引述《agga (小孩)》之銘言：
: ※ 引述《bjiyxo (若自礌)》之銘言：
: : 如題，能否證明次方最快的算法是Divide & Conquer嗎?
: : 由於我沒有學過演算法，可能這個對大家很簡單QQ
: : 而D&C這個演算法是這樣的
: : 如果我要算a^7
: : 而直接拿a乘上7次，對於指數如果是很大的數字會非常慢
: : 但是如果我將他分解
: : 分解成a^3*a^3*a
: : 先將7/2等於3餘1，將a^7divide成a^3再計算
: : 如此兩兩分對的結果就會讓結果只要乘4次就好
: : 而如果遇到大一點的指數，則會不斷的兩兩分對計算
: : 那麼最後請問這個D&C能否證明是所有次方的最快的計算方法呢？
: 可以允許除法嗎?
: 如 a^63 可以a的平方再平方再平方... 到a^64, 再除以a
: 這樣只要7次
有推文說改成二進位
15=1111 (2) = 1000(-1) 有連三個1改成除會和乘一樣快
連四個1, 改成除就比較外
我原本以為也是改成二進位就結束了
結果後來發現300以內就找到快10個數字
用別種方法比二進位快
這個主題有哪些關鍵字可以查論文呢?
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 59.115.97.146
※ 文章網址: http://www.ptt.cc/bbs/Math/M.1411908278.A.280.html
推
09/28 22:16, , 1F
09/28 22:16, 1F
→
10/01 13:44, , 2F
10/01 13:44, 2F
討論串 (同標題文章)
本文引述了以下文章的的內容：
完整討論串 (本文為第 3 之 4 篇)：