《程序设计解题策略》——1.7 本章小结

  1. 云栖社区>
  2. 华章计算机>
  3. 博客>
  4. 正文

《程序设计解题策略》——1.7 本章小结

华章计算机 2017-07-03 15:43:00 浏览799
展开阅读全文

本节书摘来自华章计算机《程序设计解题策略》一书中的第1章,第1.7节,作者:吴永辉 王建德 更多章节内容可以访问云栖社区“华章计算机”公众号查看。

1.7 本章小结

树是一个具有层次结构的集合,一种没有回路的连通图,在程序设计竞赛中,许多试题的数据关系呈现树型结构。为了拓宽读者对树的认识、拓展树的应用范围、掌握更多利用树型结构解题的处理方法,我们在本章中介绍了以往竞赛曾涉及的一些前沿知识:
1) 探讨了如何利用划分树求解整数区间内第k大的值:即先离线构建出整个查询区间的划分树,然后在划分树中查找某子区间中第k大值。这个算法保证能在O(logn)的时间复杂度内快速求出问题解。
2) 通过分析一些蕴涵最小生成树性质的试题,给出了应用最小生成树原理优化算法的一般思路和方法,在此基础上引入了最小生成树的两个拓展——最小度限制生成树和k小生成树,并

网友评论

登录后评论
0/500
评论
华章计算机
+ 关注
所属云栖号: 华章计算机