主定理求助
  • 板块学术版
  • 楼主墨笙_Mooos
  • 当前回复9
  • 已保存回复9
  • 发布时间2021/9/17 11:25
  • 上次更新2023/11/4 06:34:52
查看原帖
主定理求助
78216
墨笙_Mooos楼主2021/9/17 11:25

计算 T(n)=aT(nb)+cndT(n)=aT(\frac{n}{b})+cn^{d} 的复杂度时,若 abd<1\frac{a}{b^d}<1 (即 logba<dlog_ba<d)时,复杂度为公比的第一项 O(nd)O(n^{d})

如果这个公比虽然小于 11 但是很大也能直接写成是 O(nd)O(n^{d}) 的形式吗,如果公比 abd=0.99\frac{a}{b^d}=0.99 的话也可以算作是常数吗?

2021/9/17 11:25
加载中...