时间复杂度、递归、尾调用— (读文笔记)

susheng 发布于2019-08-23 14:34 / 2774人阅读

摘要：递归算法是一种直接或者间接调用自身函数或者方法的算法。因此，分治策略一般用来解决子问题相互对立的问题，称为标准分治，而动态规划用来解决子问题重叠的问题。调用栈尾递归和手动优化尾调用就是一个函数执行的最后一步是将另外一个函数调用并返回。

输出

斐波那契数列的四种写法

读参考文章列表

算法复杂度中的O(logN)底数是多少

从斐波那契数列谈谈代码的性能优化

冰与火之歌：时间与空间复杂度

看动画轻松理解递归与动态规划

JavaScript调用栈、尾递归和手动优化

数据结构与算法公开课

问自己几个问题

算法复杂度中的O(logN)底数是多少， log2N 和 log10N 有区别么？

复习时间复杂度、空间复杂度、时间复杂度从小到大

时间复杂度级数

循环与级数的关系

分治、递归，递归的时间复杂度

从一个数组中找出最大的两个数

什么是动态规划，时间复杂度多少

尾调用和普通调用有啥不一样

问题解答

1，常底数是无所谓的，logaN/logbN = logab, 是一个常数

2，时间复杂度：
代码段执行次数累加

空间复杂度：
除了输入本身所占的空间之外，用于计算的所必须的空间量

时间复杂度从小到大
O(1)所以，O(n) 能否优化 O(logn)?优化关键

3，Ep12 时间复杂度级数
算数级数，与末项平房同阶，
1+2+3+...n = O(n^2)

幂方级数，比幂次高出一阶：
1+2^2+3^2+4^2 +... n^2 = O(n^3);
1+2^3+3^3+4^3 +... n^3= O(n^4);
1+2^4+3^4+4^4+... n^4 = O(n^5);

几何级数（a>1）:与末项同阶
a^0+a^1+a^2+... a^n = (a^(n+1) - 1)/(a-1) = O(a^n)
1+2+4+8 +... 2^n = 2^(n+1) -1 = O(2^n)

4，循环与级数的关系

    for(let i = 0; i < n; i++)
    for(let j = 0; i < n; j++)  坐标轴形成正方形，O(n^2)
     
    for(let i = 0; i < n; i++)
    for(let j = 0; i < j; j++)  坐标轴形成三角形，O(n^2)

5，冰与火之歌：时间与空间复杂度

分治：将原问题分解为若干个规模较小但类似于原问题的子问题（Divide），「递归」的求解这些子问题（Conquer），然后再合并这些子问题的解来建立原问题的解。

递归算法是一种直接或者间接调用自身函数或者方法的算法。通俗来说，递归算法的实质是把问题分解成规模缩小的同类问题的子问题，然后递归调用方法来表示问题的解。它有如下特点：

1. 一个问题的解可以分解为几个子问题的解 
2. 这个问题与分解之后的子问题，除了数据规模不同，求解思路完全一样 
3. 存在递归终止条件，即必须有一个明确的递归结束条件，称之为递归出口

递归算法的世界复杂度，得分好几种
第一种：
递归中进行一次递归调用的复杂度分析，如：二分查找法
不管怎么样，最多调用了一次递归调用而已，这时候时间复杂度看什么时候跳出递归

第二种：
递归中进行多次递归调用的复杂度分析
比如说斐波拉契数列，多次调用自身
所以时间复杂度等于递归树中节点数总和，就是代码计算的调用次数。

T(n) = 各层递归实例所需时间之和
= O(1) * (2^0 + 2 ^1 + ...2^n)
= O(1) * (2^(n+1) - 1)
= O(2^n)

空间复杂度：
一个程序执行时除了需要存储空间和存储本身所使用的指令、常数、变量和输入数据外，还需要一些对数据进行操作的工作单元和存储一些为现实计算所需信息的辅助空间。

6，从一个数组中找出最大的两个数
算法一
先遍历一遍，找出最大值的位置，x1，时间复杂度为 n-1
再遍历一遍，从剩下的n-2个数中，找最大值，时间复杂度为 n-2
总共 O(2n-3) = O(n)

算法二
x1是小值，x2是大数
如果值比x2大，替换x2
如果 x1时间复杂度O(n)

算法三
左边找最大L1，右边找最大 R1
L1else, 要么找左边第二大

7，看动画轻松理解递归与动态规划
动态规划能解决的问题分治策略肯定能解决，只是运行时间长了。因此，分治策略一般用来解决子问题相互对立的问题，称为标准分治，而动态规划用来解决子问题重叠的问题。

将「动态规划」的概念关键点抽离出来描述就是这样的：

