复杂度

1. 时间复杂度

常见时间复杂度高低

O(1) < O(logn) < O(n) < O(nlogn) < O(logn2) < O(n2logn) < < O(logn3)

复杂问题的时间复杂度

O(n!) O(2的n次方) O(n的n次方)

快速判断算法复杂度(使用具大多数简单情况):

• 确定问题: n
• 循环减半问题: logn
• k层关于n的循环: n的k次方

复杂情况:

根据算法执行情况判断

2. 空间复杂度

使用了几个变量: O(1)
使用了长度为n的一维列表: O(n)
使用了m行n列的二维列表: O(mn)

算法中, 时间比空间重要, 所以有一个规则
空间换时间