calendar_month  schedule  web_traffic 加载中...   edit_square149 字  timer1 分钟 
🤖 AI文章摘要 qwen-turbo-latest
加载中...
此内容根据文章生成，并经过人工审核，仅用于文章内容的解释与总结 投诉

算法简介

数据元素之间的关系有逻辑关系和物理关系，对应的运算有基于逻辑结构的运算定义和基于存储结构的运算定义，通常把基于存储结构的运算实现步骤称为算法。

  • 算法的特点: 具有输入、输出、有穷性、可行性。
  • 算法的构成: 一个算法由控制结构(顺序、分支、循环)和原操作构成(加减乘除)。

算法分析

渐进分析(Asymptotic Analysis)

渐进分析是用于分析算法的一个伟大构想，我们通过算法随问题规模(n)的增长时资源消耗的增长趋势来评估算法的性能。当我们假设计算机执行每步命令所消耗的时间时相同时，算法的资源消耗满足某个函数$f(n)$，随着问题规模的增长，资源消耗增长越慢的算法在处理大量输入时相对占优。工程上使用一系列$g(n)$函数组成的函数簇来描述算法的$f(n)$的趋势以及边界，常用的是上界函数簇$O(g(n))$、下界函数簇$\Omega(g(n))$以及上下界的函数簇交集$\Theta(f(n))$，它们分别描述最坏情况、最好情况和平均情况的算法资源消耗。

  • 上界函数簇:$O$: $f(n)=O(g(n))$ 或 $f(n)\in O(g(n))$意味着存在常数$(c>0, n_{0}>0)$ ,对于所有的$n>n_{0}$，满足 $0\leq f(n) \leq c*g(n)$。
  • 下界函数簇: $\Omega$ : $f(n)=\Omega(g(n))$ 或 $f(n)\in \Omega(g(n))$ 意味着存在常数$(c>0, n_{0}>0)$ ,对于所有的$n>n_{0}$, 满足$0\leq c*g(n) \leq f(n)$。
  • 上下界函数簇交集: $\Theta(f(n))=\Omega(g(n))\cap O(g(n))$。

循环的时间复杂性分析(Loop Analysis)

循环的复杂性取决于问题规模(n)，从问题规模(n)中计算出循环执行次数。

  • 算术、访问内存等操作算作一次执行。
  • 可以使用公式或级数等数学方面的知识获取复杂度表达式。
  • 常数次数执行次数的函数或表达式集合为常数时间复杂度$O(1)$。
  • 循环常量在迭代的过程中被乘以或除以某个常数时为对数时间复杂度$O(logn)$。
  • 循环常量在迭代的过程中被指数级增加或减少时为对数时间复杂度$O(loglogn)$。
  • 有分支条件考虑循环可能执行的最长代码量，若分支数量庞大考虑忽略分支条件。
  • 连续循环、嵌套循环的时间复杂度可以求解单个循环复杂度后相加，单个循环时间复杂度为每次迭代的工作量乘以迭代次数。

递归的时间复杂性分析(Recursive Analysis)

替代法(Substitution Method)

对于替代法，我们猜测一个答案作为命题，运用数学归纳法证明命题为真。例如对于以下递推式，我们推测时间复杂度为$T(n)=O(n^3)$，并使用数学归纳法进行证明：

$ T(n)=4T(\frac{n}{2})+n $

解:
证明$T(n)=O(n^3)$，根据上界定义即证明存在非0自然数$(c, n_0)$满足$T(n) \le cn^3$.
1.$n_{0}$取合适值时，对于$n<n_{0}$，$T(n)=\Theta(1)$成立。
对于$1<n<n_{0}$，只要我们对c取足够大的数， $\Theta(1) < cn^3$成立
2.假设对于定义域$[1,n)$上，$T(n) \le cn^3$成立
对于$\frac{n}{2}(<n)$，我们有$T(\frac{n}{2}) \le c(\frac{n}{2})^3$
$T(n)=4T(\frac{n}{2})+n$
$T(n) \le 4c(\frac{n}{2})^3+n$
$T(n) \le cn^3 - (\frac{c}{2}n^3-n)$
对于$c \ge 2, n \ge 1$，$(\frac{c}{2}n^3-n) > 0$ 至此完成递推归纳。

实际上以上证明了$T(n)=O(n^3)$，$T(n)$更紧凑的上界应该是$T(n)=O(n^2)$，留作以后练习。

递归树法(Recursion-Tree Method)

todo

主定理法(Master Method)

主定理法针对以下形式的递归或可以转换为以下形式的递归直接给出解决方案。主定理法是通过递归树法中总结而来的结论。

$T(n)=aT(\frac{n}{b})+f(n) ,a\geq 1,b > 1$当n足够大时$f(n)>0$

  • 若$f(n)=O(n^{\log_{b}a-\varepsilon})$，其中$\varepsilon > 0$且$f(n)$增长趋势比$n^{\log_{b}a}$慢，则$T(n)=\Theta(n^{\log_{b}a})$
  • 若$f(n)=\Theta(n^{\log_{b}a}\lg^{\varepsilon}n)，$其中$\varepsilon > 0$且$f(n)$增长趋势与$n^{\log_{b}a}$相似，则$T(n)=\Theta(n^{\log_{b}a}\lg^{\varepsilon+1}n)$
  • 若$f(n)=\Omega(n^{\log_{b}a+\varepsilon})$，其中$\varepsilon > 0$且$f(n)$增长趋势比$n^{\log_{b}a}$快，则$T(n)=\Theta(f(n))$

例1：$T(n)=4T(\frac{n}{2})+n$

解:
$f(n)=n$，$n^{log_a^b}=n^2$
$f(n)=O(n^{2-\varepsilon})_{\varepsilon=1}$， 所以$T(n)=\Theta(n^2)$。

例2：$T(n)=4T(\frac{n}{2})+n^{2}$。

解:
$f(n)=n^{2}$，$n^{log_a^b}=n^2$
$f(n)=\Theta(n^{2}lg^{\varepsilon}n)_{\varepsilon=0}$， 所以$T(n)=\Theta(n^2lgn)$。

例3：$T(n)=4T(\frac{n}{2})+n^{3}$

解:
$f(n)=n^{3}$，$n^{log_a^b}=n^2$
$f(n)=\Omega(n^{2+\varepsilon})_{\varepsilon=1}$， 所以$T(n)=\Theta(n^3)$。

平摊分析(Amortized Analysis)

todo

算法设计

todo

算法目录

todo