算法学习week1

第一周过去都快一个月了，做一点回顾记录。

“ I will, in fact, claim that the difference between a bad programmer and a 
good one is whether he considers his code or his data structures more 
important. Bad programmers worry about the code. Good programmers 
worry about data structures and their relationships. ” 
— Linus Torvalds (creator of Linux) 

1. 一些体会

• 《Algorithms》这本书的内容比Coursera上的对应课程是要难很多的，书中的每一章节习题非常之多，由浅到深，多是根据章节内容延伸而来。后面在整体学习完后，可以回头再找部分题，练一练。
• Coursera上课程中间视频讲解时，是存在动画过程的，确实有动画对理解其中的算法过程，很有帮助，不过视频动画讲解也有不好的地方，听得时候感觉很容易懂了，但过后却忘得较快，可能是没有练习的原因。
• Coursera每周的课程中都有Interview Questions，确实是很好的面试考题，课程中虽然不做硬性要求完成，也可以后续用来练习。
• 每周的projects更多的考察的是使用本章的算法去解决问题，提交代码后的用例测试对性能有很大考验，而且边界值情景较容易忽略而出错。
• 课程提供了很便捷的IDE环境，而且封装了许多实用的基础API，如画图，取随机数等，实际作业时是非常有帮助的，第一周的课程用辅助画图模式来调试，更能看清功能是否存在问题。

2. 重要点回顾记录

• 算法是解决问题的方法，而数据结构，则是这个过程中的用于解决数据存储的，往往实际问题对应数据量非常巨大时，就非常考验数据结构设计的合理性

  • Algorithm: method for solving a problem
  • Data structure: method to store information

• 网络中两个点的连通性问题，就是一个很有意思的算法问题
  书中的算法讲解步骤，逐步的优化：
  （1）用数组存放N个点，两个点若可以连通，则设置对应下标存放的标识相等，其中存在的严重缺陷是每次连通两个点时，需要更新所有其他与这两点相连的点；
  （2）连通两点时，将其中一点设置为另一点的根节点，根节点存放的标识就是与对应下标一致，这样每次连通时，只需要更新其中一点的根节点就行，每次连接的时候相当于形成一树枝，一个点挂靠在另一个点所在的树上
  （3）上面会存在根节点过深的情况，可以继续优化，连接两点的时候，考虑两点对应已连的点数，将点数多的点对应的树挂到较少点上；
  （4）步骤（3）一定程度上减少根节点深度，实际可以做到更多减少（根节点下相连的点形成的树更加扁平化），每次连接两个点的时候，将一颗树直接挂到另一颗树的根节点上（或者另一个点的祖节点）

• Steps to developing a usable algorithm.

  实际就是这样的先功能支持，再考虑优化调整
  ・Model the problem.
  ・Find an algorithm to solve it.
  ・Fast enough? Fits in memory?
  ・If not, figure out why.
  ・Find a way to address the problem.
  ・Iterate until satisfied.

• java 内存开销示例和说明

  image.png

Total memory usage for a data type value:
・Primitive type: 4 bytes for int, 8 bytes for double, 
・Object reference: 8 bytes.
・Array: 24 bytes + memory for each array entry.
・Object: 16 bytes + memory for each instance variable 
  + 8 bytes if inner class (for pointer to enclosing class).
・Padding: round up to multiple of 8 bytes.

• 注意算法复杂度对应英文名

image.png

3. 第一周的作业，经过反复调试快一天最终满分了

最开始只使用了一个顶部虚拟点，一直无法达到其中性能用例的要求，最终性能达到要求时，使用了两个虚拟的点，一个与顶部相连，一个与底部相连，当存在一个点，既与虚拟顶点和虚拟底点相连，则顶部与底部相通，可以渗透

image.png