时间空间复杂度的解释
博客专区 > YKIT 的博客 > 博客详情
时间空间复杂度的解释
YKIT 发表于2年前
时间空间复杂度的解释
  • 发表于 2年前
  • 阅读 69
  • 收藏 8
  • 点赞 0
  • 评论 0

标题:腾讯云 新注册用户域名抢购1元起>>>   

摘要: 复杂度

 

何为时间空间复杂度?

 

1》空间复杂度ON):

一个算法在运行过程中临时占用存储空间大小的量度。一个算法的空间复杂度只考虑在运行过程中为局部变量分配的存储空间的大小,它包括为参数表中形参变量分配的存储空间和为在函数体中定义的局部变量分配的存储空间两个部分。

举例:

1)如一个算法的空间复杂度为一个常量,即不随被处理数据量n的大小而改变时,可表示为O(N)

2)当一个算法的空间复杂度与以2为底的n的对数成正比时,可表示为O(log2n)

3)当一个算法的空间复杂度与n成线性比例关系时,可表示为O(n)

4)递归函数的时间复杂度是O(N),因每次递归都需保存函数内部局部变量的存储空间。

 

2》时间复杂度

它定量描述了该算法的运行时间。算法的基本操作重复执行的次数是模块n的某一个函数f(n),因此,算法的时间复杂度记做:T(n)=O(f(n))。随着模块n的增大,算法执行的时间的增长率和 f(n) 的增长率成正比,所以 f(n) 越小,算法的时间复杂度越低,算法的效率越高。

 

常见的时间复杂度有:

常数阶O(1),对数阶O(log2n),线性阶O(n),

线性对数阶O(nlog2n),平方阶O(n^2),立方阶O(n^3),...

k次方阶O(n^k),指数阶O(2^n)。随着问题规模n的不断增大,上述时间复杂度不断增大,算法的执行效率越低。

 

 

 

 

共有 人打赏支持
YKIT
粉丝 14
博文 29
码字总数 2759
作品 3
×
YKIT
如果觉得我的文章对您有用,请随意打赏。您的支持将鼓励我继续创作!
* 金额(元)
¥1 ¥5 ¥10 ¥20 其他金额
打赏人
留言
* 支付类型
微信扫码支付
打赏金额:
已支付成功
打赏金额: