Questions in category: 算法 (Algorithm)
计算数学 >> 算法

1. 正整数乘法的 Karatsuba 算法

Posted by haifeng on 2019-04-28 08:41:57 last update 2019-04-28 09:15:17 | Answers (0) | 收藏


我们以十位数乘以十位数为例. 这里 $ab$ 是十位数, 即 $10a+b$, $a,b\in\{0,1,2,\ldots,9\}$.

\[
ab\times cd=(10a+b)(10c+d)=100ac+10(ad+bc)+bd.
\]

这是通常的算法, 需要 4 次乘法.

 

 

注意到

\[
(a+b)(c+d)=(ac+bd)+(ad+bc),
\]

因此,

\[
ad+bc=(a+b)(c+d)-(ac+bd)
\]

于是

\[
ab\times cd=100ac+10(ad+bc)+bd=100ac+10[(a+b)(c+d)-(ac+bd)]+bd.
\]

这里, 我们只需 $ac$, $bd$, $(a+b)(c+d)$ 三次乘法.

 

对于大的整数, 采用分治策略, 归结为小整数的乘法和加法运算.

2. 单处理器作业调度问题

Posted by haifeng on 2018-06-07 09:18:13 last update 2018-06-07 09:21:21 | Answers (0) | 收藏


现在有 $N$ 个作业 $j_1,j_2,\ldots,j_N$, 已知对应的运行时间分别为 $t_1,t_2,\ldots,t_N$. 而处理器只有一个.

目标是使作业平均完成的时间最小化.

要求: 这里我们非抢占调度(nonpreemptive scheduling), 即 一旦开始一个作业, 就必须把该作业运行完.

 

 


References:

Mark Allen Weiss, Data Structures and Algorithm Analysis in C++, (Third Edition).

张怀勇 等译, 《数据结构与算法分析 C++ 描述》(第三版) [Chapter 10. Page. 297]

 

https://study.com/academy/lesson/preemptive-vs-non-preemptive-process-scheduling.html