复杂度计算中，8T(n/2)为什么大于n方？

Question

在递归复杂度计算时，T(n) = aT(n / b) + n的x方时，代入 a=8, b=2
得到 T(n) = 8T(n / 2) + n的2次方
为什么 8T(n / 2) 比 n的2次方要大？
（1）这里的大指的是什么？是指时间复杂度更小，也就是计算速度更快吗？感觉有些歧义。
（2）这里的T是什么？会参与计算吗？会代入什么值呢？

Answer 1

郝老狮 2024-09-21 10:38:49

看下上一张ppt，是设复杂度8T部分大于n的平方：

T（n）为定义在非负整数上的递归式；

你看下教材422页

下载视频

投屏

复制链接

• 提问者 逐梦稚者 #1

  我明白，8T部分如果大于n平方部分，复杂度由8T部分决定。
  
  我没搞懂的是，为什么8T部分大于n平分部分。
  8T(n/2)的结果是什么东西？T(8 * n / 2) = T(4n)吗？
  这里的T是什么东西？4n怎么可能比n平方大？
  
  它们两个的大小是怎么比较的？

• 郝老狮 回复 提问者 逐梦稚者 #2

  T（n）为定义在非负整数上的递归式，比较是基于假设性结论，原文你看是如果前面大于后面，有这样的结论