计算机与人工智能导论 课件 第6章 算法与数据结构

第6章

算法与数据结构AI第6章知识导图算法与数据结构算法的定义与表示方法算法复杂度分析与评价非线性结构什么是算法算法设计实例线性结构第1章计算机工具与计算机演进史第2章计算机系统组成第3章计算机中的数据表示第4章操作系统与网络基础第5章软件构建基础：语言、编译与工程第6章算法与数据结构第7章数据管理与大数据技术第8章人工智能概述第9章机器学习基础第10章深度学习基础第11章机器人学、智能体与具身智能第12章自然语言处理与大语言模型第13章AI伦理、法律、治理与未来第14章AI赋能行业典型应用第15章前沿技术与实践能力培养常用表示方法从传统算法到AI算法为什么要分析复杂度时间复杂度空间复杂度复杂度分析在AI中的重要性数据结构概述数据结构定义数据结构的三要素学习数据结构的意义顺序表链表栈队列线性结构在人工智能中的应用树形结构图结构集合结构内容导航第6章

算法与数据结构6.1算法基础6.2算法复杂度分析6.3

数据结构概述6.4线性结构6.5非线性结构AI6.1算法基础什么是算法？01核心定义算法是为解决特定问题而设计的一系列明确、有限的指令或步骤，它是计算机解决问题的逻辑基础与执行蓝图。02核心地位程序=算法+数据结构。算法是程序的“灵魂”，决定了程序的效率与逻辑走向，是计算机系统的操作指南。算法的五个基本特性：①有穷性(Finiteness)算法必须在执行有限步骤后终止，不会陷入无限循环。②确定性(Definiteness)每一步骤都有明确、无歧义的含义，执行路径唯一。③可行性(Effectiveness)描述的操作可通过基本运算在有限时间内实现。④输入(Input)算法可以有零个或多个输入，作为初始数据。⑤输出(Output)算法至少有一个输出，反映对输入的处理结果。6.1算法基础算法的常用表示方法01自然语言描述优点：贴近日常语言习惯，无需专业编程基础，能快速阐述算法的核心思路与整体框架，适合初期沟通。缺点：缺乏严谨的语法规范，容易产生歧义；对于多分支、循环等复杂逻辑，文字描述会显得冗长且不够精准。02伪代码表示一种介于自然语言和编程语言之间的抽象描述工具，它保留了程序设计的结构化特征，同时又不受具体语法的限制，是算法设计与交流的“通用草稿”。03流程图表示使用标准化的几何图形（起止框、处理框、判断框等）和带箭头的流程线，将算法的逻辑步骤、判断条件和执行顺序以图形化方式直观呈现，是算法可视化的重要手段。6.1算法基础算法的常用表示方法示例（计算n的阶乘）：1.初始化result=1,i=1；2.若i≤n，则result=result×i，i=i+1；3.重复步骤2直至结束；4.输出result。核心价值•直观清晰：将抽象逻辑转化为图形，便于理解复杂的控制流。

•标准统一：符号规范无歧义，利于团队协作与沟通。

•易于调试：图形化展示便于发现逻辑漏洞与设计缺陷。图示：流程图基本符号示例6.1算法基础从传统算法到AI算法传统算法：规则驱动核心特征：完全由程序员预设逻辑与步骤，输出结果具有绝对的确定性与可解释性。典型场景：解决结构化、逻辑清晰的问题，如快速排序、二分查找、最短路径规划等。AI算法：数据驱动核心特征：不依赖人工编写的显式规则，通过从海量数据中自动学习模式与特征，实现对未知数据的预测。典型场景：处理复杂的非结构化数据，如图像识别、自然语言处理、推荐系统等。算法的共同基石：五大基本特性无论是传统逻辑还是智能模型，本质上都必须遵循算法的底层约束：有穷性（有限步骤终止）、确定性（无歧义）、可行性（可执行）、输入与输出。这是算法设计与验证的根本准则。内容导航第6章

算法与数据结构6.1算法基础6.2算法复杂度分析6.3

数据结构概述6.4线性结构6.5非线性结构AI6.2算法复杂度分析时间复杂度：大O记法(BigONotation)01/核心定义用于度量算法执行时间随问题规模n增长的变化趋势，它描述了算法运行时间的增长量级，而非具体的执行耗时，是评估算法效率的关键指标。02/简化法则忽略常数因子与低阶次要项，仅保留增长最快的最高阶项。例如：

多项式3n²+2n+5简化为O(n²)；线性式5n+10简化为O(n)。常见复杂度等级与特性（效率从高到低）大O表示复杂度名称增长趋势典型应用场景O(1)常数阶恒定，与数据规模无关数组下标访问、哈希表直接查询、简单计算O(logn)对数阶数据翻倍，步数仅加1有序数组二分查找、平衡二叉树查找、快速幂O(n)线性阶时间与数据量成正比单层循环遍历、顺序查找、简单的线性扫描O(n²)平方阶数据翻倍，时间翻四倍嵌套循环操作、冒泡/选择/插入排序、矩阵乘法6.2算法复杂度分析空间复杂度与时空权衡01空间复杂度定义：度量算法执行过程中所需占用的额外存储空间，随问题规模n增长的变化趋势，它量化了算法对内存资源的消耗程度。典型量级：常数阶O(1)、线性阶O(n)、平方阶O(n²)及对数阶O(logn)等。02时空权衡(Trade-off)空间换时间：利用额外存储空间缓存数据或建立索引，避免重复计算，显著提升运行速度。例如：数据库索引、图片预加载。时间换空间：在内存受限的环境下，通过实时计算替代数据存储，牺牲少量计算时间以节省宝贵的内存资源。例如：老旧设备上的程序优化。核心启示：算法优化没有绝对的“银弹”。在实际工程中，需根据硬件配置（如移动端vs服务器）、用户体验要求（如低延迟）及业务场景（如海量数据处理）来动态平衡时间与空间的消耗。内容导航第6章

