计算基础教程 2

授课内容算法概述学时2教学目标知识目标理解算法的基本概念、要素和特征掌握算法设计的基本步骤和方法学会算法的时间复杂度和空间复杂度分析方法了解算法在计算机科学中的重要地位能力目标能够运用算法思想分析和解决实际问题具备初步的算法设计和分析能力能够使用不同的工具描述算法重点与难点重点算法的基本概念和特征：理解算法的定义、要素和五大基本特征算法分析方法：掌握时间复杂度和空间复杂度的分析方法算法设计步骤：了解从问题分析到算法实现的完整流程算法的描述工具：熟悉各种算法描述方法的优缺点难点算法思想的实际应用：如何将抽象的算法思想应用于具体问题求解复杂度分析的理解：深入理解渐近时间复杂度的概念和计算方法教学内容第一部分：课程导入1、点名与签到2、课程重要性阐述结合实际应用场景讲解课程性质：理论与实践相结合的专业核心课程教学目标：培养学生算法设计和分析的核心能力学科地位：计算机学科的理论基础和核心内容企业需求：IT企业招聘程序员的必备技能考研与竞赛需求：算法是计算机考研、各类编程竞赛的核心考点

第二部分：新课讲解一、算法的定义核心定义算法是解决特定问题的有限、确定的计算步骤序列。它是解决问题的机械步骤，具有明确的输入、输出和执行规则。算法的基本特征1.

有穷性：算法必须在有限步骤内结束2.

确定性：每一步骤必须有明确的含义3.

可行性：每个步骤都必须是可执行的4.

输入：有零个或多个输入5.

输出：有一个或多个输出二、算法的特征1.

输入性2.

输出性3.

确定性4.有穷性5.可行性三、算法描述1、自然语言描述最简单的描述算法的方法是使用自然语言。使用自然语言来描述算法的优点是简单并且便于理解和阅读；缺点是不够严谨，并且对复杂的逻辑关系（例如：多重嵌套的分支或循环）很难进行清晰描述。2、流程图描述使用程序流程图描述算法的优点是简洁明了，便于表示复杂的逻辑结构，对于分支、循环的处理方案一目了然，便于对算法进行分析以及检查算法设计中的错误或疏漏之处。使用流程图描述的最大缺点是流程图的绘制比较麻烦，尤其是算法中存在多重嵌套的分支或循环时。3、伪代码描述伪代码是介于自然语言和计算机编程语言之间的描述语言，它结合了自然语言的方便性与编程语言强大的逻辑描述能力，是描述算法最常用的方式。伪代码的优点是书写方便灵活、描述能力强并且不受编程语言语法规则的限制。其缺点是严谨性略差，以及随着描述代码的增长可读性逐渐变差。四、算法评价1、时间复杂度概念时间复杂度的概念定义为：衡量算法运行时间随输入规模增长的变化趋势。它不计算具体的运行时间，而是分析操作次数的增长级别，以帮助我们在理论上比较不同算法的效率。2、表示符号时间复杂度描述的是渐进变化的趋势，它有三个表示符号：O（渐进上界）、Ω（渐进下界）和θ（确界）。3、计算方法在计算时间复杂度时，通常用n表示输入规模，而计算时一般会忽略关于n的低阶项和常数，例如：如果T(n)=3n2+2n+1，我们记时间复杂度为O(n2)。2、空间复杂度概念空间复杂度是对一个算法在运行过程中临时占用存储空间大小的一个度量，用于分析算法对内存的消耗随输入规模n的增长趋势。与时间复杂度一样，常见的空间复杂度有O(1)、O(n)、O(n2)

等。说明算法的空间复杂度在计算时一般不包括输入数据本身占用的空间。例如，排序算法的空间复杂度通常指除待排序数据外需要的额外空间。五、编程言与编程环境1、概述算法只是问题的解决方案，或者说是问题的解题原理，它本身与编程语言并无直接联系。本课程选择使用C++语言进行算法的编程实现，这样的好处为入门门槛比较低（学生已普遍学习过C语言）并且兼顾各种编程竞赛与学生工作面试的需求。2、编程环境对于C++而言，其可选的IDE有很多，常用的有Dev-C++、VisualStudio、Code::Blocks等。我们选择的编程环境是Dev-C++，它的最大优点是：简单并且免费。3、万能头文件使用Dev-C++还有一个好处，那就是它支持万能头文件。万能头文件的名字为“bits/stdc++.h”只要在程序的开始部分添加如下语句，程序中就不需要再包含任何其它头文件了。#include<bits/st