search

algorithm002 / algorithm

44 stars 91 forks source link

【018-毕业总结】积跬步，至千里 #262

Open liveForExperience opened 5 years ago

liveForExperience commented 5 years ago

回顾

算法

复杂度分析

复杂度分析就是用来分析算法执行效率与数据规模之间增长关系的方法。

Big O notation：

从时间复杂度的分析情况可以区分为：

以上三种情况在大多数情况不需要区分，只要求出一个复杂度就足矣。只有在同一块代码在不同情况下，出现数量级的差别，才会具体进行区别分析。

常见到的空间复杂度：

使用递归算法解决问题的三个条件：

  1. 一个问题的解可以分解成几个子问题
  2. 这个问题与分解之后的子问题，除了数据规模不同，求解思路完全一样
  3. 存在递归终止条件

模板公式：

def recursion(...):
  # recursion terminator
  ...

  # process logic in current level
  ...

  # drill down
  ...

  # reverse the current level status if needed
  ...

避免递归过程中重复计算：

分治和递归之间的区别：

分治每一层的递归都涉及3种操作：

模板公式：

def divide_conquer(...):
    # recursion terminator
    ...

    # prepare data
    ...

    # conquer subproblems
    ...

    # process and generate the final result
    ...

分治算法能解决的问题，一般需要满足的条件：

二分的时间复杂度是O(logn)。

二分查找中最简单的情况，在有序数组中不存在重复元素，找到给定值。可以通过递归和非递归来实现：

二分查找应用场景的局限性

树的相似概念示意图

树的遍历

深度优先搜索 DFS

dfs

动态规划的大部分问题都能够通过回溯算法来解决，但是时间复杂度会是指数级的。而动态规划的效率会高很多，采用的是一种空间换时间的算法思想。

概念

案例：斐波那契数列

fib[n] = fib[n-1] + fib[n-2]
fib(0) = 0
fib(1) = 1

fib解法图

class Solution {
    public void fib(int n) {
        if (n <= 1) {
            return n;
        }

        return fib(n - 1) + fib(n - 2);
    }
}

案例：Count the Path

paths(start, end) = paths(A, end) + paths(B, end)
notValidSquare => return 0
anEnd => return 1

CountThePath算法图

class Solution {
    public int count(boolean[][] grid, int row, int col) {
        if (!validSquare(grid, row, col)) {
            return 0;
        }

        if (atEnd(grid, row, col)) {
            return 1;
        }

        return count(grid, row + 1, col) + count(grid, row, col + 1);
    }
}

数据结构

数组

数组是一种线性表数据结构。它用一组连续的内存空间，来存储一组具有相同类型的数据。(回顾一下，二分搜索使用排序后的数组)

概念

  • 线性表：数据排成像一条线一样的结构。每个线性表上的数据最多只有前和后两个方法。
  • 数组
  • 队列
  • 链表
  • 栈
  • 非线性表：数据之间并不是简单前后的关系。
  • 二叉树
  • 堆
  • 图
  • 连续的内存空间和相同的数据：
  • 因为这两种特性，数组才能够做到随机访问。时间复杂度O(1)。
  • 因为这两种特性，数组的插入删除，为了保持连续性，需要大量的数据搬移工作。时间复杂度O(n)。

    有趣的问题

    为什么数组的下标是从0而不是从1开始？

从数组存储的内存模型上看，"下标"最确切的定义是偏移offset。如果a表示数组的首地址，a[0]就是偏移位0的位置，也就是首地址，如果用1开始计数，每次随机访问就多了一次减法运算，对CPU来说就多了一条减法指令。

链表

链表通过指针将一组零散的内存块串联起来使用。

种类

  • 单链表：节点除了存储数据外，还会通过next指针存储下一个节点的地址。
  • 循环链表：一种特殊的单链表。单链表的尾节点指向空地址，循环链表尾节点指向头节点。
  • 双向链表：支持两个方向，不仅有next指针指向下一个节点，还有prev指针指向前一个节点。
  • 双向循环链表：循环链表和双向链表的结合。

    操作

  • 删除操作：只需要改变指针，时间复杂度O(1)。如果算上遍历查找的过程，时间复杂度是O(n)。
  • 新增操作：和删除操作同理。
  • 访问操作：数组可以做到随机访问的时间复杂度为O(1)，链表因为要指针遍历搜索，所以时间复杂度是O(n)。

    常见的链表操作(代码待补充)

  • 单链表反转
  • 链表中环检测
  • 两个有虚的链表合并
  • 删除链表倒数第n个节点
  • 求链表的中间节点

    注意点

    写链表的时候，很多地方会出现小问题，需要很仔细：

  • 指针的操作
  • 边界条件

    栈

    栈是一种操作受限的线性表(回顾下，线性表概念数组中有)，呈现后进者先出，先进者后出的特性。

    使用场景

    当某个数据集合只涉及在一端插入和删除数据，并且满足后进先出、先进后出的特性，可以首选栈这个数据结构。

    如何实现

  • 通过数组实现，称为顺序栈 
    
class ArrayStack {
private Object[] datas;
private int count;
private int n;

public ArrayStack(int n) { this.datas = new Object[n]; this.n = n; }

public boolean push(Object data) { if (count == n) { return false; }

datas[count++] = data;
return true;

}

public Object pop() { if (count == 0) { return null; }

return datas[--count];

} }

- 通过链表实现，称为链式栈

**存取的时间复杂度**：O(1)
### 队列
> 队列和栈一样，是一种操作受限的线性表数据结构，呈现先进新出，后今后出的特性。
#### 特性扩展
- 循环队列
- 阻塞队列
- 并发队列
- Disruptor
- Linux环形缓存
- ArrayBlockingQueue(实现公平锁)
#### 实现
- 顺序队列：使用数组来实现
```java
public class ArrayQueue {
  private Object[] datas;
  private int n;
  private int head;
  private int tail;

  public ArrayQueue(int capacity) {
    items = new Object[capacity];
    n = capacity;
  }

  public boolean enqueue(Object data) {
    if (tail == n) {
        return false;
    }

    items[tail++] = data;
    return true;
  }

  public Object dequeue() {
    if (head == tail) {
        return null;
    }

    Object ret = items[++head];
    return ret;
  }
}

所以我给自己制定了2个小目标：

为了能配得上自己想要获得的，坚持吧！努力吧！