计算机编程常用公式大全

计算机编程中常用的公式涵盖了许多领域，包括数学、算法分析、数据结构等。以下是一些常见的公式和概念：

1. 算法复杂度

- 时间复杂度：衡量算法运行时间随输入规模增长的关系。

- 常见复杂度：O(1), O(log n), O(n), O(n log n), O(n^2)

- 空间复杂度：衡量算法在运行过程中所需要的内存空间。

2. 数学基础

- 概率公式：

- $P(A \cup B) = P(A) + P(B) - P(A \cap B)$

- $P(A|B) = \frac{P(A \cap B)}{P(B)}$

- 排列与组合：

- 排列：$P(n, k) = \frac{n!}{(n-k)!}$

- 组合：$C(n, k) = \frac{n!}{k!(n-k)!}$

- 对数公式：

- $\log_b(a) = \frac{\log_k(a)}{\log_k(b)}$

- $\log_b(xy) = \log_b(x) + \log_b(y)$

- 指数公式：

- $a^m \times a^n = a^{m+n}$

- $(a^m)^n = a^{m \times n}$

3. 数据结构

- 数组：顺序存储元素，访问时间复杂度为O(1)

- 链表：节点包含数据和指向下一个节点的指针，访问时间复杂度为O(n)

- 栈和队列：FILO和FIFO结构，入栈/出栈和入队/出队时间复杂度为O(1)

- 树和图：二叉树、红黑树、DAG等，用于表示层级关系和网络结构

4. 递归关系

- 斐波那契数列：

- $F(n) = F(n-1) + F(n-2)$，初始条件：$F(0) = 0, F(1) = 1$

5. 排序算法

- 快速排序：时间复杂度$O(n \log n)$，最坏情况$O(n^2)$

- 归并排序：时间复杂度$O(n \log n)$，空间复杂度O(n)

6. 搜索算法

- 二分查找：时间复杂度$O(\log n)$，适用于有序数组

- 深度优先搜索（DFS）和广度优先搜索（BFS）：用于遍历和搜索图结构

7. 位运算

- 左移：x << n，相当于$x \times 2^n$

- 右移：x >> n，相当于$x \div 2^n$

8. 网络与通信

- 带宽计算：带宽 = 数据量 / 时间

- 延迟：用来表示数据传输所需的时间

这些公式和概念是编程过程中常用的基本工具，深入理解它们可以帮助解决复杂的编程问题。