1. 第一节

1.1 时间复杂度

  • 常数时间的操作:一个操作如果和数据量没有关系,每次都是固定时间内完成的操作,叫做常数操作。
  • 时间复杂度为一个算法流程中,常数操作数量的指标。常用O(读作bigO)来表示。具体来说,在常数操作数量的表达式中,只要高阶项,不要低阶项,也不要高阶项的系数,剩下的部分如果记为f(N),那么时间复杂度为O(f(N))。
  • 评价一个算法流程的好坏,先看时间复杂度的指标然后再分析不同数据样本下的实际运行时间,也就是常数项时间

1.2 冒泡排序

实现代码:

动画演示:

实现思路:

  • 时间复杂度O(N^2),额外空间复杂度O(1)

1.3 选择排序

实现代码:

动画演示:

  • 时间复杂度O(N^2),额外空间复杂度O(1)

1.4 插入排序

实现代码:

动画演示:

实现思路:

  • 时间复杂度O(N^2),额外空间复杂度O(1)