算法-时间复杂度和空间复杂度
刷算法必备时间和空间复杂度，记录下方便查询。
时间复杂度
概念
时间复杂度衡量的是算法 执行所需的时间 随输入规模 n 增长的变化趋势，用大O 表示法描述（通常是看这个循环）。
分类
常数时间O(1)
无论输入多大，执行时间固定。
def sum(a,b):return a + b
线性时间O(n)
执行时间与输入规模 n 成正比。
def sum(n):sum = 0 for i in range(n):sum += ireturn sum 平方时间O(n^2)
常见于双重循环，执行时间与 n² 成正比。
def sum(arr,target):n = len(arr)for i in range(n):for j in range(i+1,n):if arr[i] + arr[j] == target:return [i,j]return [-1,-1]对数时间O(log n)
执行时间随 n 增长而增长，但增速远慢于线性（如二分查找）,这里的log n是以2为底的哈。
def binary_search(arr, target):low, high = 0, len(arr) - 1while low <= high:mid = (low + high) // 2if arr[mid] == target:return midelif arr[mid] < target:low = mid + 1 # 每次缩小一半范围，时间复杂度 O(log n)else:high = mid - 1return -1def isUgly(self, n: int) -> bool:if n <= 0 :return Falsefactors = {2, 3, 5}for factor in factors :while n % factor == 0:n /= factorreturn n == 1对数概念
如果 aˣ = N（a > 0，a ≠ 1），那么数 x 叫做以 a 为底 N 的对数记作：
-
a 叫做对数的底数
-
N 叫做真数
常用对数
-
自然对数：以 e 为底（e ≈ 2.71828），记作 lnN
-
常用对数：以 10 为底，记作 lgN 或 logN（计算机科学中常表示以2为底）
运算规则
-
乘法规则：logₐ(MN) = logₐM + logₐN
-
除法规则：logₐ(M/N) = logₐM - logₐN
-
幂规则：logₐMⁿ = n·logₐM
-
换底公式：logₐb = logₖb / logₖa （k > 0，k ≠ 1）
线性对数时间O(n log n)
转化为O(log n^n)常见于高效排序算法（如归并排序、快速排序）。
空间复杂度
概念
空间复杂度表示算法在执行过程中所需的存储空间与问题规模之间的关系，通常用大O符号表示。（通常是看这个定义参数）
分类
常数空间O(1)
算法使用的空间不随输入规模变化。
def sum(n):# 定义了一次total = 0for i in range(n):total += ireturn total线性空间O(n)
算法使用的空间与输入规模成线性关系
def sum2(n,m):# 给每个n去*m后的数组return ans = [ _* m for _ in range(n)]
平方空间O(n^2)
算法使用的空间与输入规模的平方成正比
def quadratic_space(n):# 创建N位二维数组 默认位0的matrix = [[0 for _ in range(n)] for _ in range(n)]# 等价于 [[0]* n] * nreturn matrix对数时间O(log n)
算法使用的空间与输入规模的对数成正比
def gcd_recursive(a, b):return a if b == 0 else gcd_recursive(b, a % b)