算法的分析是我们计算机科学的一项重要事务,算法的设计也是我们程序中比较重要的一块,算法属于数学领域,相对稳定,我们做应用软件更多的是组合算法,利用算法,抽象算法,软件透视图从算法提升到架构,算法被封装,我们将精力要大部分放在设计软件的灵活性,伸缩性和维护性,以让软件像条狗一样为我们服务。
算法是求解一个特定问题的有限个良好定义的相继步骤的指令列表,解决这个特定问题往往可以有多种算法,我们需要分析这些算法,以找到一个高效率的算法,算法的效率衡量标准一般就是时间复杂度和空间复杂度。
算法的复杂性分析其实就是找出一个数学函数f(n),n是输入数据的规模,一般空间复杂度是数据规模的倍数,所以我们说复杂度一般就是指时间复杂度,要分析一个算法的时间复杂度,只要找到这个算法的基本原操作,然后和输入规模n建立函数f(n)就可以了。由于一个算法的执行时间会受到输入数据的某些特性影响,所以需要抛弃这个影响而关注算法的最坏情况和平均情况,最坏是指这个算法执行的最大时间,平均则需要先假定输入数据的一个概率分布,通过概率来计算复杂度,这个要复杂些,对于很多算法,其平均情况的复杂性常与最坏情况的复杂性成比例。
得到函数f(n)之后,比如2n*n + n +1,这样表示算法复杂度不是太直观,所以我们只关心这个函数的增长率,这通常由f(n)于某标准函数相比较而的,例如指数函数,对数函数,线性对数函数以及线性函数,二次函数,三次函数这些多项式函数等等,将f(n)与一些标准函数相比较的一种方法我们用大O记号,这个大O的定义如下:
设f(x)与g(x)是定义于R或R的子集上的任意两个函数,f(x)于g(x)同阶则记作 f(x) = O(g(x))
如果存在实数k和正常数C使得对于所有的x>k有| f(x) | <= C | g(x) |
明确了这个过程,我们就可以分析各个算法的复杂度
大O表示法是用于算法的上界,如果要表示算法的下界就要使用符号,表示上下界则需要
下面贴出常用排序算法的时间复杂度
- 大小: 110.5 KB
- 大小: 853 Bytes
- 大小: 856 Bytes
分享到:
相关推荐
模型算法之数学建模32种常规方法.zip
这个是数学建模的一个程序,希望你可以用的上,上面详细的介绍了方法
遗传算法的数学基础 书籍 PDF格式 遗传算法的数学基础 书籍 PDF格式
数学建模30个常用算法(Python)数学建模30个常用算法(Python)数学建模...算法(Python数学建模30个常用算法(Python)数学建模30个常用算法(Python)数学建模30个常用算法(Python)数学建模30个常用算法(Python)
数学建模之十大算法.rar 数学建模之十大算法.rar 数学建模之十大算法.rar
贪心算法的数学原理 贪心算法的数学原理 贪心算法的数学原理
数学建模算法,包括聚类、神经网络等算法,有例子
遗传算法数学基础
数学建模数学建模数学建模数学建模数学建模数学建模数学建模数学建模数学建模数学建模数学建模数学建模数学建模
没有组合数学的基础,就无法深入研究算法和分析算法。竞赛试题的形式和类型干变万化,但通常蕴涵某个组合数学方面的问题,这些问题很能推动人们去思索,它们的解法也常常是机智和精巧的。因此,对于参与奥林匹克情息...
matlab经典算法的程序源码 数学建模算法汇总资料: matlab经典算法的程序源码 十大算法讲义.pdf 排队模型.pdf 数学建模算法全收录.pdf 数学建模算法大全.pdf 算法大全第01章__线性规划.pdf 算法大全第02章_整数规划....
算法中常用的数学工具,包括生成函数、特征方程、递归推导,主要用于计算算法递归函数的算法复杂度。
遗传算法是目前公认的最有效的全局最优化方法之一,本书详细讲解了遗传算法的数学基础,通俗详细!
数学建模算法大全,包括群智能,贪婪算法,神经网络等
涵盖数学建模所用的算法,每一章节有相应的matlab算法实现的代码,适合参加数学建模的新手作为入门的第一本百科全书!
这是数学建模中常用的十大算法之一,欢迎大家下载学习。希望能对大家建模有所帮助。
数学建模算法总结,共799页,非常全面,适合参加数学建模大赛的同学们参考。