发布者：潘万鹏 所属单位：盘州市第一中学 发布时间：2018-12-20 浏览数( -) 【举报】
【教学内容相关章节】
8.1算法分析初步 8.2再谈排序与搜索 8.3递归与分治
8.4贪心法
【教学目标】
（1）理解“基本操作”、渐近时间复杂度的概念和大O记号的含义；
（2）掌握“最大连续和”问题的各种算法及其时间复杂度分析；
（3）正确认识算法分析的优点和局限性，能正确使用分析结果；
（4）掌握归并排序和逆序对统计的分治算法；
（5）掌握归并排序和快速选择算法；
（6）熟练掌握二分查找算法，包括找上下界的算法；
（7）能用递归的方式思考和求解问题；
（8）熟练掌握用二分法求解非线性方程的方法；
（9）熟练掌握用二分法把优化问题转化为判定问题的方法；
（10）熟悉能用贪心法求解的各类经典的问题。
【教学要求】
理解渐近时间复杂度的概念和大O记号的含义；正确认识算法分析的优点和局限性，能正确使用分析结果；掌握归并排序和快速排序算法；熟练掌握二分查找算法；熟悉能用贪心法求解的各类经典的问题。
【教学内容提要】
本章介绍了设计高效算法的方法，首先介绍了分析算法效率的工具是渐近时间复杂度，并给出了大O记号的含义；接着介绍了分治法，用它去对数组进行归并排序或快速排序，以及查找过程中使用二分法；还介绍了贪心法求解问题。
【教学重点、难点】
教学重点：
（1）渐近时间复杂度的概念和大O记号的含义，并能对算法进行分析；
（2）掌握归并排序和快速排序算法；
（3）熟练掌握二分查找算法；
（4）熟悉能用贪心法求解的各类经典的问题。
教学难点：
（1）掌握归并排序和快速排序算法；
（2）熟练掌握二分查找算法；
（3）熟悉能用贪心法求解的各类经典的问题。
【课时安排】
8.1算法分析初步 8.2再谈排序与搜索 8.3递归与分治
8.4贪心法