数据结构 与 算法ENCS 111 - 2.0 版
程序就是数据，和基于数据的计算
结构
如何用内存数据表达现实问题
案例
1.
一个班级的所有的人的名字，可以用一个字符串的数组存储
2.
数组的尺寸是固定的，如何制造一个尺寸可以动态变化的数组？
3.
公司员工之间的上下级关系，用什么结构存储？
4.
北京地铁，存储站台和列车的信息？
目标
1.
能够读懂常用的数据结构，和设计的目的
2.
能够根据需求调整数据结构，或者设计新的数据结构。
思路
算法
解决一个具体问题的办法
案例
给定一个数组 A 里面都是正整数, 而且没有重复
求取两个数之和的最大值
可能的解法
1.
双层 for 循环
遍历所有两两数的组合
算出所有组合的两个数的合
保留最高值
2.
找出数组里最高的两个数
算出这两个数的合
思路
1.
双层 for 循环
穷举法 (Brute Force)
2.
找出数组里最高的两个数
贪心法 (Greedy)
思路 vs 算法
算法：解决一个具体问题的办法
思路：怎么想出一个解决具体问题的办法
目标
1.
理解并会写出来常用的算法
2.
能够理解算法思路，针对没见过的问题，可以当场想出算法。
效率
不同的解法，哪个更好。量化 与 对比
案例 1
1.
程序 1
for (...) {
for (...) {
...
}
}2.
程序 2
for (...) {
...
}
for (...) {
...
}案例 1
1.
程序 1
执行了 30秒
2.
程序 2
执行了 2秒
目标
1.
能够评估不同算法的时间和空间复杂度
2.
能够根据情况，想出时间复杂度更优的算法
