树 & 图

Tree 可以理解为多个next指针的 Linked List 的变形。

2019/7/12 posted in  算法基础

排序

时间复杂度最低: O(nlogN)

快速排序 时间复杂度 O(nlogN)

2019/7/12 posted in  算法基础

Map & Set

哈希表

  • 哈希函数

  • 哈希碰撞
    通过哈希函数计算出来对应到了同一个内存位置

  • 哈希碰撞解决方案:
    拉链法解决,通过链表一个一个叠加上去。

List 的内部实现一般可以使链表也可以是数组。
查找的时间复杂度为O(n)

Map 映射,是key value之间的关系
查找的时间复杂度O(1)

Set 不允许元素重复
查找的时间复杂度O(1) 或者 O(logn)

HashMap HashSet

使用哈希表实现,查找的时间复杂度为O(1)

TreeMap TreeSet

使用二叉搜索树实现,查找的时间复杂度 O(logn)
优势在于内部元素是以相对有序的方式排列的

Python 的Dictionary是默认使用了 HashMap

Java , C++ , C 需要指定使用 HashMap 还是 TreeMap

2019/7/12 posted in  算法基础

Swift实现队列

struct Queue<T> {
    private var elements: [T]
    var count: Int { return elements.count }
    var isEmpty: Bool { return elements.isEmpty }
    var peek: T? { return elements.first }
    
    init() {
        elements = [T]()
    }
    
    mutating func enqueue(_ element: T) {
        elements.append(element)
    }
    
    mutating func dequeue() -> T? {
        return isEmpty ? nil : elements.removeFirst()
    }
    
}
Read more   2019/7/12 posted in  算法基础

Swift实现栈

class Stack<T> {
    var stack: [T]
    var isEmpty: Bool { return stack.isEmpty }
    var peek: T? { return stack.last }
    
    init() {
        stack = [T]()
    }
    
    func push(_ object: T) {
        stack.append(object)
    }
    
    func pop() -> T? {
        if !isEmpty {
            return stack.removeLast()
        } else {
            return nil
        }
    }
}
Read more   2019/7/11 posted in  算法基础

First In Last Out

队列

First In First Out

优先队列

PriorityQueue 优先队列
正常入,按照优先级出

实现机制

  1. Heap(Binary, Binomaial, Fibonacci)
  2. Binary Search Tree

堆的实现方式有很多种:

其中 斐波那契堆 、 严格斐波那契堆的效率是最好的。

Python和Java中的堆是使用斐波那契堆实现的,还有二叉树(平衡二叉树、红黑二叉树)。

2019/7/4 posted in  算法基础

链表

链表使用的场景:

  1. 不知道有多少个元素
  2. 插入删除的操作比较多

时间复杂度:

插入和删除的操作都是 O(1) , 查找是 O(n)

单列表

有一个next的指针指向下一个节点

双链表

有前后两个指针指向前后的节点

2019/7/4 posted in  算法基础

Master Theorem

常见递归算法的时间复杂度:

4271562172471_.pi

排序二维矩阵查找 O(n) , 一维矩阵查找 O(nlogn)

2019/7/4 posted in  算法基础