数据结构笔记：算法时间复杂度和线性表

数据结构基础知识点总结 本资源摘要信息涵盖了数据结构的基础知识点，包括算法的时间复杂度、空间复杂度、算法的分类、线性表的逻辑结构和操作等。 一、算法的时间复杂度 * 算法的时间复杂度是指算法执行所需的时间量级，通常用大O符号表示。 * 时间复杂度与问题的规模和初始状态相关。 * 例题：设有两个算法在同一机器上运行，其执行时间分别为100*n**2和2**n，要是前者快于后者，n至少要多大？求不等式100n**2<2**n，得n>=15。 二、算法的分类 * 根据算法的时间复杂度，可以将算法分为原地工作和非原地工作两类。 * 原地工作是指算法所需的额外空间相对于输入数据量是常数的。 * 例题：判断一个算法是否是原地工作的方法是，检查算法所需的额外空间是否相对于输入数据量是常数的。 三、线性表的逻辑结构 * 线性表是一种基本的数据结构，包括顺序表和链表两种实现方式。 * 顺序表的逻辑结构是数组，链表的逻辑结构是链式结构。 * 线性表的操作包括插入、删除、定位等。 四、链表的操作 * 插入操作是指在链表中插入一个新的结点。 * 删除操作是指从链表中删除一个结点。 * 定位操作是指在链表中查找一个结点。 * 例题：在顺序表中插入或删除一个结点需平均移动多少个结点？答：取决于顺序表的长度n和需要插入和删除的位置i。 五、循环链表 * 循环链表是一种特殊的链表结构，链表的最后一个结点指向链表的第一个结点。 * 循环链表的用法包括约瑟夫环、猴子选大王等。 * 双向循环链表判空的条件是head->next=head或head->pre=head。 六、其他知识点 * 算法的空间复杂度是指算法所需的额外空间量级。 * 算法的时间复杂度和空间复杂度是衡量算法性能的两个重要指标。 * 数据结构的选择取决于具体的问题和应用场景。 本资源摘要信息涵盖了数据结构的基础知识点，包括算法的时间复杂度、空间复杂度、算法的分类、线性表的逻辑结构和操作等，为学习数据结构奠定了坚实的基础。