ผลต่างระหว่างรุ่นของ "ขั้นตอนวิธีของคาราซูบา"

เนื้อหาที่ลบ เนื้อหาที่เพิ่ม
EmausBot (คุย | ส่วนร่วม)
r2.7.2+) (โรบอต เพิ่ม: uk:Множення Карацуби
Nullzerobot (คุย | ส่วนร่วม)
เก็บกวาด
บรรทัด 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]])
 
ขั้นตอนวิธีของคาราซูบาเป็นการคูณแบบเร็วโดยที่มี[[ทฤษฎีความซับซ้อนในการคำนวณ|ประสิทธิภาพเชิงเวลา]] (time complexity) เป็น[[สัญกรณ์โอใหญ่]]คือ O(n<sup>1.58</sup>) มีความเร็วกว่าขั้นตอนวิธีการคูณแบบธรรมดา (grade-school multiplication) ซึ่งมีประสิทธิภาพเชิงเวลาเป็น O(n<sup>2</sup>)
== กระบวนการของขั้นตอนวิธีของคาราซูบาและการวิเคราะห์ประสิทธิภาพเชิงเวลา<ref>http://saahiihii.com/images/story/ENUBusiness1354DOCUMENT2.pdf</ref> ==
การคูณ เลข 2 จำนวน x, y ที่มีขนาด n หลัก เราสามารถเขียน x, y ใหม่ โดยใช้ จำนวน m โดยที่ m<n โดยที่เราจะเลือก m = n/2
:::::x = x<sub>1</sub>10<sup>m</sup>+x<sub>0</sub>
บรรทัด 9:
 
ดังนั้น x คูณ y จะได้เป็น
:::::xy = ( x<sub>1</sub>10<sup>m</sup>+x<sub>0</sub>) (y<sub>1</sub>10<sup>m</sup>+y<sub>0</sub>) <br />
:::::xy = x<sub>1</sub> y<sub>1</sub>10<sup>2m</sup>+ (x<sub>1</sub> y<sub>0</sub>+ x<sub>0</sub> y<sub>1</sub>)10<sup>m</sup>+ x<sub>0</sub> y<sub>0</sub>
 
บรรทัด 34:
3:
4: int karatsuba(int x, int y) {
5: if(n=1)
6: return x*y
7: else
บรรทัด 49:
 
== กราฟเปรียบเทียบระหว่างการคูณธรรมดาและขั้นตอนวิธีการคูณแบบคาราซูบา<ref>http://ozark.hendrix.edu/~burch/proj/karat/results.html</ref> ==
[[Fileไฟล์:Graphkaratsuba.gif|center]]
 
== ตัวอย่าง ==