时间复杂度和空间复杂度分析

时间复杂度

看函数执行的次数

面试四件套

首先，和面试官把题目的意思全部都确认无误；
第二，想所有可能的解决办法，同时比较这些方法的时间和空间复杂度；
接下来再找出最优的解决方案，最优的解决方案就是时间最快的，内存的话用的最少的话更好；
然后开始写程序，最后测试结果；

递归中求时间复杂度

关键就是要了解它的递归，总共执行了多少次语句；
具体做法就是把递归的执行顺序画出一个树形结构，称之为它的递归状态的递归树(或者叫做状态树)

斐波那契数列

面试中一定不要这么写，现在实现斐波那切数列的时间复杂度为O(2^n)，因为前面的数据要计算很多次，优化的话可以增加一个缓存，记录一下前面已经实现的计算或者使用循环来实现

二叉树遍历，图的遍历，DFS和BFS时间复杂度都为O(n)

可以通过主定理得到；
不管是前序遍历、中序遍历还是后序遍历，二叉树每个节点会访问且仅访问一次；

二分查找的时间复杂度为O(logn)

空间复杂度

数组的长度
递归的深度(特殊说明 )
参考链接

数组

数组访问非常便利，访问每一个元素都是非常快速的，时间复杂度为O(1)，但是数组的插入和删除操作非常麻烦，因为要移动插入或者删除的元素后面的元素的位置，最复杂的情况是需要移动整个数组，最好的情况是不需要移动元素，平均的时间复杂度为O(n/2)，所以时间复杂度是O(n);

链表

链表可以非常方便的实现插入和删除操作，时间复杂度是O(1)，但是查找的话会比较困难，最坏的情况是需要遍历整个链表，平均的时间复杂度为O(n/2),最坏的时间复杂度为O(n),

跳表

实战题目解析：移动零

任务：

请从下面两道编程题中任选一道，完成后将代码截图到微信群内，并艾特你的班主任哦：

❤️温馨提示：完成所有作业 + 完成视频观看，即可获得《覃超的算法修炼心法》视频课合集

五毒神掌：
练题步骤：
1.5-10 分钟：读题和思考
2.有思路：自己开始做和写代码，不然，马上看题解
3.默写背诵，熟练
4.然后开始自己写（闭卷）
写出自己想到的所有解法，不需要考虑时间复杂度和空间复杂度

Leetcode 上执行代码
可以修改测试用例

提交代码
查看执行结果，查看执行用时，内存消耗不太重要

查看别人的解法：
对于不好的解法可以直接略过
对于写的好的解法，可以自己按照这个解法，改进的自己的解法，也可以直接拿过来，但是需要自己整理下

最大的误区，刷题只刷一遍
核心的思维：升维，空间换时间
刷题五遍

在中国网上看完之后，去国际站看看

参考链接

Java 源码分析（ArrayList）
Linked List 的标准实现代码
Linked List 示例代码
Java 源码分析（LinkedList）
LRU Cache - Linked list： LRU 缓存机制
Redis - Skip List：跳跃表、为啥 Redis 使用跳表（Skip List）而不是使用 Red-Black？

树、二叉树、二叉搜索树

树

二叉树

二叉搜索树

参考链接

二叉搜索树 Demo

思考题
树的面试题解法一般都是递归，为什么？
说明：同学们可以将自己的思考写在课程下方的留言区一起讨论。

实战题目解析：二叉树的中序遍历

任务：
请你从以下题目中任选一道，完成后将代码贴到微信群里，并艾特你的班主任：
N 叉树的前序遍历
二叉树的前序遍历

❤️温馨提示：完成所有作业 + 完成视频观看，即可获得《覃超的算法修炼心法》视频课合集

参考链接

树的遍历 Demo
递归

递归代码模板
Python 代码模板

# Python
def recursion(level, param1, param2, ...): 
    # recursion terminator 
    if level > MAX_LEVEL: 
       process_result 
       return 
    # process logic in current level 
    process(level, data...) 
    # drill down 
    self.recursion(level + 1, p1, ...) 
    # reverse the current level status if needed

Java 代码模板

// Java
public void recur(int level, int param) { 
  // terminator 
  if (level > MAX_LEVEL) { 
    // process result 
    return; 
  }
  // process current logic 
  process(level, param); 
  // drill down 
  recur( level: level + 1, newParam); 
  // restore current status 
}

C++

// C/C++
void recursion(int level, int param) { 
  // recursion terminator
  if (level > MAX_LEVEL) { 
    // process result 
    return ; 
  }
  // process current logic 
  process(level, param);
  // drill down 
  recursion(level + 1, param);
  // reverse the current level status if needed
}

JavaScript

// JavaScript
const recursion = (level, params) =>{
  // recursion terminator
if(level > MAX_LEVEL){
     process_result
return
   }
// process current level
   process(level, params)
//drill down
   recursion(level+1, params)
//clean current level status if needed
}

参考链接

递归代码模板

总结

知道分子一无是处，专业和熟练才是关键；
要刻意练习，要持续刻意练习；
一定要锻炼自己分析解决问题的能力

算法

算法学习

时间复杂度和空间复杂度分析