1 How to measure the running speed of an algorithm?

How to measure the running speed of an algorithm? What exactly does it mean for an algorithm to be fast or efficient well?

Of course, we cannot simply measure the “running time” of the algorithm, because the different computers have different configuration.

Maybe it runs slowly on this computer because this computer is 10 years old!

So you can’t say program A is slower than program B, just based on how long the computer is running the program. Because different computers are configured differently.

2 Asymptotic Notation

Computer scientists and mathematicians developed the method of progressive analysis.

2.1 Big O notation

2.1.1 definition

A function f(x) runs on the order of G(x) if there exists some x value x_0 and some constant C for which f(x) is less than or equal to that constant times G(x) for all x greater than x_0. Then we say that f(x)=O(g(x)).

(1) f(x) \in g(x),
(2) there exists x_0, C,
(3) for all x greater x_0, f(x) \leq C \times g(x).

for example:

2.1.2 example

for another example:
f(x) = 4x^2 + 16x + 2,
g(x) = x^4,
then, we have:
f(x) = O(g(x)),
that means: 4x^2 + 16x + 2 \leq C \times x^4.

when C=1:

x 4x^2 + 16x + 2 < x^4 T or F
0 2 < 0 F
1 22 < 1 F
2 50 < 16 F
3 86 < 81 F
4 130 < 256 T
f(x) < g(x) T

So, there is normal for x_0=4, C=1, for all x greater than x_0, there are f(x) \leq C \times g(x). So, f(x)=O(g(x)).

2.2 Big Ω notation

2.2.1 definition

(1) f(x) \in g(x),
(2) there exists x_0, C,
(3) for all x greater x_0, f(x) \geq C \times g(x).

2.2.2 example

f(x) = 4x^2 + 16x + 2,
g(x) = x^2,
then, we have:
f(x) = Ω(g(x)),
that means: 4x^2 + 16x + 2 \geq C \times x^2,

when C=1:

x 4x^2 + 16x + 2 > x^2 T or F
f(x) > g(x) T

So, there is normal for x_0=0, C=1, for all x greater than x_0, there are f(x) \geq C \times g(x). So, f(x)=Ω(g(x)).

2.3 Big θ notation

2.3.1. definition

f(x) = \theta(g(x)) iff
(1)f(x)=O(g(x)),
(2)f(x)=\Omega(g(x)),

2.3.2 example

f(x) = 4x^2 + 16x + 2,
g(x) = x^2,
then, we have:
f(x) = \theta(g(x)),
than means:f(x) = O(g(x)) and f(x) = \Omega(g(x)).

prove f(x) = O(g(x))

when C=5, x>=20:
4x^2 + 16x + 2 \leq 5 \times x^2
so,f(x) = O(g(x))

prove f(x) = Ω(g(x))

when C=1, x>=0:
4x^2 + 16x + 2 \geq x^2
so,f(x) = Ω(g(x))

you can see this pic:

so,f(x) = θ(g(x)).

0
Posted in 计算机基础知识

1 How to measure the running speed of an algorithm?(如何衡量一个算法的运行速度?)

How to measure the running speed of an algorithm? What exactly does it mean for an algorithm to be fast or efficient well?

如何衡量一个算法的运行速度?如何说明一个算法是好的算法,高效的算法?

Of course, we cannot simply measure the “running time” of the algorithm, because the different computers have different configuration.

当然,我们不能简单地用算法的运行时间来衡量,因为不同电脑的配置是不一样的。

Maybe it runs slowly on this computer because this computer is 10 years old!

可能在这个电脑上运行时间慢,是因为这个电脑是 10 年前的电脑!

So you can’t say program A is slower than program B, just based on how long the computer is running the program. Because different computers are configured differently.

因此,不能说 A 程序比 B 程序运行时间慢,仅仅根据电脑运行程序的时间。因为不同的电脑配置不一样。

2 Asymptotic Notation(渐进分析)

Computer scientists and mathematicians developed the method of progressive analysis.

计算机科学家和数学家,提出了渐进分析的方法。

2.1 Big O notation (渐进上界 O 符号)

2.1.1 definition

A function f(x) runs on the order of G(x) if there exists some x value x_0 and some constant C for which f(x) is less than or equal to that constant times G(x) for all x greater than x_0. Then we say that f(x)=O(g(x)).

(1) f(x) \in g(x),
(2) there exists x_0, C,
(3) for all x greater x_0, f(x) \leq C \times g(x).

存在正常数 x_0, C, 对所有的大于 x_0x, 均存在 f(x) \leq C \times g(x)。 表示为 f(x)=O(g(x)).

按照定义来讲,O(g(x)) 应该是一个函数的集合,理论上应该写作 f(x) \in O(g(x)). 但是惯例写作 f(x)=O(g(x)).

for example:

2.1.2 example

for another example(另一个例子):
f(x) = 4x^2 + 16x + 2,
g(x) = x^4,
then, we have:
f(x) = O(g(x)),
that means: 4x^2 + 16x + 2 \leq C \times x^4.

when C=1(当 C 为 1 的时候):

