数据结构与算法之美

极客时间专栏|数据结构与算法之美

学习计划:

专栏 + 视频课 + 书 + 代码实践 + LeetCode

复杂度

• 时间复杂度
• 空间复杂度

20个最常用的，最基础的数据结构与算法：

数组，链表，栈，队列，散列表，二叉树，堆，跳表，图，Tire树；
递归，排序，二分查找，搜索，哈希算法，贪心算法，分治算法，回溯算法，动态规划，字符串匹配算法；

不用具体的测试数据来测试，就可以粗略地估计算法的执行效率的方法。

大 O 复杂度表示法
并不是具体表示代码的真正执行时间，而是表示代码执行时间随数据规模增长的变化趋势，也叫做渐进复杂度 asymptomatic time complexity ，简称时间复杂度。

1. 只关注循环执行次数最多的一段代码
2. 加法法则：总复杂度等于量级最大的那段代码的复杂度
3. 乘法法则：嵌套代码的复杂度等于嵌套内外代码复杂度的乘积

对数阶复杂度 O(logn)

 i=1;
 while (i <= n)  {
   i = i * 3;
 }

空间复杂度分析：
表示算法的存储空间与数据规模之间的增长关系。

最好情况时间复杂度 best case time complexity
最坏情况时间复杂度 worst case time complexity
平均情况时间复杂度 average case time complexity
均摊时间复杂度 amortized time complexity
_

数组

随机访问；

线性表 linear list
连续的内存空间和相同类型的数据

很多时候我们并不是要去死记硬背某个数据结构或算法，而是要学习它背后的思想和处理技巧

• JVM 标记清除 垃圾回收算法
• Java ArrayList

链表

单链表，后继指针

回文字符串问题，快慢指针。

指针和引用，内存地址。

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

栈

先进后出，后进先出；
只允许在一端插入和删除数据；

散列表

散列冲突;

散列函数，

开放寻址法，序列化

链表法；

工业级散列表举例分析，Java HashMap