算法与数据结构的复杂度分析及其求极值问题

Complexity And Finding Peaks

• 渐近表示法(Asymptotic Notation)

  • Big-O(Big O)

  • • Big O定义

  • 算法分析的整体框架

  • 寻找峰值 (Peak Finding)

  • • 线性查找
    • 二分查找

  • 参考文献

渐近表示法(Asymptotic Notation)

如何依据算法复杂度的递进关系对其进行评估与排列?
以下列举了三种常见用于衡量复杂性的标准排序方式:

1. 大O符号
2. 大Ω符号
3. 大Θ符号
   相较于大Ω与大Θ，大O符号在实际应用中更为普遍且被广泛采纳。

Big-O(Big O)

我们借助Big O符号，将某一函数的运行时间增长趋势在渐近意义上约束于一个固定比例范围内，从而使得另一函数的增长速率被抑制或保持在同一数量级。
Big O（上界）主要关联于算法在最坏情况下的表现特征。

Big O定义解析

算法分析的总体规划

1. 参数n用