第一章算法在计算中的角色

2020-03-02 本文已影响0人橡树人

什么是算法？
为什么算法值得研究？
跟在计算机中使用的其他技术相比，算法处在什么地位？

1.1节算法

第一种定义
算法是任意一个定义清晰的计算过程，该计算过程取一个值或者一组值作为输入，计算出一个值或者一组值作为输出。
根据该非正式的算法定义可以导出哪些结论？
一个算法就是将输入转换成输出的一系列的计算步骤。

第二种定义
一个算法就是解决描述清楚的可计算问题的一种工具。
对问题的描述就是描述了输入和输出之间的关系，算法实际上是描述了实现这种输入和输出关系的计算过程。

排序问题
定义
输入：一系列的数 $a_1, a_2,..., a_n$ 。

输出： $a_1^{'},a_2^{'},..., a_n^{'}$ ，其中满足 $a_1^{'}\leq a_2^{'}\leq ...\leq a_n^{'}$ 。

1.2节算法是一种技术

算法是一种帮助你有效率地使用计算时间和空间等资源的技术。

因为计算机的运行速度虽然很快，但不是无穷快；计算机的内存虽不贵，但也不是免费的，所以计算所用时间和计算所需空间是一种有限的资源。

因为计算所需时间和计算所需空间是一种有限的资源，所以需要有效地使用。

算法的效率问题

假设有两台计算机，分别是计算机A和计算机B，其中计算机A可在1秒钟执行1百亿(量级为 $10^{10}$ )条指令，计算机B可在1秒钟内执行1千万(量级为 $10^7$ )条指令。

假设运行在计算机A上的插入排序算法代码实现满足：

如果要对 $n$ 个数排序，则有 $2n^2$ 条指令；

运行在计算机B上的归并排序算法的代码实现满足：

如果要对 $n$ 个数排序，则有 $50n\log(n)$ 条指令；

问题1 现有1千万(量级为 $10^7$ )个数，占据的内存大约为76.3MB，让较快的计算机A运行插入排序，让较慢的计算机B运行归并排序。
则排序算法在计算机A上花费时间为
$\frac{2*(10^7)^2}{10^{10}}=2*10^4秒≈5.5小时，$
排序算法在计算机B上花费的时间为
$\frac{50*10^7*\log_2(10^7)}{10^7}≈1163秒≈20分钟。$

问题2 现有1亿(量级为 $10^8$ )个数，占据分内存大约是763MB，让较快的计算机A运行插入排序，让较慢的计算机B运行归并排序。
则排序算法在计算机A上花费时间为
$\frac{2*(10^8)^2}{10^{10}}=2*10^6秒≈555.55小时≈23天，$
排序算法在计算机B上花费的时间为
$\frac{50*10^8*\log_2(10^8)}{10^7}≈13230秒≈3.675小时。$

规律：

随着问题的规模的增大，归并排序的优势也会越来越大；
使用一个运行时间增长较慢的算法，即使用了较差的编译器，算法在不同计算机上的运行时间可相差17倍；

算法跟计算机里其他技术的关系

几个简单的观察：

系统的性能不仅取决于快速的硬件，而且取决于选择高效的算法。
随着计算机能力的不断提升，使用计算机来解决的问题的规模也比之前的大了。
更大规模的问题使得区分算法的效率变得尤为重要。

算法处在现代计算机技术的核心位置。

硬件设计会使用算法
图形用户界面GUI设计依赖算法
网络寻路极其依赖算法
编译器、解释器、汇编器大量使用算法

第一章算法在计算中的角色

1.1节算法

1.2节算法是一种技术

算法的效率问题

算法跟计算机里其他技术的关系

猜你喜欢

热点阅读

第一章 算法在计算中的角色

1.1节 算法

1.2节 算法是一种技术

算法的效率问题

算法跟计算机里其他技术的关系

猜你喜欢

热点阅读

第一章算法在计算中的角色

1.1节算法

1.2节算法是一种技术