lambdagent/agentexample/sample_knowledge/数据结构讲义-第1章-绪论.md

第 1 章 绪论（示例讲义）

本文件是示例知识库的演示材料，为简化版讲义提纲。

1.1 什么是数据结构

数据结构是相互之间存在一种或多种特定关系的数据元素的集合。 研究内容包括三个层面：

• 逻辑结构：数据元素之间的逻辑关系 —— 集合、线性结构、 树形结构、图状结构四大类。
• 存储结构（物理结构）：逻辑结构在计算机中的表示 —— 顺序存储、链式存储、索引存储、散列存储。
• 数据的运算：插入、删除、查找、排序等，定义在逻辑结构上， 实现依赖存储结构。

1.2 抽象数据类型（ADT）

抽象数据类型 = 数据对象 + 数据关系 + 基本操作。 ADT 把「做什么」与「怎么做」分离：使用者只关心操作语义， 实现者决定存储与算法。例如 ADT Stack 只规定 push/pop/top 的行为， 不规定用数组还是链表实现。

1.3 算法及其评价

算法的五个特性：有穷性、确定性、可行性、输入、输出。

时间复杂度

用渐进上界 O 记号描述基本操作执行次数随问题规模 n 的增长趋势：

• 常见量级：O(1) < O(log n) < O(n) < O(n log n) < O(n²) < O(2ⁿ)
• 分析方法：找出最深层循环中的基本操作，数它的执行次数。
• 例：两层嵌套循环遍历 n×n 矩阵为 O(n²)；折半查找每次缩小一半 规模，为 O(log n)。

空间复杂度

算法运行过程中临时占用存储空间的量级。原地工作的算法空间复杂度 为 O(1)；递归算法的空间复杂度要计入递归工作栈的深度。

本章要点（考试常考）

1. 逻辑结构与存储结构的区别与举例。
2. ADT 的三要素。
3. 给一段代码，写出其时间复杂度（必考，通常 1-2 题）。
4. 递归程序的空间复杂度分析。