《吴军-Google方法论》 DSA、教育、思维、逻辑、智慧

1. 计算机数据结构

1. 专业绘画的都会先素描框（使用基本的几何图形、结构和组成），画好框架骨骼，在细化绘画元素（画鱼思考）
2. 大的艺术家有时候未打稿，原因是相关草稿已了然于胸了
3. 计算机科学完成一个程序，有两种方式（一种是一行行代码去写，另一种是提前做好相关集合图像的规划，这些几何图形的规划在计算机科学中就是数据结构）
4. 程序=数据结构+算法，数据等同于点，数据结构等同于数据中的具体关系（比如队列、栈、二叉树等都有自己的特定）
5. 常用线性表数据结构：
   • 数组（插入需要移动大量元素，寻找容易，只需要提供数组下标）
   • 链表（插入方便，但寻找需要基于链表的首地址开始，元素很大时候效率很低）
6. 对比数组和链表，凡事有一列也有一弊

专业和业余人士做东西的一个重要区别，前者掌握了使用基本的几何图形、结构、组合来构建复杂的设计和系统的方法，后者只是根据自己脑子里面的构思和直觉，直接构建最终的产品和设计

2. 二叉树

1. 计算机科学中，相对的大小比绝对的数量更重要（真实世界是具体数值重要还是，数值间的相对大小（或次序）更重要？）
2. 有什么样的问题就有什么样的工具，测量的重要性（时间上面的钟、测量长度尺子、化学中的反应当量等）
3. 二叉树：首先是一颗树，且每个节点至多有两个子节点；
4. 检索二叉树：二叉树的子类，数上的任一节点，比该节点左子树都大，比右子树都小
5. 二叉树浓缩了很多概念：分叉、层层递进、有序

3. 锦标赛排序算法（N个选手中选K个选手）

1. 算法说明：
   1. 将所有数字放入二叉树的叶子节点，按比赛规则，两两比较选出最大的
   2. 对于第二大的，从所有被最大的数字淘汰的数字中选择
2. 算法复杂度：第一名的只需要N，第二名的增加LogN次计算，第三名也是增加LogN
3. 25人短跑比赛，有5个赛道，单轮淘汰赛，如何最快角逐金银铜前3名？
   1. 前5轮：25人分5组（A1~A5,…E1~E5），角逐每组第1
   2. 第6轮：每组第1再赛一轮（假定A1,B1,C1,D1,E1），角逐冠军(假定为A1)
   3. 第7轮：由于只要前3，故D、E两组已被淘汰（如果还继续比较则为无用功），因此亚军、季军候选只需要从A、B、C组挑选（A2、A3、B1、B2、C1），再一起赛一轮可知
4. 归纳起来：
   1. 少做无用功
   2. 善用信息

4. Google地图最短路径算法

1. 假如你再开发一款地图应用，如何找到离你最近的5个加油站
2. 很重要的第一步，解题之前，先读懂题目
   • 人和开车找位置的差别，对人来说200m都可能很远，但对开车来说，2.3公里和2.5公里没有太大差别，可能还有堵车的问题
   • 搞清楚每一个加油站和汽车的位置，以及行车方向，汽车是移动的通过GPS导航，是基于坐标、还是房屋门牌
   • 搞清楚行车方向
   • 距离不是欧几里得直线距离，两点之间的路可能有很多种，基于动态规划可以获取两点间的最短距离
   • 按距离排序，找到最近的5个加油站距离（排序是一类解决方式，但效率不是最高的）
3. 回到问题原点：
   • 没有必要针对很远的加油站排序，浪费资源
   • 基于二叉树的细类堆数据结构，可以满足N个数据排序前K个的数据算法复杂度：第1的只需要N，第2的增加LogN次计算，第3的也是增加LogN）次计算（这里就差了一个工程数量级，淘宝求全年销售top10差距就更大）
4. 继续回到问题原点：
   • 考虑到地图被很多人使用，在求解路径过程时候，A到E点、B到E点、C到E点，其中可能很多复用的线路，我们可以提前计算好存储起来，在求解某条最短路径时候，只需要通过服务调取出来即可，会降低很大的重复计算量
5. 大数据思维，很重要一条就是是将所有事件统一起来，全局性的优化
6. 归纳起来：
   1. 少做无用功
   2. 很多事情遵循统一个规律（最短路径、N中TopK、堆），学习理论需要思考理论提出的时候，要解决的应用问题是什么，搞清楚这块才有可能一通百通
   3. 解决问题时候，我们不知不觉做了很多前提假设，适当回到原点，重新读懂问题（产品思维也是强调从不同用户角度看问题，跳出局限性）
   4. 好的面试官会引导，不怕刷题的