算法与数据结构6.1算法基础6.2算法复杂度分析6.3数据结构概述6.4线性结构6.5非线性结构AI6.3数据结构概述数据结构的三要素数据结构是相互之间存在一种或多种特定关系的数据元素的集合，是计算机存储和组织数据的核心方式。它不仅是算法设计的基础，更直接决定了程序的运行效率与系统的整体性能表现。01逻辑结构：数据关系的抽象蓝图描述数据元素之间的抽象逻辑联系，如线性结构（数组、链表）、树形结构（二叉树）或图形结构，是构建数据组织的“骨架”。02存储结构：物理实现的载体数据在计算机内存中的具体存储方式，分为顺序存储（连续地址）与链式存储（离散节点+指针），决定了数据的存取效率与空间开销。03数据运算：功能价值的体现对数据结构施加的核心操作集合，包括插入、删除、查找、排序等，是衡量数据结构设计是否高效、适用的关键指标。图示：数据结构的体系分类与要素构成框架6.3数据结构概述学习数据结构的意义01学科枢纽：承上启下的知识核心它是计算机学科的“立交桥”，向上衔接程序设计、离散数学等基础理论，向下支撑操作系统、数据库、人工智能等核心应用领域。掌握它，就掌握了理解计算机系统运作的底层逻辑，是构建完整计算机知识体系的必经之路。图示：数据结构与其他课程的关系6.3数据结构概述学习数据结构的意义02能力基石：逻辑与效率的双重塑造它不仅训练你理清数据处理的完整逻辑，更教会你如何以最优方式组织、存储和操作数据。这种高效的思维模式，是进行复杂算法设计、开发高性能软件系统以及深入研究人工智能技术的坚实基础，也是从“会编程”进阶到“善编程”的关键。图示：数据结构的地位内容导航第6章

算法与数据结构6.1算法基础6.2算法复杂度分析6.3

数据结构概述6.4线性结构6.5非线性结构AI6.3线性结构逻辑相邻性除首尾外，每个元素仅有唯一的直接前驱与后继。顺序可访问性支持从头至尾的顺序遍历，或根据索引直接定位。结构易实现物理存储方式简单，在内存中易于连续或链式分配。线性结构是数据元素之间存在一对一逻辑关系的有序序列，元素按顺序排列，是构建数组、链表、栈与队列等复杂结构的基础。线性结构定义：6.3线性结构栈(Stack)与队列(Queue)01栈(Stack)核心特性：后进先出(LIFO)，仅允许在一端（栈顶）进行插入和删除操作。关键操作：push(入栈)、pop(出栈)、peek(查看栈顶元素)。生活实例：叠放的盘子、浏览器历史记录、编辑器撤销功能。图示：栈的入栈与出栈操作示意图6.3线性结构栈(Stack)与队列(Queue)02队列(Queue)先进先出(FIFO)遵循“先来先服务”原则，一端进行插入(enqueue)，另一端进行删除(dequeue)，体现了数据处理的公平性。核心特性：先进先出(FIFO)，队尾(rear)入队，队首(front)出队。关键操作：enqueue(入队)、dequeue(出队)、front(查看队首)。生活实例：食堂排队打饭、打印机任务队列、消息缓冲队列。图示:队列的入队与出队操作内容导航第6章

算法与数据结构6.1算法基础6.2算法复杂度分析6.3

数据结构概述6.4线性结构6.5非线性结构AI6.3非线性结构树形结构(Tree)核心定义一种描述数据元素之间“一对多”层次关系的非线性数据结构，由节点和连接节点的边组成，呈现出倒置的树状形态。关键特征结构中存在且仅存在一个没有前驱的根节点；其余节点分为互不相交的有限子集，每个子集构成一棵独立的子树。场景应用广泛应用于表达层级关系的场景，例如：企业的组织架构图、计算机的文件目录系统、家族的族谱世系图等。图示：大学的行政与教学组织架构，直观体现了树形结构的层级划分与隶属关系。6.3非线性结构图结构(Graph)核心定义描述数据元素之间“多对多”复杂关系的非线性数据结构，是现实中网状结构的抽象数学模型。关键要素由顶点(Vertex)代表数据实体，边(Edge)表示实体间的关联，二者共同构成图的拓扑结构。广泛应用于城市交通路网规划、社交网络好友推荐、互联网路由计算及地图导航路径寻优。典型应用图示：图的三种形状示例本章小结核心理念：程序=算法+数据结构这一公式揭示了程序设计的本质，是理解计算机科学与软件