1.动态规划法试图只解决每个子问题一次
2.一旦某个给定子问题的解已经算出，则将其记忆化存储，以便下次需要同一个子问题解之时直接查表。

8.JavaScript调用栈、尾递归和手动优化
尾调用：
就是一个函数执行的最后一步是将另外一个函数调用并返回。

一般来说，如果方法a调用方法b, 那么b放到栈顶，栈指针指向栈顶, 当前帧是b, 调用帧是a,

当函数B执行完成后，还需要将执行权返回A，那么函数A内部的变量，调用函数B的位置等信息都必须保存在调用帧A中。不然，当函数B执行完继续执行函数A时，就会乱套。
那么现在，我们将函数B放到了函数A的最后一步调用（即尾调用），那还有必要保留函数A的栈帧么？当然不用，因为之后并不会再用到其调用位置、内部变量。因此直接用函数B的栈帧取代A的栈帧即可。当然，如果内层函数使用了外层函数的变量，那么就仍然需要保留函数A的栈帧，典型例子即是闭包。

总得来说，如果所有函数的调用都是尾调用，那么调用栈的长度就会小很多，这样需要占用的内存也会大大减少。这就是尾调用优化的含义。

// 尾调用错误示范1.0
function f(x){
  let y = g(x);
  return y;
}

// 尾调用错误示范2.0
function f(x){
  return g(x) + 1;
}
// 尾调用错误示范3.0
function f(x) {
  g(x); // 这一步相当于g(x) return undefined
}

1.0最后一步为赋值操作，2.0最后一步为加法运算操作，3.0隐式的有一句return undefined

GPU云服务器云服务器尾调用时间复杂度递归调用快速排序时间复杂度

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/100804.html

尾调用优化——记一道面试题的思考

摘要：如果函数内部还调用函数，那就还有一个的调用帧，依次类推。等同于等同于如果所有函数都是尾调用，那么完全可以做到每次执行时，调用帧只有一项，这将大大节省内存。这就是尾调用优化。尾递归函数调用自身，称为递归。前言面某东，有一道题目是实现一个斐波拉契数列，已知第一项为0，第二项为1，第三项为1，后一项是前两项之和，即f(n) = f(n - 1) + f(n -2)。拿到这个题目，二...

awkj 2019-08-22 17:00 评论0 收藏0
js 实现斐波那契数列(数组缓存、动态规划、尾调用优化)

摘要：根据该规则，返回第个斐波那契数。尾递归函数调用自身，称为递归。一个前端眼中的斐波那契数列解斐波那契数列的实用解法调用栈尾递归和手动优化尾调用优化译我从用写斐波那契生成器中学到的令人惊讶的件事斐波那契数列是以下一系列数字： 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, ... 在种子数字 0 和 1 ...

赵连江 2019-08-23 11:38 评论0 收藏0
基于CPS变换的尾递归转换算法

摘要：一个解决的办法是从算法上解决，把递归算法改良成只依赖于少数状态的迭代算法，然而此事知易行难，线性递归还容易，树状递归就难以转化了，而且并不是所有递归算法都有非递归实现。前言众所周知，递归函数容易爆栈，究其原因，便是函数调用前需要先将参数、运行状态压栈，而递归则会导致函数的多次无返回调用，参数、状态积压在栈上，最终耗尽栈空间。一个解决的办法是从算法上解决，把递归算法改良成只依赖于少...

supernavy 2019-08-20 14:35 评论0 收藏0
尾调用和尾递归

摘要：执行完了，销毁调用栈中自己的记录，依次销毁和的调用帧，最后完成整个流程。尾递归定义先来看一下递归，当一个函数调用自身，就叫做递归。尾调用 1. 定义尾调用是函数式编程中一个很重要的概念，当一个函数执行时的最后一个步骤是返回另一个函数的调用，这就叫做尾调用。注意这里函数的调用方式是无所谓的，以下方式均可：函数调用: func(···) 方法调用: obj.meth...

goji 2019-08-22 16:09 评论0 收藏0
Vue源码解析：虚拟dom比较原理

摘要：算法子节点比较这部分代码比较多，先说说原理后面再贴代码。循环结束的标志就是旧子节点数组或新子节点数组遍历完，即。第二步尾尾比较。第三步头尾比较。第四步尾头比较。节点确认后，真实序列为，未确认序列为第五次是均不相似，直接插入到未确认序列头部。通过对 Vue2.0 源码阅读，想写一写自己的理解，能力有限故从尤大佬2016.4.11第一次提交开始读，准备陆续写：模版字符串转AST语法...

Towers 2019-08-23 15:19 评论0 收藏0