【数据结构】稍复杂的级数题

题目

  该题求级数的复杂度,简单解析如下图。

  为什么0+0+1+2 * 2+3 * 4+4 * 8+…会是一个几何级数呢? 几何级数不是等倍数增长吗? 又是如何推导出O(logn*2^logn)呢?

问题详解

  可得S与等比数列求和的复杂度同阶,所以S可以当几何级数处理;而几何级数的复杂度与末项同阶且相等,所以S的复杂度为:
  O((logn-1) * 2^logn+1) = O(logn * 2^logn)。

————————— 本文结束 感谢您的阅读 —————————
谢谢你请我喝咖啡ლↂ‿‿ↂლ(支付宝扫一扫即可领红包, 消费时可抵现! 你省钱, 我赚钱, 多谢支持~)