x 4x^2 + 16x + 2 < x^4 T or F
0 2 < 0 F
1 22 < 1 F
2 50 < 16 F
3 86 < 81 F
4 130 < 256 T
f(x) < g(x) T

所以,存在正常数 x_0=4, C=1, 对所有的大于 x_0x, 均存在 f(x) \leq C \times g(x)。因此,g(x)f(x) 的渐进上界。

2.2 Big Ω notation (渐进下界 Ω 符号)

2.2.1 definition

(1) f(x) \in g(x),
(2) there exists x_0, C,
(3) for all x greater x_0, f(x) \geq C \times g(x).

存在正常数 x_0, C, 对所有的大于 x_0x, 均存在 f(x) \geq C \times g(x)。 表示为 f(x)=Ω(g(x)).

2.2.2 example

f(x) = 4x^2 + 16x + 2,
g(x) = x^2,
then, we have:
f(x) = Ω(g(x)),
that means: 4x^2 + 16x + 2 \geq C \times x^2,

when C=1(当 C 为 1 的时候):

x 4x^2 + 16x + 2 > x^2 T or F
f(x) > g(x) T

所以,存在正常数 x_0=0, C=1, 对所有的大于 x_0x, 均存在 f(x) \geq C \times g(x)。因此, g(x)f(x) 的渐进下界。

2.3 Big θ notation (渐进紧界 θ 符号)

2.3.1. definition

f(x) = \theta(g(x)) iff(当且仅当if and only if)
(1)f(x)=O(g(x)),
(2)f(x)=\Omega(g(x)),

f(x)=Ω(g(x))f(x)=O(g(x)),则f(x) = \theta(g(x))

2.3.2 example

f(x) = 4x^2 + 16x + 2,
g(x) = x^2,
then, we have:
f(x) = \theta(g(x)),
than means:f(x) = O(g(x)) and f(x) = \Omega(g(x)).

prove f(x) = O(g(x))

when C=5, x>=20:
4x^2 + 16x + 2 \leq 5 \times x^2
so,f(x) = O(g(x))

prove f(x) = Ω(g(x))

when C=1, x>=0:
4x^2 + 16x + 2 \geq x^2
so,f(x) = Ω(g(x))

you can see this pic:

so,f(x) = θ(g(x)).

0
Posted in 算法设计与分析, 计算机基础知识

参考视频:https://www.youtube.com/watch?v=fpnE6UAfbtU&feature=youtu.be

图片是从视频中截取的,版权问题归 CrashCourse 作者。这里仅仅做学习使用。
(The images were captured from the video. The copyright is reserved for the CrashCourse authors. Here is only for learning purposes.)

真的是觉得原视频里的图片太好了,很直观!

1 只存一个 bit 的电路

1.1 OR 门

当 A 和 B 均输入 0 的时候,输出将为 0。

当 A 输入为 1,B 输入为 0 的时候,输出为 1。
之后,1 回传到 B,

此时 A 和 B 输入都为 1,输出为 1。
这个时候,无论 A 为 0,还是为 1,输出将都为 1。
所以这一个电路可以存储 1。

1.2 AND 门

首先,A和B均输入1,则与操作后,输出为1。

接下来,将A输入0,B输入1,则输出为0。
0回传到B,则B输入为0,输出仍旧为0。

这个时候,无论A输入为0,还是为1,输出将都为0。
所以,这一个电路可以存储0。

1.3 AND-OR 锁存器

OR 门和 AND 门分别可以存储 1 和 0。将这两个门合并起来,就构成了下面的“AND-OR”锁存器。

如上图,当锁存器的SET位置输入为1,RESET位输入为0的时候,输出为1。

而锁存器的RESET位为1的时候,输出为0。(此时无论SET位为1还是0,输出都为0):

当锁存器的SET位和RESET位都为0的时候,电路会输出上一次存储的值(即上次输出为0,这次输出仍为0;上次输出为1,这次输出仍为1):

此时可以看到,电路存储了 1bit 的数据。

因此,它之所以叫做锁存器,就是因为存储了一个特定的值并保持了这个值。我们可以读取这个值(SET 和 RESET 位均为 0),也可以写入新的值(RESET 为 1 的时候写入 0;SET 为 1,RESET 为 0 的时候写入 1)。

1.4 门锁

为了让电路更容易使用,我们希望只有一条“输入线”,可以将它设置为 0 或 1 来存储值。

同时,还需要加一根“允许内存写入线”。启用的时候用允许写入,没启用的时候“锁定”。

此时的电路如下:

当“允许内存写入线”打开时(即置为 1),数据输入线为 1,数据输出为 1,而数据输入线为 0,数据输出为 0:

当“允许内存写入线”关闭时(即置为 0),此时无论数据输入线为 1 还是 0,均不能改变上一次的输出值:

上图状态相当于 AND-OR 锁存器中 SET 位和 RESET 位均为 0。

为了简化电路,将其进行封装。
则电路图为:

如上图,当“允许写入内存线”打开时,数据输入线输入为 1,则数据输出为 1;数据输入线输入为 0,则数据输出为 0。

