ผลต่างระหว่างรุ่นของ "ขั้นตอนวิธีของคาราซูบา"
เนื้อหาที่ลบ เนื้อหาที่เพิ่ม
Nullzerobot (คุย | ส่วนร่วม) ล เก็บกวาด |
Nullzerobot (คุย | ส่วนร่วม) ล เก็บกวาด |
||
บรรทัด 4:
== กระบวนการของขั้นตอนวิธีของคาราซูบาและการวิเคราะห์ประสิทธิภาพเชิงเวลา<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>
::::: y = y<sub>1</sub>10<sup>m</sup>+y<sub>0</sub>
ดังนั้น x คูณ y จะได้เป็น
::::: xy
::::: xy
กำหนดให้
::::: A
::::: B
::::: C
จะได้
::::: xy
: ซึ่งจะเห็นได้ว่าเกิดการคูณกันแค่ 3 ครั้ง คือ A, B, C เกิดการบวกกัน 4 ครั้ง ลบกัน 2 ครั้ง โดยที่การบวก และการลบใช้เวลาคงตัวโดยใช้เวลาเป็นเชิงเส้น<br />
: ดังนั้น '''ประสิทธิภาพเชิงเวลา''' ของขั้นตอนวิธีของคาราซูบา โดยที่ n เป็นจำนวนหลักคือ<br />
:::: T (n) = 3T (n/2) +O (n)<br />
: โดยที่ 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 />
== รหัสเทียม ==
<source lang="text">
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
</source>
บรรทัด 53:
== ตัวอย่าง ==
การคูณเลข 2 จำนวน 5678×8765
:::: 5678 = 56×10<sup>2</sup> + 78
:::: 8765 = 87×10<sup>2</sup> + 65
:::: 5678×8765 = (56×10<sup>2</sup> + 78)(87×10<sup>2</sup> + 65)
:::::::
:::::::
:::::::
: การคูณของพหุนาม 2 จำนวน<ref>http://www.ccas.ru/personal/karatsuba/divcen.htm</ref> (a + bx) (c + dx)
:::: (a + bx)(c + dx) = ac + ((a+b)(c+d) − ac − bd)x + bdx<sup>2</sup>
:::::::
== อ้างอิง ==
|