【大话数据结构】- 读书笔记

2023-12-13 读书笔记

第一章 数据结构绪论

逻辑结构

• 集合结构
• 线性结构
• 树形结构
• 图形结构

物理结构

• 顺序存储结构
• 链式存储结构

可能在学习的时候会困惑、不懂、不理解、不会应用，甚至不知所云，可实际上无论学什么都是通过努力才可以学到真东西。只有真正掌握技术的人，才有可能去享用它。如果你中途放弃了，之前所有的努力和付出都会变的毫无意义。
学游泳难吗？掌握英语口语难吗？可能是难，但在掌握了的人的眼里，这根本不算什么，“就那么回事呀”。只要你相信自己一定可以学得会，学得好，既然无数人已经掌握了，你凭什么不行。
最终的结构一定是，你对着别人很牛的说：”数据结构-就那么回事。“

第二章 算法

2.4 算法的定义

算法是解决特定问题求解步骤的描述，在计算机中表现为指令的有限序列，并且每条指令表示一个或多个操作。

2.5 算法的特征

• 输入输出
  算法具有零个或多个输入, 算法至少有一个或多个输出
• 有穷性
  算法在执行有限的步骤之后， 自动结束而不会出现无限循环，并且每一个步骤在可接受的时间内完成。
• 确定性
  算法的每一个步骤都具有确定的含义，不会出现二义性，
• 可行性
  算法的每一步都必须是可行的，也就是说，每一步都能够通过执行有限次数完成。

2.6 算法的设计要求

好的算法具有如下特征：

• 正确性
• 可读性
• 健壮性
• 时间效率高和时间存储量低

每天有计划有效的学习进步一点，一年，两年下来会感受大不一样的。

2.9 算法时间的复杂度

大O记法

• O(1) :常数阶
  无论这个函数执行的常数是多少，都记为O(1), 而不是O(3), O(12)
• O(n)：线性阶
  函数中循环体中的代码要执行n次
• O(logn)对数阶
  2^x = n --> log2n
• O(n^2)：平方阶

推导大O阶方法

1. 用常数1取代运行时间中的所有加法常数。
2. 在修改后的运行次数函数中，只保留最高阶项。
3. 如果最高阶项存在且不是1， 则去除与这个项相乘的常数

eg:

算法的运行次数 f(n)

2.10 常见的时间复杂度

2.12 算法的空间复杂度

第三章 线性表