做算法题之前有一些概念是需要掌握

1、复杂度分析中的大(O)表示法

严格意义上的数学证明非常复杂，通常考核需要通过‘肉眼’去观察分析代码，得出结果，通常我们只关心，最高复杂度的运算，而且通常不考虑系数。

---

对于时间复杂度：个人理解，代码执行所需要的时间与输入数据量n的关系。

同样对于空间复杂度就表示：代码执行所需要的空间与输入数据量n的关系。

常见的几种情况有

• O(1) 常数时间复杂度

• O(log n) 对数时间复杂度

• O(n) 线性时间复杂度

• O(n^2)平方时间复杂度

• O(n^3)立方时间复杂度

• O(2^n)指数时间复杂度

• O(n!)阶乘时间复杂度

举一些例子去对比分析：

1. 常数时间复杂度，所谓O（1）不是指只执行一次，前面我们也说了可以忽略系数

 int i = 8;
 int j = 6;
 int sum = i + j;

1. 线性时间复杂度

for (int i = 0; i < n; i++) {
    System.out.println(i);
}

1. 平方时间复杂度

for (int i = 0; i < n; i++) {
    for (int j = 0; j < n; j++) {
        System.out.println(i+ j);
    }
}

4.对数时间复杂度 比如二分查找法，后续介绍二分查找法的时候再举例

5.指数时间复杂度

int fib(int n){
    if(n<2)return n;
    return fib(n-1) + fib(n-2);
}

了解时间复杂度和空间复杂度的分析，可以帮助我们了解代码执行的效率，做算法题肯定是要我们给出一个性能比较高效的解法。如果我们掌握了如何分析，才能知道如何去改进我们的代码。

2.常见的数据结构与算法

讲算法是离不开数据结构的。算法都必须在数据结构的基础上进行操作，所以学习算法，必须了解基本的数据结构，以及对于数据结构的一些基本操作。

• 数据结构划分:

  • 一维
    • 基础:数组array(string),链表 linked list
    • 高级:栈stack,队列queue,双端队列deque,集合set,映射map,etc
  • 二维
    • 基础:树tree,图graph
    • 高级:二叉搜索树binary search tree(red-black tree,AVL),堆heap,并查集disjoint set,字典树Trie,etc
  • 特殊
    • 位运算Bitwise,布隆过滤器BloomFliter
    • LRU Cache

• 算法:

  • if-else,switch -> branch
  • for, while Loog -> Iterator
  • 递归Recursion(Divide & Conquer,Backtrace)
  • 搜索Search:深度优先搜索Depth first search,广度优先搜索Breadth first search,A* etc
  • 动态规划Dynamic Programming
  • 二分查找 Binary Search
  • 贪心 Greedy
  • 数学 Math,几何 Geometry

这是一张完整的脑图，后续会跟着脑图逐一的探索各个数据结构与算法的知识 图片转载自阿甘的码路