about 2 months ago

时间复杂度

定义:

程序运行次数与数据量的比值

七种时间复杂度:
1. O(1)
2. O(log n)
3. O(n)
4. O(n^2)
5. O(n^3)
6. O(2^n)
7. O(n!)

常用算法时间复杂度:
1. 二分查找: O(log n)
2. 二叉树遍历: O(n)
3. 最佳排序矩阵搜索(已排好序的二维矩阵): O(n)
4. 归并排序: O(n log n)

空间复杂度

定义:

程序运行时占用内存的大小

其他

增加空间复杂度可以降低时间复杂度,空间换时间。

← Python Note:003