读书笔记 算法 algorithms 第一章 时间复杂度 马士兵解析

书上写的太复杂了,不深读文章不容易理解. 看马士兵的视频容易理解些.

如何测算算法的优劣:

时间测算

1. 计算算法的时间差
2. 幅度不够循环来凑(时间少看不出算法的差别 就使用循环加大幅度)

时间复杂度

空间测算

1. 看使用空间的大小

空间复杂度.

Big O 标记法

学术上算法区分算法的优劣

时间随着问题规模的扩大 时间怎么进行变化的
空间同理

1. 不考虑必须要的操作. 循环, 赋初值, 程序初始化,

• 比如访问数组的最后一个值花的时间, 不随着数组的规模扩大而扩大, 这时时间复杂度是 O(1). 时间是固定的一个值.

2. 不考虑常数项. 2n 到 n

• 比如 访问链表的某个位置的值花的时间. (一般时间复杂度我们都是讲的"最差"情况), 那么假设链表的规模是n, 那么时间复杂度就是O(n).
  如果用图表来表示
  

当问题规模在1的时候,时间是1. 当问题规模是2的时候, 时间是2.

下面是算法书里面的图解

分为标准图像 和对数图像. 我上面画的和对数图像是一致的.

当然时间复杂度还有O(n2),O(n3) ,n的平方(两遍循环),n的立方(三遍循环).

• 求数组的内所有数字的平均数是什么. 想一想…
• O(n)