元数据

高亮划线

2.9 算法时间复杂度

• 📌 循环的时间复杂度等于循环体的复杂度乘以该循环运行的次数。

  • ⏱ 2023-01-25 14:05:37

3.4 线性表的顺序存储结构

• 📌 数组的长度是存放线性表的存储空间的长度，存储分配后这个量一般是不变的

  • ⏱ 2023-01-25 15:45:52

• 📌 线性表的长度是线性表中数据元素的个数，随着线性表插入和删除操作的进行，这个量是变化的。

  • ⏱ 2023-01-25 15:46:48

• 📌 在任意时刻，线性表的长度应该小于等于数组的长度。

  • ⏱ 2023-01-25 15:46:57

读书笔记

2.9 算法时间复杂度

划线评论

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

  • 💭 计算时间复杂度
  • ⏱ 2023-01-25 14:07:55

划线评论

• 📌 事实上无论n为多少，上面的两段代码就是3次和12次执行的差异。这种与问题的大小无关（n的多少），执行时间恒定的算法，我们称之为具有O(1)的时间复杂度，又叫常数阶

  • 💭 常数阶
  • ⏱ 2023-01-25 14:01:16

划线评论

• 📌 显然，由此算法时间复杂度的定义可知，我们的三个求和算法的时间复杂度分别为O(n)，O(1)，O(n2)。我们分别给它们取了非官方的名称，O(1)叫常数阶、O(n)叫线性阶、O(n2)叫平方阶，当然，还有其他的一些阶，我们之后会介绍

  • 💭 算法的时间复杂度
  • ⏱ 2023-01-25 13:57:05

2.11 最坏情况与平均情况

划线评论

• 📌 对算法的分析，一种方法是计算所有情况的平均值，这种时间复杂度的计算方法称为平均时间复杂度。另一种方法是计算最坏情况下的时间复杂度，这种方法称为最坏时间复杂度。一般在没有特殊说明的情况下，都是指最坏时间复杂度。

  • 💭 算法的分析
  • ⏱ 2023-01-25 14:22:01

2.12 算法空间复杂度

划线评论

• 📌 算法的空间复杂度通过计算算法所需的存储空间实现，算法空间复杂度的计算公式记作：S(n)=O(f(n))，其中，n为问题的规模，f(n)为语句关于n所占存储空间的函数。

  • 💭 算法空间复杂度计算公式
  • ⏱ 2023-01-25 14:31:59

本书评论