大 O 复杂度表示法是一种粗略衡量算法性能的方法，以便在讨论算法时进行比较。 大 O 复杂度表示法表示代码（消耗时间/占用空间）随数据规模增长的变化趋势： 时间复杂度的全称是渐进时间复杂度，表示算法的执行时间与数据规模之间的增长关系。 空间复杂度全称就是渐进空间复杂度，表示算法的存储空间与数据规模之间的增长关系。 之所以分别衡量时间和空间，是因为可能一种算法执行的操作比另一种算法少，但它却占用更多的内存。 所以需要根据不同的要求来选择不同的算法。 下面是一些常见的复杂度： | 名字 | 复杂度 | 感受 | |--|--|--| | 常数复杂度 | O(1) | 了不起 | | 对数复杂度 | O(log N) | 很棒 | | 线性复杂度 | O(N) | 还好 | | 线性对数复杂度 | O(N log N) | 呵呵 | | 次方复杂度 | O(N ^ 2) | 狗屎 | | 指数复杂度 | O(2 ^ N) | 可怕 | | 阶乘复杂度 | O(N!) | 可以骂人吗 | 为了让你对这些的操作数量级有更直观的认识。来看看指定 N，这些复杂度计算出来的值是多少。 | | N = 5 | 10 | 20 | 30 | |--|--|--|--|--| | O(1) | 1 | 1 | 1 | 1 | | O(log N) | 2.3219... | 3.3219... | 4.3219... | 4.9068... | | O(N) | 5 | 10 | 20 | 30 | | O(N log N) | 11.609... | 33.219... | 84.638... | 147.204... | | O(N ^ 2) | 25 | 100 | 400 | 900 | | O(2 ^ N) | 32 | 1024 | 1,048,576 | 1,073,741,824 | | O(N!) | 120 | 3,628,800 | 2,432,902,0... | 265,252,859,812,191,058,636,308,480,000,000 | O(1) O(log N) O(N) O(N log N) O(N ^ 2) O(2 ^ N) O(N!) 看到了吧，即使对于相对较小的数据集，也会做大量的额外工作。 对于数据结构，通常会执行如下 4 种类型的操作：访问、搜索、插入和删除。 需要注意的是，一种数据结构可能擅长一种操作，另一种操作却很糟。 | | 访问 | 搜索 | 插入 | 删除 | |--|--|--|--|--| | 数组 | O(1) | O(N) | O(N) | O(N) | | 链表 | O(N) | O(N) | O(1) | O(1) | | 二叉搜索树 | O(log N) | O(log N) | O(log N) | O(log N) | 直观感受是 | | 访问 | 搜索 | 插入 | 删除 | |--|--|--|--|--| | 数组 | 了不起 | 还好 | 还好 | 还好 | | 链表 | 还好 | 还好 | 了不起 | 了不起 | | 二叉搜索树 | 很棒 | 很棒 | 很棒 | 很棒 | 更进一步，某些操作将具有不同的平均性能和最坏情况性能。 没有完美的数据结构，可以根据正在使用的数据以及将使用它做的事情来做选择。 这就是为什么了解许多不同的常见数据结构很重要的原因，可以做出更好的选择。