ผลต่างระหว่างรุ่นของ "ขั้นตอนวิธีของคาราซูบา"
เนื้อหาที่ลบ เนื้อหาที่เพิ่ม
ไม่มีความย่อการแก้ไข |
ไม่มีความย่อการแก้ไข |
||
บรรทัด 1:
'''ขั้นตอนวิธีของคาราซูบา''' ({{lang-en|Karatsuba algorithm}}) <!--Karatsuba เป็นชาวรัสเซีย ไม่ใช่ญี่ปุ่น--> เป็น [[ขั้นตอนวิธี]] ที่ค้นพบโดย [[:en:Anatolii Alexeevitch Karatsuba|Anatolii Alexeevitch Karatsuba]]<ref>http://www.mi.ras.ru/~karatsuba/index_e.html</ref> ในปี ค.ศ. 1960 และตีพิมพ์ในปี ค.ศ. 1962<ref>A. Karatsuba and Yu. Ofman (1962). "Multiplication of Many-Digital Numbers by Automatic Computers". Proceedings of the USSR Academy of Sciences 145: 293–294</ref> เป็นขั้นตอนวิธีสำหรับ[[การคูณ]]เลข 2 จำนวนที่มีค่ามากๆ หรือการคูณกันของ[[พหุนาม]]โดยใช้[[ขั้นตอนวิธีแบบการแบ่งแยกและเอาชนะ]] ([[:en:Divide and conquer algorithm|Divide and conquer algorithm]]) <br />
== กระบวนการของขั้นตอนวิธีของคาราซูบาและการวิเคราะห์ประสิทธิภาพเชิงเวลา<ref>http://saahiihii.com/images/story/ENUBusiness1354DOCUMENT2.pdf</ref> ==
การคูณ เลข 2 จำนวน x, y ที่มีขนาด n หลัก เราสามารถเขียน x, y ใหม่ โดยใช้ จำนวน m โดยที่ m<n โดยที่เราจะเลือก m = n/2
บรรทัด 25:
:โดยที่ 3T (n/2) มาจาก 3 คือการที่เราแบ่งแล้วเกิดการคูณกัน 3 ที n/2 มาจากที่เราแบ่งจำนวนหลักของข้อมูลเป็นครึ่งหนึ่ง<br />
:จาก T (n) = 3T (n/2) +O (n) เราสามารถใช้ [[:en:master theorem|master theorem]] ลดรูปจนได้ T (n) = O (n<sup>log 3/log 2</sup>) ≈ '''O (n<sup>1.58</sup>)'''<br />
== รหัสเทียม ==
| |||