现在的位置: 首页 > web前端 > 正文

时间复杂度与空间复杂度分析

2020年07月08日 web前端 ⁄ 共 1079字 ⁄ 字号 评论关闭

  时间复杂度是同一问题可用不同算法解决,而一个算法的质量优劣将影响到算法乃至程序的效率。算法分析的目的在于选择合适算法和改进算法。计算机科学中,算法的时间复杂度是一个函数,它定性描述了该算法的运行时间。这是一个关于代表算法输入值的字符串的长度的函数。时间复杂度常用大O符号表述,不包括这个函数的低阶项和首项系数。使用这种方式时,时间复杂度可被称为是渐近的,它考察当输入值大小趋近无穷时的情况。


  时间复杂度与空间复杂度分析


  1.算法的时间复杂度分析:


  假设一个算法是由n条指令序列所构成的集合,则:


  算法的执行时间=\sum^{n}_{i=1}x_i(指令序列(i)的执行次数*单个序列(i)的执行时间)


  算法的执行时间与指令序列的执行次数之和成正比(单个序列的执行时间大约相同)。通过计算程序中语句频度之和估算一个算法的执行时间,所以语句频度就是语句重复执行的次数。


  时间复杂度T(n)=O(算法中所有语句的执行次数的和)


  最好,最坏和平均时间复杂度。


  2.算法的空间复杂度分析:


  程序运行所需的存储空间包括两部分。


  (1)固定空间需求:主要包括算法本身的程序代码,常量,变量所占的空间;


  (2)可变空间需求:与所处理问题的规模有关。主要包括输入的数据元素所占的存储空间和程序运行过程中所需要的额外空间。


  由于固定空间基本由问题的规模决定,所以在计算算法的空间复杂度时,主要考虑程序运行过程中的额外空间。


  时间复杂度和空间复杂度是评价算法优缺点的重要指标


  大O符号是由德国数论学家保罗·巴赫曼(PaulBachmann)在其1892年的著作《解析数论》(AnalytischeZahlentheorie)首先引入的。而这个记号则是在另一位德国数论学家艾德蒙·朗道(EdmundLandau)的著作中才推广的,因此它有时又称为朗道符号(Landausymbols)。代表“orderof...”(……阶)的大O,最初是一个大写的希腊字母'Ο'(omicron),现今用的是大写拉丁字母‘O’,但从来不是阿拉伯数字‘0’。


  空间复杂度(SpaceComplexity)是对一个算法在运行过程中临时占用存储空间大小的量度,记做S(n)=O(f(n))。比如直接插入排序的时间复杂度是O(n^2),空间复杂度是O(1)。而一般的递归算法就要有O(n)的空间复杂度了,因为每次递归都要存储返回信息。一个算法的优劣主要从算法的执行时间和所需要占用的存储空间两个方面衡量。


  总之,时间复杂度与空间复杂度给大家简单介绍了一些,希望大家看看。

抱歉!评论已关闭.