1.3 算法和算法分析
<strong>大O记号</strong>
重要程度：9 分
<div>
<h2>大O记号</h2>
<p><strong>定义：</strong> 大O记号是一种用于描述算法时间复杂度或空间复杂度上界的方法。它用来表示当输入规模趋向于无穷大时，算法运行时间和输入数据量之间增长关系的一个上限估计。</p>
<p>如果存在正常数 \(c\) 和 \(n_0\)，使得对于所有 \(n \geq n_0\) 都有 \(T(n) \leq c\cdot f(n)\)，则我们说 \(T(n) = O(f(n))\)。这里\(T(n)\)是实际的时间函数（或空间函数），而\(f(n)\)则是其渐近的上界。</p>
<h3>重要性质:</h3>
<ul>
<li>如果\(T(n) = a_m n^m + a_{m-1} n^{m-1} + ... + a_1 n + a_0\) 是一个多项式，则 \(T(n) = O(n^m)\)。</li>
<li>\(O(c\cdot f(n)) = O(f(n))\)，其中\(c > 0\)是一个常数。</li>
<li>\(O(f(n)) + O(g(n)) = O(\max\{f(n), g(n)\})\)。</li>
<li>\(O(f(n)) \cdot O(g(n)) = O(f(n) \cdot g(n))\)。</li>
</ul>
<h3>例子说明:</h3>
<p><strong>例题 1:</strong> 考虑以下简单循环：</p>
<pre>
for (int i = 0; i < n; i++) {
// 执行某些操作
}
</pre>
<p>此段代码的时间复杂度为 \(O(n)\)，因为随着\(n\)的增长，循环次数线性增加。</p>
<p><strong>例题 2:</strong> 对于嵌套循环：</p>
<pre>
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
// 执行某些操作
}
}
</pre>
<p>这段代码的时间复杂度为 \(O(n^2)\)，因为它包含了两个级别的迭代，每个级别都与\(n\)成正比。</p>
<h3>证明:</h3>
<p>以例题2为例来证明为什么其时间复杂度为\(O(n^2)\): 假设内层循环中的操作耗时为常数时间\(k\)。那么外层每执行一次，内层总共会执行\(n\)次。因此，整个过程将需要\(n * n * k = kn^2\)单位时间。根据大O记号的定义，我们可以忽略常数因子\(k\)，从而得出该程序的时间复杂度为\(O(n^2)\)。</p>
</div>