时间复杂度

评估算法运行效率的一个单位，常见的时间复杂度：
O(1)

print('Hello World')   #基本的操作，加减乘除、打印等时间复杂度是O(1)

#结果是O(1)，不是O(3)
#O(1)，O理解为大约，1理解为一个单位。O(n)，O理解为大约，n理解为单位。O(n^2)，O理解为大约，n^2理解为单位。只是单位大小有区别，比如小时、分钟、秒
#比如几秒钟，打印三次不会表达成3个几秒钟，因为时间复杂度是用来表达一个大概值，所以统称为几秒钟
#这里是基本操作重复执行的次数只要没有上升到n，都是O(1)
print("Hello World1")
print("Hello World2")
print("Hello World3")

O(n)

for i in range(n):
    print('Hello World')

O(n^2)

for i in range(n):
    for j in range(n):
        print('Hello World')

#结果是O(n^2)，不是O(n^2 + n)
#n^2是一个大单位，n是一个小单位，不会表达成几分钟零几秒。只留大单位表达大概值
for i in range(n):
    print('Hello World')
    for j in range(n):
        print('Hello World')

O(n^3)

for i in range(n):
    for j in range(n):
        for k in range(n):
            print('Hello World')

O(logn)

#每次循环减半
while n > 1:
    print(n)
    n = n // 2

• 时间复杂度用来区分随着n变大，时间复杂度高的算法会越来越大
  比如O(n)和O(10n)，随着n变大，两者始终相差10倍
  但是O(n)和O(n^2)，随着n变大，O(n ^ 2)会远大于O(n)
• 计算机性能一样、问题规模一样并且足够大的情况下，时间复杂度高的算法比复杂度低的算法慢
  常见的时间复杂度按效率排序：
  O(1)<O(logn)<O(n)<O(nlogn)<O(n ^ 2)<O(n ^ 2 logn)<O(n^3)

空间复杂度

用来评估算法占用内存大小的一个单位

• 算法使用了几个变量：O(1)
• 算法使用了长度为n的一维列表：O(n)
• 算法使用了m行n列的二维列表：O(mn)
  内存现在已经很便宜了，所以有时候会使用空间换时间