笔记关键词检索?

在所有笔记中搜索你感兴趣的关键词!

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

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


算法复杂度

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

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

时间复杂度相关公式:

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的实际效率。

评论 (0)

发布评论

你的邮箱地址不会被公开。请输入所有带 * 的信息。