论文部分内容阅读
随着计算机技术的高速发展,数学知识在计算机技术发展中,尤其是在算法设计中处于极其重要的地位.同时,用数学的思维解决各种程度算法难题也是十分重要的. 在计算机程序设计中,采用高效而简洁的算法可以提高程序的稳定性和可读性,不同的算法中蕴涵着不同的数学思想,将数学思想融入到算法构造以及程序设计中是十分重要的.
1. 算法描述
算法概念是计算机科学的基础. 许多通用问题都有算法,而设计高效的算法对于开发大型计算机系统起着至关重要的作用. 简单地说,所谓算法就是定义良好的计算过程,它取一个或一组值作为输入,并产生一个或一组值作为输出. 亦即,算法就是一系列的计算步骤,用来将输入数据转换成输出结果.
数学是自然科学的基础,计算机科学实际上是数学的一个分支. 计算机理论其实是很多数学知识的融合,算法更是数学知识的合理和巧妙的运用. 高中数学作为数学的基础,其基本思想也在算法中得以体现和应用.
2. 算法性能分析
算法的空间复杂性和时间复杂性是评价算法的主要指标. 程序的空间复杂性是程序从开始执行到完成所需的存储空间的数量;程序的时间复杂性是程序从开始执行到完成所需的计算时间.
程序所需的存储空间包括固定的空间需求和可变的空间需求. 任意程序的总的空间需求S(p) = c + Sp(I). 其中,c是一个常数,表示固定的存储空间需求,在分析程序的空间复杂性时,通常只关心可变的空间需求.
程序p所需时间T(p)是其编译时间和运行时间的总和. 其中编译时间不依赖于问题实例的特征.因此,真正关注的只是程序的执行时间Tp. 例如,假定有一个进行数字加法和减法的简单程序,令n表示该程序的实例特征,可将Tp(n)表示为Tp(n) = CaADD(n) + CsSUB(n) + ClLDA(n) + CstSTA(n),其中,Ca,Cs,Cl,Cst是常数,表示执行每个操作所需的时间,而ADD,SUB,LDA,STA表示执行实例特征为n的程序时所需的加法,减法,读取数,存入数操作的次数.
3. 数学的应用
在时间复杂度中,定义f(n) = O(g(n)),当且仅当存在正的常数c和 n0,使得对于所有的n,当n ≥ n0时,有f(n) ≤ cg(n). 我们通过数学证明,来分析一些算法的复杂性.
定理1 如果f(n) = amnm + … + a1n + a0,则f(n) = O(nm) .
对于所有的n ≥ 2,都有3n + 2 ≤ 4n,所以有3n + 2 = O(n). 对于所有的100n + 6 ≤ 101n,所以100n + 6 = O(n). 对于所有的n ≥ 5,都有10n2 + 4n + 2 ≤ 11n2,所有10n2 + 4n + 2 = O(n2). 由于对于任意常数c和所有的n ≥ n0, 3n + 2大于c,所有3n + 2 = O(1). 同样的,10n2 + 4n + 2 ≠ O(n2) . 我们通过数学证明来验证定理1.
证明 f(n)≤ |ai|ni ≤ nm |ai|ni-m ≤nm |ai|,当n ≥ 1 时,f(n) = O(nm) .
由定理1可知,对于任意c1,c2,c3都为非负常数,f1(n) = c1n2 + c2n + c3 = O(n2),f2(n) = c1n + c2 = O(n) . 一般情况下,复杂度为O(n2)比复杂度为O(n)的程序执行得快. 对于小的n值,两个程序可能执行得都比较快. 当n ≤ 97时,有n2 + 2n + 1<100n,而当n > 97时,n2 + 2n + 1>100n,我们把n = 97称为平衡点. 可以证明,如果平衡点为0,那么复杂性为O(n)的程序相比于复杂性为O(n2)的程序,总以较快的速度运行. 据此,我们得出如下结论.
推论1 复杂性为O(ni)的程序比复杂性为O(nj)的程序运行得快,其中i和j为非负数,且i < j .
4. 实际问题
在互联网和手机搜索,如果要找附近的咖啡馆,那么搜索引擎该怎么处理这个请求呢?最简单的办法就是把整个城市的咖啡馆都找出来,然后计算出它们的所在位置与你之间的距离,再进行排序,然后返回最近的结果. 算法的伪代码如下:
FindNearestCoffeeBar(n)
near = 1;
For i = 2 to n
Do calculate distance between searcher and coffee bar i
If coffee bar i is nearer than coffer bar near
Then near = i;
Coffee bar near is search result.
此时对于每次搜索,都需要找到每个咖啡馆,因此整个算法的复杂度为O(n) .
这么做也许是最直观的,但绝对不是最迅速的. 如果一个城市只有为数不多的咖啡馆,那么这么做应该没什么问题,反正计算量不大. 但如果一个城市里有很多咖啡馆,又有很多用户都需要类似的搜索,那么服务器所承受的压力就大多了. 在这种情况下,我们该怎样优化算法呢?
首先,我们可以把整个城市的咖啡馆做一次“预处理”. 比如,把一个城市分成若干个“格子(grid)”,格子数目为m,每个咖啡馆唯一分布在一个格子中. 此时搜索算法的伪代码如下:
FindNearestCoffeeBar(n)
near_grid= 1;
For i = 2 to m
Do calculate distance between searcher and grid i
If coffee bar i is nearer than grid near_grid
Then near_grid = i;
grid near_grid is found grid.
find the nearest coffee bar in the found grid
near = 1;
For i = 2 to n
Do calculate distance between searcher and coffee bar i
If coffee bar i is nearer than coffer bar near
Then near = i;
Coffee bar near is search result.
我们先在大范围内搜索,将问题域缩小,然后在小范围内求解. 如何划分格子才能使我们的运算量最小呢?
假设总共有n个咖啡店,咖啡店均匀分布,我们将咖啡店划分为m个格子,则每个格子内的咖啡店数目为 ,则算法的运行次数为 m +.
根据数学知识,sum ≥ 2 ,当且仅当m =时,即m =时,取等号,此时我们算法的复杂度为O( ). 根据推论1,优化的算法比原算法运行速度快.
5. 结语
算法既是计算机理论和实践的核心,也是数学的最基本内容之一. 高中数学作为我们学习数学的基础,其不仅在算法中不断体现和应用,同时,更是组合数学､密码学､计算机图形学等计算机课程的基础. 很多数学基础很好的人,一旦熟悉了某种计算机语言,他可以很快地理解一些算法的精髓,使之能够运用自如,并可能写出时间与空间复杂度都有明显改善的算法. 因此,我们在高中阶段就应该形成“算法思维”,培养自己的数学修养.
注:“本文中所涉及到的图表､注解､公式等内容请以PDF格式阅读原文｡”
1. 算法描述
算法概念是计算机科学的基础. 许多通用问题都有算法,而设计高效的算法对于开发大型计算机系统起着至关重要的作用. 简单地说,所谓算法就是定义良好的计算过程,它取一个或一组值作为输入,并产生一个或一组值作为输出. 亦即,算法就是一系列的计算步骤,用来将输入数据转换成输出结果.
数学是自然科学的基础,计算机科学实际上是数学的一个分支. 计算机理论其实是很多数学知识的融合,算法更是数学知识的合理和巧妙的运用. 高中数学作为数学的基础,其基本思想也在算法中得以体现和应用.
2. 算法性能分析
算法的空间复杂性和时间复杂性是评价算法的主要指标. 程序的空间复杂性是程序从开始执行到完成所需的存储空间的数量;程序的时间复杂性是程序从开始执行到完成所需的计算时间.
程序所需的存储空间包括固定的空间需求和可变的空间需求. 任意程序的总的空间需求S(p) = c + Sp(I). 其中,c是一个常数,表示固定的存储空间需求,在分析程序的空间复杂性时,通常只关心可变的空间需求.
程序p所需时间T(p)是其编译时间和运行时间的总和. 其中编译时间不依赖于问题实例的特征.因此,真正关注的只是程序的执行时间Tp. 例如,假定有一个进行数字加法和减法的简单程序,令n表示该程序的实例特征,可将Tp(n)表示为Tp(n) = CaADD(n) + CsSUB(n) + ClLDA(n) + CstSTA(n),其中,Ca,Cs,Cl,Cst是常数,表示执行每个操作所需的时间,而ADD,SUB,LDA,STA表示执行实例特征为n的程序时所需的加法,减法,读取数,存入数操作的次数.
3. 数学的应用
在时间复杂度中,定义f(n) = O(g(n)),当且仅当存在正的常数c和 n0,使得对于所有的n,当n ≥ n0时,有f(n) ≤ cg(n). 我们通过数学证明,来分析一些算法的复杂性.
定理1 如果f(n) = amnm + … + a1n + a0,则f(n) = O(nm) .
对于所有的n ≥ 2,都有3n + 2 ≤ 4n,所以有3n + 2 = O(n). 对于所有的100n + 6 ≤ 101n,所以100n + 6 = O(n). 对于所有的n ≥ 5,都有10n2 + 4n + 2 ≤ 11n2,所有10n2 + 4n + 2 = O(n2). 由于对于任意常数c和所有的n ≥ n0, 3n + 2大于c,所有3n + 2 = O(1). 同样的,10n2 + 4n + 2 ≠ O(n2) . 我们通过数学证明来验证定理1.
证明 f(n)≤ |ai|ni ≤ nm |ai|ni-m ≤nm |ai|,当n ≥ 1 时,f(n) = O(nm) .
由定理1可知,对于任意c1,c2,c3都为非负常数,f1(n) = c1n2 + c2n + c3 = O(n2),f2(n) = c1n + c2 = O(n) . 一般情况下,复杂度为O(n2)比复杂度为O(n)的程序执行得快. 对于小的n值,两个程序可能执行得都比较快. 当n ≤ 97时,有n2 + 2n + 1<100n,而当n > 97时,n2 + 2n + 1>100n,我们把n = 97称为平衡点. 可以证明,如果平衡点为0,那么复杂性为O(n)的程序相比于复杂性为O(n2)的程序,总以较快的速度运行. 据此,我们得出如下结论.
推论1 复杂性为O(ni)的程序比复杂性为O(nj)的程序运行得快,其中i和j为非负数,且i < j .
4. 实际问题
在互联网和手机搜索,如果要找附近的咖啡馆,那么搜索引擎该怎么处理这个请求呢?最简单的办法就是把整个城市的咖啡馆都找出来,然后计算出它们的所在位置与你之间的距离,再进行排序,然后返回最近的结果. 算法的伪代码如下:
FindNearestCoffeeBar(n)
near = 1;
For i = 2 to n
Do calculate distance between searcher and coffee bar i
If coffee bar i is nearer than coffer bar near
Then near = i;
Coffee bar near is search result.
此时对于每次搜索,都需要找到每个咖啡馆,因此整个算法的复杂度为O(n) .
这么做也许是最直观的,但绝对不是最迅速的. 如果一个城市只有为数不多的咖啡馆,那么这么做应该没什么问题,反正计算量不大. 但如果一个城市里有很多咖啡馆,又有很多用户都需要类似的搜索,那么服务器所承受的压力就大多了. 在这种情况下,我们该怎样优化算法呢?
首先,我们可以把整个城市的咖啡馆做一次“预处理”. 比如,把一个城市分成若干个“格子(grid)”,格子数目为m,每个咖啡馆唯一分布在一个格子中. 此时搜索算法的伪代码如下:
FindNearestCoffeeBar(n)
near_grid= 1;
For i = 2 to m
Do calculate distance between searcher and grid i
If coffee bar i is nearer than grid near_grid
Then near_grid = i;
grid near_grid is found grid.
find the nearest coffee bar in the found grid
near = 1;
For i = 2 to n
Do calculate distance between searcher and coffee bar i
If coffee bar i is nearer than coffer bar near
Then near = i;
Coffee bar near is search result.
我们先在大范围内搜索,将问题域缩小,然后在小范围内求解. 如何划分格子才能使我们的运算量最小呢?
假设总共有n个咖啡店,咖啡店均匀分布,我们将咖啡店划分为m个格子,则每个格子内的咖啡店数目为 ,则算法的运行次数为 m +.
根据数学知识,sum ≥ 2 ,当且仅当m =时,即m =时,取等号,此时我们算法的复杂度为O( ). 根据推论1,优化的算法比原算法运行速度快.
5. 结语
算法既是计算机理论和实践的核心,也是数学的最基本内容之一. 高中数学作为我们学习数学的基础,其不仅在算法中不断体现和应用,同时,更是组合数学､密码学､计算机图形学等计算机课程的基础. 很多数学基础很好的人,一旦熟悉了某种计算机语言,他可以很快地理解一些算法的精髓,使之能够运用自如,并可能写出时间与空间复杂度都有明显改善的算法. 因此,我们在高中阶段就应该形成“算法思维”,培养自己的数学修养.
注:“本文中所涉及到的图表､注解､公式等内容请以PDF格式阅读原文｡”