5. 好算法对效率影响

1. 计算机科学做事原则：构建理想环境，确定比较标准（事先讲好游戏规则，再做研究，确定基线）
2. 计算机思维本质是翻译，解决问题共性地方形成了算法，构成了计算机科学的基础
3. 吴军大学实习，财务系统数据量级问题
4. 计算机是要处理大数的，工程师需要对计算资源数量有概念
5. 评判算法好坏，高德纳思想：
   • 考虑接近极限的情况（计算机用于处理大数）
   • 算法快慢两类决定性因素：不随数量变化的因素，随数量变化的因素（10N^2之前的系数，可以忽略）
   • 计算机科学中，两类算法量级一样，则认为他们速度一致
6. 回顾科学发展史，将问题抽象，过滤次要因素，构建理想环境（但并非不考虑现实）

6. 高效率的本质

1. 对比冒泡，插入排序，都是同量级O(n^2)
2. 提高算法效率本质是让计算机少做事，做有效率的事情，减少对比次数，归并排序（先自顶向下细分，再自底向上合并），O(NlogN)
3. 效率=产出/所做的事情，人的产出很难提高，但做的事情可以减少
4. 自己苦思冥想一个月或者一年，可能一周或者一个月，学习并练习，就可能足够了
5. 今天常用的快速排序，是计算机诞生13年后产生的，是自己冥想，还是学习？

7. 谈快速排序：少做事情

1. 最好的算法，是考虑一般情况，还是最差的极限情况
2. 吴军从东三环去机场选路问题
3. 世上没有绝对的最好
4. 目前通常情况下，最好算法是快速排序，其思想还是少做事：
   • 从一堆无序数字中，随机挑选一个数字（称为枢值），以枢值为界限，将数字分成大于和小于的两部分（总共两堆）
   • 在大于和小于的数字堆中，再随机挑选一个枢值，继续以该枢值为界限，将数字分成大于和小于的两部分（总共四堆）
   • 依次上面的戏法，直至最后都排序好
   • 算法复杂度：O(NlogN)，科学上和归并排序一样好，但工程上面一般情况比归并排序块两倍
5. 归并排序：2万学生分10个学习，每个学校2000人按成绩挑学习好的学生
6. 快速排序：2万学生，划几分数线，学生成绩和分数比较，挑学习好的学生
7. 计算机和组织的管理，乃至社会的管理，想要提高效率就是少做事情（学生成绩从0~100教，老师也很难办）
8. 每个底层员工要做的事情，就是快速进入更高层

8. 计算机科学和工程的差别

1. 计算机科学是方向，工程则是沿着方向建设道路
2. 关注是事情不同，环境也有差异；科学不过分考虑资源的边界效应，抽象出理想环境，算法上面几倍的提升，没有太多意义，而工程哪怕20%的效率也是值得的
3. 中国大学制造超级计算机，只能说明工程比较厉害
4. 和钱的距离
5. 思维转变，现实到理想，吴军经历科学、工程、再到科学的道路
6. 机器学习模型，20兆到3兆的意义
7. Google工程上面2%的计算资源优化，足矣让一个工程师花一个季度时间投入优化
8. 优化的价值和意义，在工程和科学上面是不一样的
9. 计算机科学关注在量级上面，而不太在意细小成本；在计算机工程上面，必须先使用科学上面最优方法，再做细节改进

9. 做减法

1. 首先要对一个学科，一个整体的知识体系有完整而深刻的理解，抓住主干
2. 抽象不容易，如果一些概念抽象不了，不要勉强
3. 认识是不断进步的，早先理解的本质，以后看来可能会很浅显，随着见识不断攀升，对一个问题的理解会越来越透彻
4. 事物的本质应该是简单的
5. 抽象是筛选的过程，抓大放小，突出主要，过滤次要，寻求本质的过程：
   • 明确抽象的目的
   • 明确抽象的结构
   • 检验抽象的效果：见识、视野、实战，洞悉本质
6. 按一定原则分类，有助于提高效率，但过分强调公平，效率就提升不上去
7. 做减法不等于不做事，职场中稍微有经验的领导，都不会指望新人可以挑重担，和臭棋篓子下棋，会越下越臭
8. 做事情，做得多，5个50分，不如一个100分
9. 送礼品，宁可送一个让她记住一辈子的东西
10. 《算法导论》
11. 软实力：看透钱；学会服从、合作、当助手和领导；认清边界；成为健全的人；树立信仰；