如上图,当“允许写入内存线”关闭时,此时无论数据输入为 0 还是 1,数据会持续输出上一次的输出值(即值被存起来了)。

2 寄存器

我们并排 8 个锁存器,则可以存 8 位信息。8 位信息正好是 1 个字节的数据。

一组这样的锁存器就叫做“寄存器”!

其中,一个寄存器能够存储的 bit 位叫做“位宽”。

早期电脑用 8 位寄存器,现在的电脑可以用 32 位或 64 位寄存器。

2.1 线性排列锁存器

在写入寄存器之前,要启用里面所有的锁存器,可以用一根“允许写入内存线”连接所有的寄存器,然后将其设为 1(下图标1的线):

然后对于每个锁存器,输入 1 或者 0,便可以存储一个字节的数据:

对于 64 位寄存器来说,这样的电路,需要 64 根输入线,64 根输出线,1 根允许内存写入线,需要 129 根线!

而电脑肯定不是仅仅需要存储 1 个字节,而是很多很多个……

如何减少线的数量呢?
解决方式是使用矩阵。

2.2 矩阵排列锁存器

256 位寄存器(锁存器矩阵阵列):

电路图为:

当某个行和某个列选中的时候,就可以选中某个锁存器。
当行和列的“允许写入内存线”都为 1 的时候,AND 门后输出为 1,表示允许写入选中的锁存器。

使用这种矩阵的形式,(对于16×16的寄存器)只需要 35 根线:每行 16 根,每列 16 根用于选择锁存器,1 条“数据输出线”,1 条“允许写入线”,1 条“允许读取线”。
因此省去了很多线!

多路复用器

为了能够准确地选择到指定的锁存器,需要选择指定的行和指定的列。

可以使用多路复用器,一个多路复用器负责选择行,一个多路复用器负责选择列。

在上述的寄存器中,16行×16列的寄存器,需要一个4位的多路复用器选择行,一个4位的多路复用器选择列。例如,行选择器为0001表示选择第一行。

则,如上图,我们需要8个地址线(4个行选择,4个列选择),1条数据输入线,1条允许内存写入线,1条允许内存读入线。

3 内存条

对寄存器进行排列(不断对寄存器进行封装),就可以得到存储空间更大的内存。

0
Posted in 计算机基础知识

简介

对于一个CPU来说,执行指令一般要经过四个流程:
1.取指 2.译码 3.执行 4.写回

1 取指

在此图中,有程序计数器(PC)、存储器地址寄存器(MAR)、存储器数据寄存器(MDR)、控制器(CU)、内存(Memory)五个组件。内存当前的指令为(ADD:R1,R2),内存地址为101。

  1. 程序计数器指向当前指令在主存的位置。即PC指向内存的101地址。PC所指向的内容会放到指令地址总线上,对指令启动读命令。在一条指令取出后,PC指针指向的地址会加1,即指向102地址。

  2. 控制器将PC中的指令地址通过内部总线传输到MAR中。

  3. MAR存储了指令或数据的内存地址。MAR将控制指令传输到地址总线上。

  4. 控制单元通过MAR提供的地址,发送信号访问存储器并进行读操作。

  5. 存储器通过地址译码器查到存储地址为101的存储单元的内容(ADD:R1,R2),并将存储单元的内容传送到MDR中。

  6. MDR中保存的数据通过内部总线传送给IR寄存器(指令寄存器)。

至此,取指令部分完成!

2 译码

  1. MDR中保存的数据通过内部总线传送给IR寄存器。指令包含操作数和地址码两部分。

  2. IR寄存器会分析出操作码部分和地址码部分。将操作码送入解码器,解析出ADD是加操作。

  3. 控制单元接收到解码器译码后的指令后,发出取数的操作命令。

  4. (对应图中6-2)IR寄存器中的地址码部分会送到MAR寄存器,从内存中读出R1,R2中的数。读出的R1,R2会存储在MDR中,之后送入ACC(累加器)。

3 执行

根据不能的操作码,进行不同的操作。

3.1 加减法

ACC:累加器
ALU:算术逻辑单元
MQ:乘商寄存器

第一步:取数操作将 被加数/被减数 存取至ACC寄存器中。

第二步:将[M]地址空间的数据存放在X寄存器中。

第三步:ACU累加器对数进行 加/减 操作,结果存放在ACC中。

3.2 乘法

第一步:取数操作将 被乘数 存取至ACC寄存器中。

第二步:将[M]地址空间的数据存放在MQ寄存器中。

第三步:将ACC中的数据存放在X寄存器中。

第四步:将ACC寄存器清空。

第五步:ACU累加器对数进行 乘 操作,高位存放在ACC中,低位存放在MQ寄存器中。

3.3 除法

第一步:取数操作将 被除数 存取至ACC寄存器中。

第二步:将[M]地址空间的数据存放在X寄存器中。

第三步:ACU累加器对数进行 除 操作,余数存放在ACC中,商存放在MQ中。

4 写回

读取和写回操作其实执行存取指令。

写回:将ACC中的数据送至MDR寄存器,然后进行存操作。

0
Posted in 计算机基础知识