基础速通

复杂度分析

时间复杂度的计算方法

针对代码，逐行从上到下计算代码一共的操作次数即可。此操作数量中的各种系数、常数项都可以忽略。根据此原则，可以总结出以下计数简化技巧。

1. 忽略循环次数中的常数项。因为它们都与n无关，所以对时间复杂度不产生影响。
2. 省略所有系数，因为前面的系数对时间复杂度没有影响。
3. 循环嵌套时使用乘法。总操作数量等于外层循环和内层循环操作数量之积，每一层循环依然可以分别套用第1点和第2点的技巧。

空间复杂度的计算方法

通常不太考虑，很多算法都是空间换时间。空间由很多部分组成：

在分析一段程序的空间复杂度时，只统计暂存数据、栈帧空间和输出数据三部分。统计方法就是计算整个程序中需要的所有空间大小。

递归函数时才需要注意统计栈帧空间，函数递归调用会占用大量的空间。

数组和链表

跳过概念，需要知道一个点： 数组和链表对缓存的利用效率是不同的，主要体现在以下几个方面。

• 占用空间：链表元素比数组元素占用空间更多，导致缓存中容纳的有效数据量更少。
• 缓存行：链表数据分散在内存各处，而缓存是“按行加载”的，因此加载到无效数据的比例更高。
• 预取机制：数组比链表的数据访问模式更具“可预测性”，即系统更容易猜出即将被加载的数据。
• 空间局部性：数组被存储在集中的内存空间中，因此被加载数据附近的数据更有可能即将被访问。 总体而言，数组具有更高的缓存命中率，因此它在操作效率上通常优于链表。这使得在解决算法问题时，基于数组实现的数据结构往往更受欢迎。

需要注意的是，高缓存效率并不意味着数组在所有情况下都优于链表。实际应用中选择哪种数据结构，应根据具体需求来决定。例如，数组和链表都可以实现“栈”数据结构（下一章会详细介绍），但它们适用于不同场景。

在做算法题时，我们会倾向于选择基于数组实现的栈（比如C++自带的栈实现），因为它提供了更高的操作效率和随机访问的能力，代价仅是需要预先为数组分配一定的内存空间。

如果数据量非常大、动态性很高、栈的预期大小难以估计，那么基于链表实现的栈更加合适。链表能够将大量数据分散存储于内存的不同部分，并且避免了数组扩容产生的额外开销。

参考资料：Hello算法