算法本质33_算法战的本质

//因为时间少，所以用简单的语言。

算法有三个特征，（1）算法复杂度。实际是程序有几个循环，主循环中有几个内层循环。算法复杂度与具体数据结构，循环用到的元素数量，所有操作的个数有关。传统上，算法的操作可认为是函数的个数。（2）循环的工作原理。 循环的作用是什么。例如，动态规划矩阵链乘法<A1,A2,...,An>的第一层循环有两个，主循环有三层。主循环的第一层循环有l=2,3,...,n个子矩阵链长度，子问题的长度。第二层循环i=1,....,n-l+1是子矩阵链的开始位置，结束位置j=i+l-1。第三层循环k=i,i+1,...,j-1是子矩阵链的分割点。迭代的次数可称为循环步。主循环的第一个循环步对i=1,....,n-1计算所有长度为2的子矩阵链的标量乘法次数M[i,i+1]，第二个循环步计算所有长度为3的子矩阵链的乘法次数M[i,i+2]。注意循环的终止和保持条件。（3）算法对程序数据的操作功能。图的搜索算法对数据的操作有三个功能，算法对图的数据建立元素分组的索引结构并且保存到队列，元素在队列中搜索并且出队创建输出线性序列，将搜索的出队元素在数据结构中索引的元素保存到队列。

        算法的分析有算法复杂度分析，摊还分析和新的方法。摊还分析又称为平摊分析，是对所有操作对所有元素时间代价的分析，从数据库存储和搜索发现，能改进数据结构的存储效率，发现了新的数据结构伸展树等。新的分析方法是程序功能结构分析。

     算法有数据结构上的算法，树和图的遍历算法（线性算法），矩阵计算（辅助数组的并行计算），图的两点间最短距离（子集合与路径选择）