DSA - 渐近分析(Asymptotic Analysis)
算法的渐近分析是指定义其运行时性能的数学边界/框架。 使用渐近分析，我们可以很好地得出算法的最佳情况，平均情况和最坏情况。
渐近分析是输入约束，即，如果算法没有输入，则结论是在恒定时间内工作。 除了“输入”之外，所有其他因素都被认为是不变的。
渐近分析是指以数学计算单位计算任何操作的运行时间。 例如，一个操作的运行时间计算为f （n），并且可以用于另一个操作，其计算为g （n 2 ）。 这意味着第一操作运行时间将随着n的增加而线性增加，并且当n增加时第二操作的运行时间将指数地增加。 类似地，如果n非常小，则两个操作的运行时间几乎相同。
通常，算法所需的时间分为三种类型 -
Best Case - 程序执行所需的最短时间。
Average Case - 程序执行所需的平均时间。
Worst Case - 程序执行所需的Worst Case长时间。
渐近符号
以下是计算算法运行时间复杂度的常用渐近符号。
- Ο符号
- Ω表示法
- θ表示法
大哦符号，Ο
符号Ο（n）是表示算法运行时间上限的正式方式。 它测量最坏情况下的时间复杂度或算法可能需要完成的最长时间。
例如，对于函数f (n)
Ο(<i>f</i>(n)) = { <i>g</i>(n) : there exists c > 0 and n<sub>0</sub> such that <i>f</i>(n) ≤ c.<i>g</i>(n) for all n > n<sub>0</sub>. }
Omega表示法，Ω
符号Ω（n）是表示算法运行时间下限的正式方式。 它测量最佳案例时间复杂度或算法可能需要完成的最佳时间量。
例如，对于函数f (n)
Ω(<i>f</i>(n)) ≥ { <i>g</i>(n) : there exists c > 0 and n<sub>0</sub> such that <i>g</i>(n) ≤ c.<i>f</i>(n) for all n > n<sub>0</sub>. }
Theta Notation，θ
符号θ（n）是表示算法运行时间的下限和上限的形式方式。 它表示如下 -
θ(<i>f</i>(n)) = { <i>g</i>(n) if and only if <i>g</i>(n) = Ο(<i>f</i>(n)) and <i>g</i>(n) = Ω(<i>f</i>(n)) for all n > n<sub>0</sub>. }
常见的渐近符号
以下列出了一些常见的渐近符号 -
| constant | − | Ο(1) |
| logarithmic | − | Ο（log n） |
| linear | − | Ο(n) |
| n log n | − | Ο（n log n） |
| quadratic | − | Ο(n 2 ) |
| cubic | − | Ο(n 3 ) |
| polynomial | − | n Ο(1) |
| exponential | − | 2 Ο(n) |
