算法学习心得

左神算法课学习笔记：

1. 时间复杂度：

   1. 最好情况和最坏情况：什么时候考虑最好/最坏情况？当算法的复杂度和数据状况有关的时候就得考虑。
   2. 评价一个算法的好坏，一律按照最坏情况去评价（所以时间复杂度的定位：一个算法流程中，在最坏情况下常熟操作数量的指标）

2. 额外空间：

   1. 有限变量空间，为O(1)

3. 关于递归如何估计其样本量：

   1. 通式：T(N) = a*T(N/b) + O(n^d)：

      1. 注释：N/b为子过程的样本量a为每一次子过程发生的次数，T(N/b)为调用子过程的时间复杂度，O(n^d)是除去调用子过程剩下的时间复杂度

      2. 满足这个通式的都可以有一个公式（Master公式）求出时间复杂度：

         log(b,a) > d => 复杂度为O(N^log(b,a))
         log(b,a) = d => 复杂度为O((N^d) * logN)
         log(b,a) < d => 复杂度为O(N^d)
         
         注：
         1.使用master公式的前提：子过程时间复杂度都一样
         2.出去调用子过程剩下的时间复杂度有可能不是O(n^d)的形式，可能是O(N*logN)等形式，也可以使用了该公式
         3.归并排序的时间复杂度就是通过Master公式计算得出
         

实现剑指Offer的题目

链表 1、反转单向链表 2、反转双向链表 3、K 个一组翻转链表 4、合并两个排序的链表 5、链表中倒数第 K 个节点 6、O(1) 时间内删除一个节点 7、删除链表中重复的节点 8、从尾到头打印链表 9、判断一个链表是否为回文结构 10、给出两个有序链表的头结点，打印出两个链表中相同的元素 11、将单向链表按某值划分成左边小、中间相等、右边大的形式 12复制含有随机指针节点的链表 13两个单链表相交的一系列问题 14链表中环的入口节点 15复杂链表的复制