ผลต่างระหว่างรุ่นของ "ขั้นตอนวิธีของคาราซูบา"
เนื้อหาที่ลบ เนื้อหาที่เพิ่ม
ไม่มีความย่อการแก้ไข |
ไม่มีความย่อการแก้ไข |
||
บรรทัด 21:
:ซึ่งจะเห็นได้ว่าเกิดการคูณกันแค่ 3 ครั้ง คือ A, B, C เกิดการบวกกัน 4 ครั้ง ลบกัน 2 ครั้ง โดยที่การบวก และการลบใช้เวลาคงตัวโดยใช้เวลาเป็นเชิงเส้น<br />
:ดังนั้น [[ทฤษฎีความซับซ้อนในการคำนวณ|ความซับซ้อนด้านเวลา]] ([[:en:Time complexity|Time complexity]]) ของขั้นตอนวิธีของคารัดซูบะ โดยที่ 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]]<ref>http://en.wikipedia.org/wiki/Master_theorem</ref> ลดรูปจนได้ T (n) = O (n<sup>log 3/log 2</sup>) ≈ O (n<sup>1.58</sup>)<br />
== รหัสเทียม ==
| |||