Math&Algs
本文是我学习算法&数学的总结，包含笔记和一些资料，因为非专业出身，平时看的书也不成体系，所以本文更像是个大杂烩。持续更新…
数学
最近发现了《鸢尾花书》系列数学教程，这一套书籍包含《编程不难》、《可视之美》、《数学要素》、《矩阵力量》、《统计至简》、《数据有道》和《机器学习》。这套书同时包含理论和应用，也包含 Python 代码，对于我这种智商堪忧后知后觉的人来说，是很好的学习资料
网站&工具
- 通用：wolframalpha / 数字帝国 / mathwords / 数学百科全书 / 古今中外数学网 / 中学数学 /
- 矩阵：matrixcalculus / matrixcalc /
- 问答：https://math.stackexchange.com/ /
- 其他参考：math-tools /
算法
- Algorithms + Data Structures = Programs
- Sapir-Whorf hypothesis，Language shapes human thought
- 算法是一门技术，与 C++/Java 的学习方法类似，需要不断的重复
- 在一道题目上花费超过 30~45 分钟的时间依旧没有头绪，直接找解答资源
参考资料
- hello-algs & 在线阅读 / 《数学归纳法》 / Matlab-R-Python 命令对照表 /
- 《算法设计与分析》 & 公开课信息 & 公开课视频 / 《算法设计》 & 课后答案 /
- 《程序员面试金典（第6版）》 / LeetCode 面试金典题目 / 课后习题源码 / leetcode cookbook / leetcode 101 /
- 其他：《编程珠玑》 & code / 《算法 4th》 & code / 《DSAAIC++》 / 《STL 源码剖析》 / OI-Wiki / LEDA 商业版算法库 /
应用示例
你想把硬盘上的文件发送给你的朋友，但是他远在异国他乡。你想尽快把文件送到，该怎么办？
文件大小、网络是否可用、信道是否安全、是否有存储设备都是需要考虑的因素，所以一个问题的解决办法可以很简单，也可能因为场景的原因变得非常困难
一年与一天
这个故事来自于编程珠玑第六章，算法优化人员将原本需要一年才能运行完的程序优化到执行一天即可完成。模拟程序用于模拟三维空间 n 个物体相互影响的过程，传统迭代算法每次迭代需要计算所有物体之间的影响，每次迭代的时间复杂度是 \(O(n^2)\) 。作者对问题的优化使用了一些近似手段，比如相隔比较远的物体之间在计算相互影响的时候可以直接计算簇与簇之间的影响，这样可以减少簇中物体之间的计算。距离比较近的物体，就不再使用近似的手段。作者使用二叉树来表示物体之间的关系，二叉树的叶子节点是真实的物体，非叶子节点表示的是簇 。优化手段与效果。一共是 2*2*2*2*2*12=384 倍
- 使用二叉树近似物体之间的影响，提速 12 倍，好的数据结构非常重要
- 算法调优，使用小时间间隔处理相邻的物体，2 倍；迭代过程优化数据结构，2 倍
- 使用单精度浮点数，2 倍；使用汇编实现核心代码，2 倍；使用更好的机器，2 倍
从 \(O(n^3)\) 到 \(O(n)\)
问题：输入是具有 n 个浮点数的向量 x，输出是输入向量的任何连续子向量中的最大和
DSAAIC++ 第二章也有这道题并且给出了不同解法的 C++ 版代码，leetcode 对应习题为：maximum-subarray
- 普通的迭代算法，双指针，每次计算指针之间的和。时间复杂度 \(O(n^3)\)
- 对上述算法进行优化（BUD），减少最内层循环（使用累加数组可快速计算两指针之间的元素和），\(O(n^2)\)
- 分治法，每次处理一半数据同时考虑两边数据左右整合，时间复杂度 \(O(nlogn)\)
- 线性扫描法（动态规划），时间复杂度 \(O(n)\) 。这是理论上能达到的最佳值
通过数学手段减少指令个数，比如编程珠玑第九章提供的一些方法。减少内存占用意味着程序更小，更容易被载入到 cache 中，从而执行速度更快