揭秘算法优劣：时间与空间复杂度

一、如何衡量一个算法的好坏看下面的一个代码是求斐波那契数列的算法这个算法好不好为什么二、算法效率算法效率的分析分为两种一种是时间效率另一种就是空间效率。时间效率就是时间复杂度空间效率就是空间复杂度。时间复杂度主要衡量一个算法的运行效率而空间复杂度主要衡量一个算法所需要的一个额外空间。在计算机早期的发展中内存是很小的所以空间复杂度显得至关重要而现如今时间复杂度显得格外重要。三、时间复杂度1.时间复杂度的概念时间复杂度不用算真实运行时间只估算代码执行次数用来衡量算法运行快慢用大 O 符号O()表示。2.大O的渐进表示法而通过计算可以得到fucn1的执行次数为fucn1N N²2N10实际计算时间复杂度我们不需要计算执行的精确的次数只需要计算大概的次数用大O渐进法就够用了3.推导大O渐进法1、用常数1取代运行时间中的所有加法常数。2、在修改后的运行次数函数中只保留最高阶项。3、如果最高阶项存在且不是1则去除与这个项目相乘的常数。得到的结果就是大O阶。则这个fucn1 的时间复杂度是 O(N²)。4.常见的时间复杂度计算示例1.示例2.示例3.示例4.示例5.示例6.示例7.四、空间复杂度空间复杂度是对一个算法在运行过程中临时占用存储空间大小的量度 。空间复杂度不是程序占用了多少bytes的空 间因为这个也没太大意义所以空间复杂度算的是变量的个数。空间复杂度计算规则基本跟时间复杂度类似也 使用大O渐进表示法。示例1.示例2.示例3.递归调用了N次开辟了N个栈帧每个栈帧使用了常数个空间。空间复杂度为O(N)