ผลต่างระหว่างรุ่นของ "ขั้นตอนวิธีของคาราซูบา"
เนื้อหาที่ลบ เนื้อหาที่เพิ่ม
ไม่มีความย่อการแก้ไข |
ไม่มีความย่อการแก้ไข |
||
บรรทัด 1:
== ประวัติของคารัดซูบะ ==
'''ขั้นตอนวิธีของคารัดซูบะ''' ({{lang-en|Karatsuba algorithm}}) เป็น [[ขั้นตอนวิธี]] ที่ค้นพบโดย [[:en:Anatolii Alexeevitch Karatsuba|Anatolii Alexeevitch Karatsuba]]<ref>http://en.wikipedia.org/wiki/Anatolii_Alexeevitch_Karatsuba</ref> ในปี ค.ศ. 1960<ref>http://www.devarticles.com/c/a/Cplusplus/Multiplying-Large-Numbers-with-Karatsubas-Algorithm/2/</ref> เป็นขั้นตอนวิธีสำหรับการคูณเลข 2 จำนวนที่มีค่ามากๆ หรือการคูณกันของ[[พหุนาม]]โดยใช้[[ขั้นตอนวิธีแบบการแบ่งแยกและเอาชนะ]] ([[:en:Divide and conquer algorithm|Divide and conquer algorithm]])
== กระบวนการของขั้นตอนวิธีของคารัดซูบะ<ref>http://saahiihii.com/images/story/ENUBusiness1354DOCUMENT2.pdf</ref> ==
บรรทัด 26:
:โดยที่ 3T (n/2) มาจาก 3 คือการที่เราแบ่งแล้วเกิดการคูณกัน 3 ที n/2 มาจากที่เราแบ่งจำนวนหลักของข้อมูลเป็นครึ่งหนึ่ง<br />
:จาก T (n) = 3T (n/2) +O (n) เราสามารถใช้ [[:en:master theorem|master theorem]]
== รหัสเทียม ==
| |||