【算法优化】线性计算_斐波那契数列和传统递归对比

; 20层以内，递归写法简洁，20层以上，斐波那契数列效率高

t := A_TickCount
MsgBox % fn(25) "`n" A_TickCount - t "毫秒"

; 传统递归
fn(n) {
  if n < 2
    return n
  return fn(n - 1) + fn(n - 2)
}


t1:=A_TickCount
Loop 50
  记录 .= A_Index " = " 斐波那契数列(A_Index) "`n"

MsgBox % "耗时：" A_TickCount - t1 " 毫秒`n" 记录
return


; 函数
斐波那契数列(n) {
  if (n=1)
    s2 := 1
  else {
    s1 := 0
    s2 := 1
    Loop % n-1 {
      s2_tmp := s2
      s2 := s1 + s2
      s1 := s2_tmp
    }
  }
  return s2
}

Esc::ExitApp

/*
刚刚百度了一下，同样问题递归的时间复杂度跟循环一样吧？只不过函数调用使递归产生额外的开销，但这个性能损失好像不足以影响时间复杂度

斐波那契，迭代是O(n)，递归就成了O(2^n)
因为有非常多的重复求解

对象的深拷贝  相当于对每个对象都操作一次。 用什么方法 都需要对对象至少操作一次。
斐波那契数列的计算，如果用递归计算，比如算第50个值，则前面的很多数都会被计算很多次（重复计算 浪费时间）

斐波那契还可以用矩阵快速幂，复杂度更低，O(log n)
*/

 

声明：站内资源为整理优化好的代码上传分享与学习研究，如果是开源代码基本都会标明出处，方便大家扩展学习路径。请不要恶意搬运，破坏站长辛苦整理维护的劳动成果。本站为爱好者分享站点，所有内容不作为商业行为。如若本站上传内容侵犯了原著者的合法权益，请联系我们进行删除下架。