一 . 概念
我们评估一种算法的优劣，可以使用它的时间复杂度和空间复杂度来衡量(一个算法的优劣主要从算法的执行时间和所需要占用的存储空间两个方面衡量)，当然，不作特殊说明，我们一般讨论的是该算法的最坏时间复杂度和最坏空间复杂度，即分析最坏情况以估算算法的执行时间的上界。在下面，我们会详细讨论关于斐波那契数列等函数实现的各种算法的时间复杂度和空间复杂度。
二. 时间复杂度
我们一般采用大O渐进表示法描述一个算法的时间复杂度。时间复杂度主要讨论的是算法执行的次数。
一般算法时间复杂度O(n)的表示方法：
（1）用常数1取代运行时间中的所有加法常数 ；
（2）在修改后的运行次数函数中，只保留最高阶项；
（3）如果最高阶项系数存在且不是1，则去除与这个项相乘的常数；
（4）递归算法的时间复杂度 == 递归总次数*每次递归的次数
空间复杂度 == 递归的深度（即树的高度）
常见的时间复杂度有：
常数阶O(1),
对数阶O(log2 n),
线性阶O(n),
线性对数阶O(n log2 n),
平方阶O(n^2)，
立方阶O(n^3)
k次方阶O(n^K),
指数阶O(2^n)。
随着n的不断增大，时间复杂度不断增大，算法花费时间越多,通常我们计算时间复杂度都是计算最坏情况
三. 空间复杂度
空间复杂度是对一个算法在运行过程中临时占用存储空间大小的量度。
一个程序的空间复杂度是指运行完一个程序所需内存的大小。利用程序的空间复杂度，可以对程序的运行所需要的内存多少有个预先估计。一个程序执行时除了需要存储空间和存储本身所使用的指令、常数、变量和输入数据外，还需要一些对数据进行操作的工作单元和存储一些为现实计算所需信息的辅助空间。程序执行时所需存储空间包括以下两部分。
固定部分: 这部分空间的大小与输入/输出的数据的个数多少、数值无关。主要包括指令空间（即代码空间）、数据空间（常量、简单变量）等所占的空间。这部分属于静态空间。
可变空间: 这部分空间的主要包括动态分配的空间，以及递归栈所需的空间等。这部分的空间大小与算法有关。
一个算法所需的存储空间用f(n)表示。S(n)=O(f(n)) 其中n为问题的规模，S(n)表示空间复杂度。
计算方法：
①忽略常数，用O(1)表示
②递归算法的空间复杂度=递归深度N*每次递归所要的辅助空间
③对于单线程来说，递归有运行时堆栈，求的是递归最深的那一次压栈所耗费的空间的个数，因为递归最深的那一次所耗费的空间足以容纳它所有递归过程。
网友评论