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

作者: 橡树人 | 来源:发表于2020-03-02 07:33 被阅读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设计依赖算法
网络寻路极其依赖算法
编译器、解释器、汇编器大量使用算法

网友评论

算法导论

本文标题：第一章算法在计算中的角色

本文链接：https://www.haomeiwen.com/subject/bypukhtx.html

延伸阅读

深度阅读

您也可以注册成为美文阅读网的作者，发表您的原创作品、分享您的心情！

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

1.1节算法

1.2节算法是一种技术

算法的效率问题

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

相关文章

网友评论

延伸阅读

深度阅读

栏目导航

热点阅读

算法导论

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

1.1节 算法

1.2节 算法是一种技术

算法的效率问题

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

相关文章

网友评论

延伸阅读

深度阅读

栏目导航

热点阅读

算法导论

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

1.1节算法

1.2节算法是一种技术