10. 计算机思维

1. 计算机思维：智能时代，学会计算机思维方式
2. 工程师的直觉：一个房间可以装多少高尔夫球，没有数据之前不要轻易给答案
3. 工程师的极限：尝试永动机、水发电，遵循科学理论和极限，不为不可能的事情浪费时间
4. 在边界内做事：在极限内寻找答案，不浪费时间做超越极限事情（不要动不动就超越极限）
5. 量级思维：芝麻、西瓜、大象、地球、太阳、银河，成就=成功率x事情的量级x做事的速度
6. 把事情做好的三条边：基线、极限、阶梯，认清当下，明确目标方向，找到持续前进的道路
7. 粗调和精调：显微镜的目镜和物镜螺旋按钮、100层楼丢球，不用粗调只用精调，不仅做事效率会低，而且可能由于方向不对，导致最后放弃

11. 发明的逻辑

1. 早期飞行的发明：
   1. 有条件可以将目标定得高远一些
   2. 模仿不可耻，可耻是走不出模仿
   3. 违背常理的，很多源于我们感性的认知和做法
   4. 勇于承认错误，不至于在错误道路上滑得太远
   5. 成功需要等到风云汇聚，天时地利人和
2. 莱特兄弟对飞机贡献：实验和测试的重要性，不要莽撞的推出产品；成功最重要的是走出模仿；
3. 计算机发明过程：
   1. 人们总是根据不断的增加需求，增加系统的复杂性，等待系统非常复杂，就需要有人能够从更高的层次维度思考，搞清楚系统的本质，然后用简单办法解决
   2. 世界的奥秘在于搞清楚他们的基本单元和他们之间的关系
   3. 东西越做越复杂，就是化繁为简的时候了
   4. 大的目标需要拆解成简单的一个个解决，一个复杂问题拆解成两个简单问题，成功解决可能性就大了很多（这个不等同于做了两个收益很小的事情，就等于做了一件大事情）

12. 教育和学习

1. 学好语文、数学、历史，科学：培养好沟通、个人素养，思维逻辑，看清楚自己位置，以及科学看待问题和讲道理的人
2. 上好大学目的：提升自己格局，让自己可以在社会养活自己，从社会消费者到贡献者的必要训练
3. 大学五训练：看透钱、学会服从和合作、认清边界、成为健全的人、树立信仰

13. 人生和商业智慧

1. 上帝喜欢笨人：事情一件件的做，不要并行处理；善始善终，做很多半途而废的事情，不如完成一两件小事；
2. 一生要做的五件事：恋爱结婚生子、做自己喜欢的事情做到极致、回馈、有一个信仰、给社会留下遗产
3. 超越免费：稀缺性、时效性、个性化、可用性、可靠性、粘性（数据、用户）
4. APRU(Average Revenue Per User): 平均用户收入，抛弃不值钱的关注，有这些时间不如找一些真正可以帮组我们的朋友，为他们提供一些价值
5. 中美生活习惯差异：家庭观念（中国人家族、美国家庭）、做事方式（计划性和随意性）、任何人直接的距离（对隐私的看重）、父母和孩子的关系（成人即独立）、公私分明（下班私人时间看重）、主动性（很早就找到老板说明自己的职业发展计划，希望老板支持和配合）

14. 走出死循环

1. 不要让孩子继承自己的焦虑(有欲望追求，满足不了或者凡事自己想把控)；麦糠中的两粒谷子，不听也罢(GIGO，机器学习中的噪音数据)；隔断或差异化地生活；
2. 不要把上名校当成中进士，目光所及，即人生的境界；所谓的终生学习，是不断超越自己，超越别人；
3. 多了解孩子，树立榜样（家长的懒惰，孩子会模仿）；以后不在孩子面前玩手机，多一些高质量的陪伴（多陪陪孩子，了解具体情况，看看出了什么问题，多和孩子一起看看书，比上培训班要好很多了）
4. 学习不是中彩票（相信自己的运气，不想通过努力），将教育当成人生的必须品，不用囫囵吞枣的学完，而是根据自己的兴趣一点一点的学下去，长期效应
5. 学会生活，学会花钱（不要将钱投在阻碍在自己上升的地方），走不出贫困的人(时间和钱投入在哪了？)
6. 不要迷恋公务员（高风险也不一定意味着高回报，但低风险一定没有高回报）