大O表示法用于描述算法的时间复杂度或空间复杂度。大O是一种表达算法时间或空间复杂度上界的方式。
- 描述函数的渐近行为（即时间或空间相对于输入规模的增长率），而不是其具体数值。
- 可用于比较不同算法或数据结构的效率。
- 它提供了算法在输入规模维度上的时间上限。为了用大O表示法找到时间复杂度，我们主要考虑算法的最坏情况。
大O的定义
给定两个函数 f(n) 和 g(n)，如果存在常数 c > 0 和 n0 >= 0，使得对于所有 n >= n0，都有 f(n) <= c*g(n)，那么我们说 f(n) 是 O(g(n))。
简而言之，如果 f(n) 的增长速度不超过 c*g(n)（对于所有 n >= n0，其中 c 和 n0 是常数），那么 f(n) 就是 O(g(n))。
快速求解表达式大O值的方法
- 忽略低阶项，仅保留最高阶项。
- 忽略最高阶项相关联的常数。
> 示例 1: f(n) = 3n2 + 2n + 1000Logn + 5000
> 忽略低阶项后，我们得到的最高阶项是 3n2
> 忽略常数 3 后，我们得到 n2
> 因此，该表达式的大O值为 O(n2)
>
> 示例 2 : f(n) = 3n3 + 2n2 + 5n + 1
> 主导项: 3n3
> 增长阶数: 立方 (n3)
> 大O表示法: O(n3)
大O表示法的性质
以下是大O表示法的一些重要性质：
1. 自反性
对于任何函数 f(n)，f(n) = O(f(n))。
示例：
> f(n) = n2, 则 f(n) = O(n2)。
2. 传递性
如果 f(n) = O(g(n)) 且 g(n) = O(h(n))，那么 f(n) = O(h(n))。
示例：
> 如果 f(n) = n^2, g(n) = n^3, 且 h(n) = n^4, 那么 f(n) = O(g(n)) 且 g(n) = O(h(n))。
> 因此，根据传递性，f(n) = O(h(n))。
3. 常数因子
对于任何常数 c > 0 以及函数 f(n) 和 g(n)，如果 f(n) = O(g(n))，那么 cf(n) = O(g(n))。
示例：
> f(n) = n, g(n) = n2。那么 f(n) = O(g(n))。因此，2f(n) = O(g(n))。
4. 求和法则
如果 f(n) = O(g(n)) 且 h(n) = O(k(n))，那么 f(n) + h(n) = O(max( g(n), k(n) )。当结合复杂度时，只有最大的项起主导作用。
示例：
> f(n) = n2, h(n) = n3。那么，f(n) + h(n) = O(max(n2 + n3) = O ( n3)
5. 乘积法则
如果 f(n) = O(g(n)) 且 h(n) = O(k(n))，那么 f(n) h(n) = O(g(n) k(n))。
示例：
> f(n) = n, g(n) = n2, h(n) = n3, k(n) = n4。那么 f(n) = O(g(n)) 且 h(n) = O(k(n))。因此，f(n) h(n) = O(g(n) k(n)) = O(n6)。
6. 复合法则
如果 f(n) = O(g(n))，那么 f(h(n)) = O(g(h(n)))。
示例：
> 如果 f(n) = n^2, g(n) = n^3 且 h(n) = log n, 那么根据复合法则 f(h(n))=O(g(h(n)))。因此，(log n)^2=O((log n)^3)。
常见的大O表示法
大O表示法是衡量算法时间和空间复杂度的一种方式。它描述了最坏情况下的复杂度上界。让我们深入了解不同类型的时间复杂度：
1. 线性时间复杂度：大O(n) 复杂度
线性时间复杂度意味着算法的运行时间与输入规模呈线性增长。
例如，考虑一个遍历数组以查找特定元素的算法：
代码片段
CODEBLOCK_30b119f2
2. 对数时间复杂度：大O(log n) 复杂度
对数时间复杂度意味着算法的运行时间与输入规模的对数成正比。
例如，二分查找算法具有对数时间复杂度：
代码片段
CODEBLOCK_53cc08b8
3. 平方时间复杂度：大O(n2) 复杂度
平方时间复杂度意味着算法的运行时间与输入规模的平方成正比。
例如，一个简单的冒泡排序算法具有平方时间复杂度：
代码片段
void bubbleSort(int ar