0x03 算法

Review

  1. 2019/08/12
  2. 2021/03/19
  3. 2024-09-08 08:12

[!Summary] 算法与数据结构是相辅相成的，不要孤立开来学习。学习的重点不在于死记硬背，因为不常用的话很快也会忘记，所以要有一个大纲性的思路。

一、Introduction #

在计算机领域里，算法（Algorithm）是一系列程序指令，用于处理特定的运算与逻辑问题。

时间复杂度 一个算法运行时间长短的度量，用大O表示，T(n) = O(f(n)); O(1) < O(logn) < O(n) < O($nlogn$) < O($n^2$) < O($n^3$)

推导时间复杂度原则：

  • 如果运行时间是常数量级，则用1表示
  • 只保留时间函数中的最高阶项
  • 如果最高阶项存在，则省区最高阶项前面的系数

空间复杂度 算法在运行过程中，临时占用存储空间大小的度量，用大O表示，S(n) = O(f(n));

《算法图解》总结 #

  1. 首先得会复杂度分析：特别是时间复杂度，除了平均复杂度还需要知道最坏情况下算法会退化到何种地步。
  2. 算法要做到脑中要有动画、知道应用场景、对比其他算法优缺点、平均复杂度和最坏复杂度、使用需配合何种数据结构。常用基础算法都用这种方式过一遍：查找、排序、递归、搜索、聚类、哈希算法、贪心算法、分治算法、回溯算法、动态规划等
  3. 数据结构要做到脑中有图、适用何种算法、对比同类数据结构。经典数据结构要掌握：数组、链表、堆、栈、队列、散列表、二叉树、跳表、图、Tire树
  4. 适度刷题总结：leetcode

重点是对比性学习，给定场景要能选出合适的算法和数据结构 以本书为例说明算法和数据结构的配合：

  1. 广度优先搜索要配合队列；
  2. 递归、深度优先搜索要配合栈；
  3. 图算法多配合散列表；
  4. NP问题多用贪心和动态规划求近似解

以数组 vs 链表为例说明优缺点对比：

  • 数组：随机访问O(1)，插入删除O(n)，利于缓存、扩容时搬运麻烦、内存利用率高
  • 链表：插入删除O(1)，随机访问O(n)，不利于缓存、动态扩容、消耗额外空间、易产生内存碎片

以文中的散列表冲突说明退化问题： 采用链表结构解决冲突，当所有输入均映射至同一位置，O(1)退化至O(n)。另外散列表是一种空间换时间的方案，空间占用较大（不考虑实体内容，每条目消耗就有50字节左右），海量数据判断是否存在的场景用布隆过滤即可，缺点则是损失部分精度和时间。

算法竞赛 #

1: 竞赛 #

CCPC 中国大学生程序设计竞赛 https://ccpc.io/

ICPC 国际大学生程序设计竞赛 https://icpc.global/

NOI 全国青少年信息学奥林匹克 http://www.noi.cn/ 做题： oj.noi.cn

2: Online Judge #

Online judges, OJ, 在线判题网站 https://vjudge.net/

  1. 杭电OJ acm.hdu.edu.cn
  2. 北京大学OJ poj.org
  3. uva
  4. ural
  5. usaco: http://www.usaco.org/

3: 算法刷题网站 #

洛谷试炼场： https://www.luogu.com.cn/training/list

Reference #