ขั้นตอนวิธีของคาราซูบา

ขั้นตอนวิธีของคาราซูบา (อังกฤษ: Karatsuba algorithm) เป็น ขั้นตอนวิธี ที่ค้นพบโดย Anatolii Alexeevitch Karatsuba[1] ในปี ค.ศ. 1960 และตีพิมพ์ในปี ค.ศ. 1962[2] เป็นขั้นตอนวิธีสำหรับการคูณเลข 2 จำนวนที่มีค่ามากๆ หรือการคูณกันของพหุนามโดยใช้ขั้นตอนวิธีแบ่งแยกและเอาชนะ (Divide and conquer algorithm)ขั้นตอนวิธีของคาราซูบาเป็นการคูณแบบเร็วโดยที่มีประสิทธิภาพเชิงเวลา (time complexity) เป็นสัญกรณ์โอใหญ่คือ O(n1.58) มีความเร็วกว่าขั้นตอนวิธีการคูณแบบธรรมดา (grade-school multiplication) ซึ่งมีประสิทธิภาพเชิงเวลาเป็น O(n2)

ใกล้เคียง

ขั้นตอนวิธีแบบยุคลิด ขั้นตอนวิธีการค้นหาเพื่อนบ้านใกล้สุด k ตัว ขั้นตอนวิธีของฟลอยด์-วอร์แชล ขั้นตอนวิธีของควิน-แม็กคลัสกีย์ ขั้นตอนวิธี ขั้นตอนวิธีเชิงพันธุกรรม ขั้นตอนวิธีฮังกาเรียน ขั้นตอนวิธีของชอร์ ขั้นตอนวิธีโบรน-เคอร์โบสท์ ขั้นตอนวิธีของเบลแมน-ฟอร์ด