《算法导论（原书第3版)》 ── Introduction to Algorithms, third edition

作者：[美] Thomas H.Cormen，[美] Charles E.Leiserson，[美] Ronald L.Rivest，[美] Clifford Stein 著，殷建平，徐云，王刚等译

2020-10-30 10:57 概念评论 0

时间复杂度：需要多少时间

空间复杂度：需要多少内存空间

时间复杂度相关公式：

N*1个操作 = O(N)

O(N) + O(N) = O(N)

N/2 *1个操作 = 1/2 * O(N) = O(N)

O (N ^ 2) + O (N) = O (N ^ 2)

1+2+3....+N = N * (N + 1) / 2 = N * N / 2 + N / 2 = 1 / 2 * O (N ^ 2) + 1 / 2 * O (N) = O (N ^ 2) + O (N) = O (N ^ 2)

空间复杂度相关公式：

2个单位的内存空间 = O(1)

定理：if x的时间复杂度要由于y的时间复杂度，那么，假设存在一个足够大的数M，当n>M时，我们可以保证X的时间效率要优于Y的实际效率。