算法

方法论

心态

via: https://www.bilibili.com/video/BV1ub1XBVE7Q

关注点 1: 是预期的效果吗？

1. 真实值 / 真值，via: https://en.wikipedia.org/wiki/Truth_value
2. 度量标准

关注点 2: 是最佳的方法吗？

1. 术语
   1. 多项式算法 (polynomial algorithm)
   2. 可行解 (certificate)
2. 刻画问题复杂度
   1. 非确定性多项式问题，NP
   2. 多项式问题，P
   3. NP 完全问题
   4. NP 难问题

Note

P = NP? 目前还没法证明

关注点 3: 更大的数据集会收敛到哪里？表现如何？

时间复杂度

NOTE

算法的用时随数据规模而增长的趋势

数据规模：输入数字个数、图点数与边数等等; 一般来说，数据规模越大，算法的用时就越长。

为什么要考虑数据规模？现代计算机的运算速度会把微乎其微的差别无限放大，考虑到输入内容 $\propto$ 运行用时, 分为

• 最坏时间复杂度
• 平均时间复杂度 / 期望 ¹

$floor(x)=[x](<=x的最大整数)ceil(x)=[x](>=x的最小整数)$

• 复杂度
  • 数学分析
  • Master Theorem

空间复杂度

NOTE

算法所空间使用随输入规模变化的趋势

渐进符号

渐进符号是函数的阶的规范描述, 简单来说，渐进符号忽略了一个函数中增长较慢的部分以及各项的系数 (在时间复杂度相关分析中，系数一般被称作 ” 常数 ”), 而保留了可以用来表明该函数增长趋势的重要部分

大 $O$ 符号：研究时间复杂度时通常会使用 $O$ 符号; 因为我们关注的通常是程序用时的上界; 而不关心其用时的下界; 这里的「上界」和「下界」是对于函数的变化趋势而言的; 而不是对算法而言的

使用广泛主要原因：

1. 我们有时只能证明时间复杂度的上界而无法证明其下界
   1. 这种情况一般出现在较为复杂的算法以及复杂度分析
2. $O$ 在电脑上输入更方便一些

量度 Big O notation：

1. $O(1)$ / Constant Complexity / 常数复杂度：表示与输入数据规模无关
2. $O(logn)$ / Logarithmic Complexity / 对数复杂度
   1. 一般底数默认 2
   2. 不是 2 也没关系, 用换底公式 ${\log }_{a}b=\frac{{\log }_{c}b}{{\log }_{c}a}$ 之后就是常数了
3. O（Vn）
4. $O(n)$ / Linear Complexity / 线性复杂度
5. $O(n^2)$ / N square Complexity / 平⽅复杂度
6. $O(n^3)$ / N square Complexity / ⽴⽅复杂度
7. $...$
8. $O(C^n)$ / Exponential Growth / 指数级, $C$ 是一个常数
9. $O(n!)$ / Factorial / 阶乘级

注意：只看最⾼复杂度的运算

数据结构

数据结构	优点	缺点
数组	插入快	查找慢，删除慢，大小固定，只能存储单一元素
有序数组	比无须数组查询快	插入慢，删除慢，大小固定，只能存储单一元素
栈	提供后进先出的存取方式	存取其他项很慢
队列	提供先进先出的存取方式插入快，删除快	存取其他项很慢
链表	如果树是平衡的，则查找、插入、删除都快	查找慢
二叉树	查找、删除、插入都快。树总是平衡的算法复杂	删除算法复杂
红黑树	查找、删除、插入都快。树总是平衡的。类似的树对磁盘存储有效	算法复杂算法复杂
2-3-4 树	如果关键字已知则存取极	删除慢，如果不知道关键字存取慢，对存储空间使用不充分
哈希表	快插入、删除快，对最大数据项存取快	对其他数据项存取慢
堆	对现实世界建模	有些算法慢且身

算法策论

1. 循环
2. 枚举
3. 模拟
4. 递归 & 分治
5. 贪心
6. 二分
7. 动态规划
8. 求解 TSP
9. PageRank 算法

路线图 Roadmap

Wikipedia

https://en.wikipedia.org/wiki/List_of_algorithms

• 1. Automated planning, 自动化规划
• 2. Combinatorial algorithms, 组合算法
  • General combinatorial algorithms, 通用组合算法
  • Graph algorithms, 图算法
    • Graph drawing, 图形绘制
    • Network theory, 网络理论
    • Routing for graphs, 图的路由
    • Graph search, 图形搜索
    • Subgraphs, 子图
  • Sequence algorithms, 序列算法
    • Approximate_sequence_matching, 近似序列匹配
    • Selection_algorithms, 选择算法
    • Sequence_search, 序列搜索
    • Sequence_merging, 序列合并
    • Sequence permutations, sort, 序列排列
    • Sequence_combinations, 序列组合
    • Sequence_alignment, 序列比对
    • Sequence_sorting, 序列排序
    • Subsequences, 子序列
    • Substrings, 子串
• 3. Computational mathematics, 计算数学
  • Abstract algebra, 抽象代数
  • Computer algebra, 计算机代数
  • Geometry, 几何
  • Number theoretic algorithms, 数论算法
  • Numerical algorithms, 数值算法
    • Linear algebra, 线性代数
  • Optimization algorithms, 优化算法
• 4. Computational science, 计算科学
  • 天文学
  • 生物信息学
  • 地球科学
  • 语言学
  • 医学
  • 物理学
  • 统计
• 5. Computer science, 计算机科学
  • Computer architecture, 计算机体系结构
  • Computer graphics, 计算机图形学
  • Cryptography, 密码学
  • Digital logic, 数字逻辑
  • Machine learning and statistical classification, 机器学习与统计分类
  • Programming language theory, 程序设计语言理论
  • Parsing, 解析
  • Quantum algorithms, 量子算法
• 6. Information theory and signal processing, 信息论与信号处理
  • Coding theory, 编码理论
  • Digital signal processing, 数字信号处理
• 7. Software engineering, 软件工程
• 8. Database algorithms, 数据库算法
• 9. Distributed systems algorithms, 分布式系统算法
• 10. Networking, 网络
• 11. Operating systems algorithms, 操作系统算法
  • Process synchronization, 进程同步
  • Scheduling, 调度
  • I/O_scheduling, I/O 调度

More

Tutorials

1. https://oi-wiki.org
2. https://ctf-wiki.org

References

• CTF Wiki
• 知乎 Live - 如何自学计算机专业课程？ · Shannon’s Blog
• 如何自学计算机专业课程？ - 知乎 Live
• OI 赛事与赛制 - OI Wiki
• ICPC/CCPC 赛事与赛制 - OI Wiki
• 黄明《从简单的线性数据结构开始：栈与队列》
• 王记超《Java中HashMap数据结构分析（语言无关）》
• 张宇腾《Dijkstra算法分享》
• 阎文元《聊聊散列表》
• 张鹏《深入浅出数组》

Footnotes

1. 复杂度 - OI Wiki ↩