数据结构与算法：衡量算法好坏的指标——复杂度

1.复杂度

复杂度，用来分析算法执行过程中，所需要的资源。
时间复杂度是衡量所需要的时间。
空间复杂度，是衡量所需要的(内存)空间。

1.1 时间复杂度

特性

1.衡量算法执行所需时间
2.根据「常数操作」次数推定
3.一般以最大数据量N作为衡量基准

如何表示？

通过O(x)计数法表示

O 用来表示 最差情况；θ 表示平均情况；Ω 最好情况

时间复杂度其实表现的是一种趋势，随着数据量增加，消耗的时间呈什么样态地增长(常数操作次数的变化趋势)

常见的复杂度

O(n2)

代表指数级增长

O(n)

线性增长

O(logn)

对数增长

O(1)

不增长

用函数图像来表示时间复杂度来看：

在数据量极少的时候，可能看不出算法的优劣，只有在数据量极大的时候，讨论 时间复杂度才有意义。

1.2 空间复杂度

同样空间复杂度是指，所需要的内存大小增长趋势。比如用来存储N个数，空间复杂度就是O(N)，用来存储有限个数，空间复杂度是O(1)……以此类推。

O() 中的数字或者字母，代表了一种趋势，而不是一个具体的值。

额外空间复杂度

除了已知占用空间，要完成算法，还需要多少空间。