算法和数据结构和算法时间复杂度

为什么学？

• 编程的内功修炼
• 去国内一流互联网公司的必要条件
• 硅谷互联网公司要求当场写算法
• 算法和数据结构是有趣且实用的

如何学？

如何精通一个领域？

• 切碎知识点
• 刻意练习
• 反馈

数据结构

image.png

数据结构和算法列表

image.png

数据结构

• Array （数组）
• Stack （堆）/ Queue （队列）
• PriorityQueue（优先队列）
• LinkedList 链表
• Tree （树 二叉树）
• Binary Search Tree （二叉搜索树）
• HashTable （哈希表）
• Disjoint Set（并查集）
• Trie（字母树）
• BloomFilter（布鲁姆过滤器）
• LRU Cache（高级数据结构）

算法

• General Coinding（一般算法，经典编程题目）
• In-order/Pre-order/Post-order traversal （基于树的前序、中序、后序）算法
• Greedy （贪心算法）
• Recursion/Backtrace （回溯递归算法）
• Breadth-first search（深度优先算法）
• Depth-first search（广度优先算法）
• Divide and Conquer （分值算法）
• Dynamic Programming（动态规划）
• Binary Search（二分查找）
• Graph（图）

时间复杂度和空间复杂度

image.png

• 常数级运算的复杂度

  
  image.png

image.png

可以看出，for循环的复杂度取决于n的值的大小，如果只有一层循环，n=10的情况下就是O(10)的复杂度，那么双层循环则是O(10x10)的复杂度。

image.png image.png

• 经典例子：

  
  image.png

前者通过for循环来计算的复杂度为O(n)
后者则为O(1)

所以看不同算法的话，对于优化有很大的提升。

• 经典例子（递归算法）

  
  image.png

后者等于前两个数的和，那么复杂度怎么计算？

只有三行的代码计算，fib(6) 实际运行的时候却是下面的样子：

image.png

那么它的复杂度是O(2的n次方)
也就是指数级的复杂度

常用算法复杂度计算：

image.png

• 二分查找 O(log n)
• 二叉树的遍历，因为遍历二叉树每个节点仅遍历一次 O(n)
• 排序 一维 O(n) 二维 O(log n)
• 快排、归并排序 O(n*log n)