Re: [中學] 能證明所有次方最快的算法是D&C嗎?
※ 引述《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次
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 203.72.177.253
※ 文章網址: http://www.ptt.cc/bbs/Math/M.1411806733.A.10F.html
→
09/27 17:10, , 1F
09/27 17:10, 1F
推
09/27 19:18, , 2F
09/27 19:18, 2F
推
09/28 14:06, , 3F
09/28 14:06, 3F
討論串 (同標題文章)