时间复杂度 Tk 怎么计算呢？
假设树的节点个数是 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 怎么计算呢？
页:
[1]