算法分析：复杂度、效率与对数的应用

### 算法分析：复杂度、效率与对数的应用 #### 1. 算法复杂度基础 在算法分析中，理解不同函数之间的主导关系至关重要。常见的主导关系如下： \[n! \gg 2^n \gg n^3 \gg n^2 \gg n \log n \gg n \gg \log n \gg 1\] 这表明，在实际应用中，虽然高级算法分析可能会出现一些深奥的函数，但少数几种时间复杂度就足以涵盖大多数广泛使用的算法。 #### 2. 大O符号的运算 在高中我们学习过代数表达式的简化，处理大O符号也需要运用这些知识，但并非所有规则都适用。 - **函数相加**：两个函数之和由主导函数决定，具体规则如下： - \(O(f(n)) + O(g(n)) \to O(\max(f(n), g(n)))\) - \(\Omega(f(n)) + \Omega(g(n)) \to \Omega(\max(f(n), g(n)))\) - \(\Theta(f(n)) + \Theta(g(n)) \to \Theta(\max(f(n), g(n)))\) 例如，\(n^3 + n^2 + n + 1 = O(n^3)\)，因为与主导项相比，其他项都微不足道。 - **函数相乘**： - 乘以一个正常数 \(c > 0\) 不会影响函数的渐近行为，即： - \(O(c \cdot f(n)) \to O(f(n))\) - \(\Omega(c \cdot f(n)) \to \Omega(f(n))\) - \(\Theta(c \cdot f(n)) \to \Theta(f(n))\) - 当两个递增函数相乘时，两者都很重要，一般规则为： - \(O(f(n)) * O(g(n)) \to O(f(n) * g(n))\) - \(\Omega(f(n)) * \Omega(g(n)) \to \Omega(f(n) * g(n))\) - \(\Theta(f(n)) * \Theta(g(n)) \to \Theta(f(n) * g(n))\) 下面通过一个表格总结大O符号的运算规则： | 运算类型 | 规则 | | ---- | ---- | | 函数相加 | \(O(f(n)) + O(g(n)) \to O(\max(f(n), g(n)))\) | | 函数相加 | \(\Omega(f(n)) + \Omega(g(n)) \to \Omega(\max(f(n), g(n)))\) | | 函数相加 | \(\Theta(f(n)) + \Theta(g(n)) \to \Theta(\max(f(n), g(n)))\) | | 乘以正常数 | \(O(c \cdot f(n)) \to O(f(n))\) | | 乘以正常数 | \(\Omega(c \cdot f(n)) \to \Omega(f(n))\) | | 乘以正常数 | \(\Theta(c \cdot f(n)) \to \Theta(f(n))\) | | 函数相乘 | \(O(f(n)) * O(g(n)) \to O(f(n) * g(n))\) | | 函数相乘 | \(\Omega(f(n)) * \Omega(g(n)) \to \Omega(f(n) * g(n))\) | | 函数相乘 | \(\Theta(f(n)) * \Theta(g(n)) \to \Theta(f(n) * g(n))\) | 此外，大O关系具有传递性。若 \(f(n) = O(g(n))\) 且 \(g(n) = O(h(n))\)，则 \(f(n) = O(h(n))\)。证明如下： 已知 \(f(n) \leq c_1g(n)\)（\(n > n_1\)），\(g(n) \leq c_2h(n)\)（\(n > n_2\)），则 \(f(n) \leq c_1g(n) \leq c_1c_2h(n)\)（\(n > n_3 = \max(n_1, n_2)\)）。 #### 3. 算法效率分析示例 下面通过几个具体的算法来分析其效率。 - **选择排序**：选择排序算法会反复找出剩余未排序元素中的最小元素，并将其放置在已排序部分的末尾。代码如下： ```c selection_sort(int s[], int n) { int i,j; /* counters */ int min; /* index of minimum */ for (i=0; i<n; i++) { min=i; for (j=i+1; j<n; j++) if (s[j] < s[min]) min=j; swap(&s[i],&s[min]); } } ``` 外层循环执行 \(n\) 次，内层循环执行 \(n - i - 1\) 次。\(if\) 语句执行的总次数为： \[S(n) = \sum_{i=0}^{n-1} \sum