数据结构与算法python版（1）-算法简介

1、时间复杂度

• 时间复杂度：用来评估算法运行效率的一个式子
• 常见的时间复杂度排序
  O(1)<O(logn)<O(n)<O(nlogn)<O(n²) <O(n²logn)<O(n³)

2、判断时间复杂度方法

• 确定问题规模：n
• 循环减半：logn
• k层关于n的循环：n^k
• 复杂情况：根据算法执行过程判断

3、时间复杂度举例

• 如下代码,时间复杂度为O（1）

print("hello world")

• 如下代码，时间复杂度为O（n）

for i in range(n):
print("hello world")

• 如下代码，时间复杂度为O（n²）

for i in range(n)
for j in range(n):
print("Hello world")

• 如下代码，每次循环减半的时候，时间复杂度为O（logn）

while n>1:
print(n)
n//=2

4、空间复杂度

• 空间复杂度：用来评估算法内存占用大小的式子
• 空间复杂度的表示方式与时间复杂度完全一样

• 算法使用了几个变量：O（1）
• 算法使用了长度为n的一组列表：O（n）
• 算法使用了m行n列的二维列表：O（mn）

• 通常情况下经常会以空间换时间