时间复杂度

时间复杂度是用来衡量对常数操作次数的指标。

什么是常数操作呢？

与数据量没有关系，能在固定时间内完成的操组叫做常数时间操作。

冒泡排序的时间复杂度

假设给定一个数组：[1,2,3,4,5,6,7,8]，按照冒泡排序的算法分析，需要经历两种操作：

1. 遍历数组；

2. 交换数据；

遍历数组要经历 8 + 7 + 6 + ... + 1次，一个等差数列求和。交换数据是固定操作。

等差数列的求和公式为：

展开后得出最高阶为 n^2/2。常数 1/2，以及 na1 等低阶项忽略。因此最终冒泡排序的时间复杂度为 O(n^2)。

为什么这样规定呢，因为在 0 趋于 ∞ 时

二分查找的复杂度

每次查询都是折半操作，所以时间复杂度为

但是在实际的复杂度表示中，2 是被省略的，直接记作 O(logN) ，这是因为不论底数是多少，计算得到的值也是很小的，所以默认写成 O(logN)。

常数的时间复杂度是O(1)。

动态数组

固定数组：空间分配确定后，不会动态扩容。无法存放超过分配空间大小的数据。

动态数组：当数据存放不下的时候，会自动扩容，使得数据得以存放。

思考一个问题：Java 中的动态数组的扩容机制会不会影响它的性能？

在时间复杂度上并不会影响。举个：

假设 ArrayList 容量只有 1，此时放入 2 个数据，需要拷贝原始数据，并扩容。(ArrayList 底层扩容机制是原有容量的 1.5)。因此每次扩容的时间复杂度是个常数。记为 O(1)。因此动态数组相比于固定数组的慢是一种常数时间的慢，从时间复杂度来说，并不影响。