算法:解决特定问题求解步骤的描述在计算机中表现为指令的有限序列,每条指令可表示一条或多个操作
设计算法的要求:正确性、可读性、健壮性、时间效率高且涳间使用率低、简单性。
???时间复杂度是指执行算法所需要的计算工作量简单说时间复杂度是语句执行的此数;而空间复杂度怎么算是指执行这个算法所需要的内存空间。
算法存在好坏、平均和最坏情况:
1.最坏情况:任意输入规模的最大运行次数(上届)
2.平均情况:任意输入规模的期望运行次数
3.最好情况:任意输入规模的最小运行次数通常最好情况不会出现(下届)
???在实际中通常最关注的是算法的最坏运行情况。理由如下:
1.一个算法的最坏情况的运行时间是在任意输入下的运行时间上届
2.对于某些算法 最坏的情况出现的较为頻繁
3.大体上看,平均情况与最坏情况一样差
??? 那时间复杂度和空间复杂度怎么算如何计算呢
一、时间复杂喥的计算方法
1.用常数1取代运行时间中的所有加法常数
2.在修改后的运行次数函数中,只保留最高阶项
3.如果最高阶项系数存在且不是1则去除與这个项相乘的常数
1.对于非递归算法:可以直观的算出它的执行次数
2.对于递归算法的时间复杂度:递归总次数*每次递归次数
对于这个求n的阶乘的算法:
一、空间复杂度怎么算的计算方法
空间复杂度怎么算:不是计算实际占用的空间,而是计算整个算法的辅助空间单元的个数与问題的规模没有关系
1.忽略常数,用O(1)表示
2.递归算法的空间复杂度怎么算=递归深度*每次递归所要的辅助空间
3.对于单线程来说递归有运行时堆栈,求的是递归最深的那一次压栈所耗费的空间的个数因为递归最深的那一次所耗费空间足以容纳它所有递归过程。递归是要返回上一层嘚所以它所需要的空间不是一直累加起来的。