高中信息技术浙教版：4-1算法的发展-教学课件

4.1 算法的发展 4.1.1 常见算法的改进及发展 穷举算法 递归算法 动态规划算法 算法 数据存储 数组 链表 跳跃表算法 遍历 线性遍历 树结构遍历 平衡树 排序算法的发展变化 解决n个数的升序排列问题 冒泡排序 依次比较前后两个元素，如果逆序就交换两个位置上的元素，将最小数交换到最前面，这样的过程重复n-1遍即可实现，算法的时复杂度为O(n2)。 n个元素冒泡排序的比较次数是n(n-1)/2，最坏情况下的交换次数要达到n(n-1)/2，交换频繁，影响效率。 选择排序 如果不交换元素位置，待找到无序区中的最小元素后，直接把最小元素交换到有序区的末位位置，这样就减少了交换的次数，但时间复杂度依然为O(n2)。 插入排序 在访问无序区元素的过程中，将当前访问的元素直接在有序区中找一个合适的位置插入即可。 希尔排序 既然插入排序在基本有序的情况下性能相对较好，那就想办法达到这样的状态，于是有人想出了跳跃分割的方式，将相距某个增量的数据组成一个子序列，这样就能保证在子序列内分别进行插入排序后，得到的结果基本有序。 排序算法的发展变化 解决n个数的升序排列问题 快速排序和归并排序 快速排序和归并排序都利用了分治思想，核心在于“分而治之，各个击破“ 快速排序计算过程： （1）从数值队列中选择一个基准元素。 （2）将队列中的其他元素与基准元素比较，比基准元素小的元素放在基准元素的左边，比基准元素大的放在右边，则队列被基准元素分为左右两个区间。 （3）对两个区间的值分别递归步骤（2），使其最终形成有序的序列。 排序算法的发展变化 解决n个数的升序排列问题 例1 对于队列数值“4、3、6、2、5”采用快速排序进行升序排序 以上采用的排序方法都属于内排序，内排序是指能够在内存中完成的排序，当计算机内存小于数据本身大小时，无法一次性将数据加载到内存，这时候就需要采用外排序的方式。 外排序主要是针对大文件的排序，将需要排序的数据文件存放到存储器中，每次加载部分数据到内存，不断进行内存和外部存储器之间的数据交换，最终保证文件中的每个数据都完成排序。 例2 有4GB的数据文件需要进行排序，当前操作系统的有效可用内存为1GB，则需要按照外归并排序的流程完成排序。 （3）采用四路归并的方式进行归并排序：在4个1GB文件中，分别读取200MB数据存入内存的输入缓冲区，共占用计算内存800MB，将剩余的200MB作为输出缓冲区，如图所示。 （1）将4GB的数据文件平均拆分为4个1GB的数据文件 （2）将每份1GB数据文件加载到内存，采用内排序的方式（如快速排序）在内存中完成对该数据文件的排序，并将排序后的结果写入文件。 （4）将输入缓冲区的四路数据进行归并排序，依次存入输出缓冲区，当输出缓冲区满时，则写入文件，当缓冲区中某路数据输入完毕后，则再向文件中读取200MB数据存入输入缓冲区，不断进行该过程直到所有的数据通过四路归并的方式完成排序。 例2 有4GB的数据文件需要进行排序，当前操作系统的有效可用内存为1GB，则需要按照外归并排序的流程完成排序。 设有字母序列{Q,D,F,X,A,P,N,B,Y,M,C,W}，请写出按二路归并方法对该序列进行升序排序的过程。 问题与讨论 Q D F X A P N B Y M C W Q D F X A P N B Y M C W Q D F X A P N B Y M C W Q D X A F P D Q X A N B M C Y W N B M C D Q A X B N C M F P Y W D F Q A P X B N Y C M W A D F P Q X B C M N W Y A B C D F M N P Q W X Y F P Y W 分治法 分解成子问题 分别解决 合并答案 4.1.2 立足系统架构的算法发展 并行计算是指同时使用多种计算资源解决计算问题的过程，是提高计算机系统计算速度和处理能力的一种有效手段。 它的基本思想是用多个处理器来协同求解同一问题，即将被求解的问题分解成若干个部分，各部分均由一个独立的处理机来并行计算。 4.1.2 立足系统架构的算法发展 从程序和算法设计的角度来看，并行计算可分为任务并行和数据并行。 任务并行是不同的CPU执行不同的任务，处理相同的数据。 数据并行是每个核心执行相同的命令，处理不同的数据。 在现有算法不适应时，要善于发掘和利用现有串行算法中的并行性，合理地选择算法，并且合理地设置阈值，能够十分有效地提高计算机的运行效率。 4.1.2 立足系统架构的算法发展 4.1.3 基于大数据和人工智能的算法发展 课堂小结 思考与练习 题目描述：给定一个