数据结构和算法基础学习记录

一、什么是好算法

二、评判算法优劣

即：TM图灵机、RAM等模型，为度量算法的性能提供了准确的尺度。

三、大O记法

四、迭代与递归

特别要注意，算法的初衷就是解决问题的“规模”，所以要学会抽象出问题的规模，从问题的规模角度去解决问题。

注：这道算法题虽然简单，但是体现了算法解决问题的一些思路。如其中的n可看作是问题的规模，每当一次循环结束后（n-1），则问题的规模减少1。这种将问题规模逐渐减少的过程则是很重要的算法思想。

注：其中的sum(A,n-1)是“问题规模减少驱动”，A[n-1]是“平凡问题的迭代”。

递归式算法的效率（复杂度）分析方法。

注：递归跟踪，直观形象，仅适用于简明的递归模式。而接下来的递推方程，间接抽象，更适用于复杂的递归模式。

另一实例

注：将问题规模设立好区间，即问题规模为hi-lo，则将问题的规模二分化来解决。所以，解决思路还是通过问题规模的角度去进行解决。

注：其中的logn是以2为底的对数，即log2(n)，文案中未纠正。

注：其中的logn是以2为底的对数，即log2(n)，文案中未纠正。

递归和分治的综合例子

小结：算法，迭代和递归。策略，减而治之和分而治之。分析，递归跟踪和递推。

五、动态规划

利用斐波那切数列进行展开

当菲波那切数列数列的规模达到40左右以后，处理速度会明显变慢。

通过递归跟踪分析得出

同样问题的规模，优化之后的效率杠杠的

且注意，改进后的空间复杂度也将为O（1），未改进前的空间复杂度为O（n）。

另一例子，求公共最长子序列问题LCS

六、向量接口与实现相关（其它的基本数据结构可以此知识点来作为思考维度进行拓展）

以下的策略不是最好的，但是可以作为基础来进行拓展

采用模板式的结构，可以使得数据结构的定义更加规范，此后也可以构建更为复杂的数据结构。

如，Vector是向量序列，如果模板元素是二叉树类型，则整个数据结构就相当于一个“森林”，非常的形象的映射出了现实的对象。

注：之所以V[r]能作为左值能被赋值，是因为其接口已经定义了其类型为引用类型。引用类型就和平时的“变量”一样，所以可以对其进行赋值的。

注：输入敏感，就是复杂度对于输入什么来说非常关键，输入的数据不同，可能对于复杂度的影响会有很大的不同。

二分查找

其中的rand()取值为0到MAX值，对2取模后，取值为0或1，因为取2的余数只能为0或1。

二分真的是最优的分法吗？

插值查找

七、栈

八、队列

以上的数据结构为“线性数据结构”

九、树（半线性结构，毕竟其组成形式也掺杂了线性结构的一些性质）

十、词典（散列）

十一、优先级队列（各种数据结构的综合应用）