数学中国

 找回密码
 注册
搜索
热搜: 活动 交友 discuz
查看: 1120|回复: 0

时间复杂度 Tk 怎么计算呢?

[复制链接]
发表于 2022-7-5 16:23 | 显示全部楼层 |阅读模式
假设树的节点个数是 n,树的深度是 k。绘制这颗完整的树,空间复杂度是 O(n);时间复杂度是 O(n)。
因为是数组存储,需要存储 n 个节点,所以空间复杂度是 O(n)。
如果要绘制这颗完整的树,按照上面的算法步骤需要逐层展开,程序最外层循环次数是 k,内层循环的调整次数如下:
假设第 k 层的个数为 Sk(Sk < n),调整执行次数为 Tk。
第 1 层的执行次数为 T1:T1 = S1
第 2 层的执行次数为 T2:T2 = T1 + (S1 + S2)
第 3 层的执行次数为 T3:T3 = T2 + (S1 + S2 + S3)
第 4 层的执行次数为 T4:T4 = T3 + (S1 + S2 + S3 + S4)
...
第 k 层的执行次数为 Tk:Tk = Tk-1+  (S1 + S2 + ... + Sk) = Tk-1+  n = S1 + (S1 + S2) + (S1 + S2 + S3) + ... + n
时间复杂度 Tk 怎么计算呢?
您需要登录后才可以回帖 登录 | 注册

本版积分规则

Archiver|手机版|小黑屋|数学中国 ( 京ICP备05040119号 )

GMT+8, 2024-3-29 03:19 , Processed in 0.079101 second(s), 15 queries .

Powered by Discuz! X3.4

Copyright © 2001-2020, Tencent Cloud.

快速回复 返回顶部 返回列表