时间复杂度和空间复杂度

时间:2022-01-18 07:42:02

事前分析估算方法:程序编写前依据统计方法对算法进行估算。

程序运行所耗时间主要取决于:

  ——算法采用的策略;

  ——编译产生的代码质量;

  ——问题的输入规模

  ——机器执行指令的速度

  抛开和计算机软硬件相关的因素,程序运行时间依赖于算法的好坏和问题的输入规模

研究算法的复杂度侧重于研究算法随着输入规模扩大增长量的一个抽象,而不是精确定位执行多少次。

时间复杂度

(说求复杂度通常指的是时间复杂度)

算法的时间复杂度,即算法的时间量度,记作:T(n)=O(f(n))  T(n)语句执行次数(=时间),n问题规模 

随着n增大,T(n)增长最慢的算法为最优算法。

常见的时间复杂度:

时间复杂度和空间复杂度

时间复杂度和空间复杂度

推导大O阶方法

  ——用常数1取代运行时间中的所有加法常数;

  ——修改后的运行次数函数中,只保留最高阶项

  ——如果最高阶存在且不是1,则去除该项系数

线性阶(单循环)、平方阶(嵌套循环)、对数阶

  关于对数阶:

时间复杂度和空间复杂度

  执行次数x通过 2^x=n算出,x=log(2)n

 空间复杂度

S(n)=O(f(n))  n问题规模,f(n)为语句关于n所占存储空间的函数。