递归求和与其时间复杂度

发表于

递归算法实现1-100求和

C语言形式

1
2
3
4
5
Sum(int num) {

return num <= 0 ? 0 : num + Sum(num - 1);

}

时间复杂度

因为运行了100次，所以时间复杂度O(n)=O(100)

递归形式的缺点

  1. 效率会有问题，时间复杂度高，如菲波那切数列计算重复会造成资源浪费。
  2. 调用层级过多，会引起调用栈溢出。

尝试优化时间复杂度至O(1)

采用高斯的算法
(1 + num) *num/2