数据结构与算法 - 复杂度

1, 复杂度用来干什么?

答: 用来衡量算法的执行效率.

2, 为什么不通过直接在机器上执行一下某一个算法来作为对执行效率的考量呢?

答: 不同配置的机器对同一个算法的执行效率结果不同; 即使同一个机器, 不同时间不同运行状态下, 针对同一个算法程序的执行结果也是不同的.

3, 复杂度分为: 时间复杂度和空间复杂度

答: 其中时间复杂度更为常见, 因为数据结构与算法的目的, 主要是用来写出高性能且稳定的程序, 另外由于硬件的价格并不是限制程序的主要因素, 所以, 一般用时间复杂度来评价算法的执行效率. 不仅如此, 有时候为了对程序的时间进行更高的要求, 用空间换时间也是一种行之有效的手段.

4, 复杂度的大 O 表示法

答: 时间复杂度, 又称为渐进时间复杂度, 意思是, 随数据规模的不断增大算法的执行效率变化趋势.

所以, 初学算法的同学, 可能会认为大 O 表示法表示的具体时间

有点类似高数中的极限定义, 随着 X 不断趋近某个数值, Y 的趋近情况, 复杂度中: 随着数据规模的不断趋于无穷大, 执行效率的趋势.

5, 常见的时间复杂度

答: O(1), O(n), ...