电脑编程中常用的重要公式215

1. 时间复杂度公式- 大 O 表示法: O(f(n))，其中 n 是输入大小，f(n) 是算法运行时间随 n 渐近增长的函数。
- 常见的时间复杂度:
- O(1): 常数时间，与输入大小无关
- O(log n): 对数时间，随输入大小以对数方式增加
- O(n): 线性时间，随输入大小线性增加
- O(n^2): 平方时间，随输入大小以平方方式增加
- O(n^3): 立方时间，随输入大小以立方方式增加

2. 空间复杂度公式- 空间复杂度: 算法运行时所需的内存空间量。
- 常见的空间复杂度:
- O(1): 常数空间，与输入大小无关
- O(n): 线性空间，随输入大小线性增加
- O(n^2): 平方空间，随输入大小以平方方式增加

3. 斐波那契数列公式- F(n) = F(n-1) + F(n-2)，其中 F(0) = 0，F(1) = 1
- 渐近公式: F(n) ≈ (φ^n) / √5，其中 φ = (1 + √5) / 2 ≈ 1.618 是黄金比例

4. 素数判定公式- 费马小定理: 如果 p 是素数，则对于任何 a，a^p ≡ a (mod p)
- 米勒-拉宾素数判定法: 对于 n 和 k，如果 n 是合数，则存在一个 a 使得 (a^k) % n ≠ a^k，或存在 0 ≤ j ≤ k-1 使得 (a^(2^j * k)) % n ≠ a^(2^(j+1) * k) 或 n

5. 归并排序的时间复杂度公式- 时间复杂度: O(n log n)，其中 n 是数组大小

6. 快速排序的时间复杂度公式- 平均时间复杂度: O(n log n)
- 最坏情况时间复杂度: O(n^2)

7. 哈希函数公式- 模除法: h(key) = key % m，其中 m 是哈希表大小
- 乘法法: h(key) = ((a * key) % p) % m，其中 a 是随机常数，p 是大素数

8. 离散傅里叶变换公式- 系数: F[k] = Σ[n=0 to N-1] x[n] * e^(-2πi * k * n / N)
- 逆变换: x[n] = Σ[k=0 to N-1] F[k] * e^(2πi * k * n / N)

9. 线性回归公式- 直线方程: y = mx + b，其中 m 是斜率，b 是 y 轴截距
- 最小二乘法: m = Σ[(x[i] - x̄)(y[i] - ȳ)] / Σ[(x[i] - x̄)^2]

2024-11-27

上一篇：初学者计算机编程全面指南

下一篇：幼儿电脑编程：开启数字之旅的指南