时间性能
算法复杂性函数：
\[ f(n)=n^2 +1000n+\log_{10}n+1000 \]
当n的数据规模逐渐增大时，f(n)的增长趋势：

  • 当n增大到一定值以后，计算公式中影响最大的就是n的幂次级最高的项，并且其他的常数项和低幂次项都可以忽略，我们更关注的是它是一个什么量级的算法，是线性的还是n方的，还是指数级的。

大O表示法

  • 函数f、g定义域为自然数，值域为非负实数集
  • 定义：如果存在正数c和\(n_0\)，使得对任意的\[ n \geq n_0 \] 都有\[ f(n) \leq cg(n)。\]
  • 称f(n)在集合O(g(n))中，简称f(n)是O(g(n))的，或f(n)=O(g(n))。
  • 大O表示法：表达函数增长率上限
  • 一个函数增长率的上限可能不止一个
  • 大O表示法不关心小范围的（n较小）的特例。

大O表示法的单位时间

  • 一个简单的布尔或算数运算 - O(1)
  • 简单I/O
    • 指函数的输入/输出
      例如：从数组读取数据等操作
    • 不包括键盘文件等I/O
  • 函数返回

大O表示法的运算规则

  • 加法规则： \[f_1(n)+f_2(n)=O(max(f_1(n),f_2(n)))\]
    （ 最耗时的那一段。）
  • 乘法规则： \[ f_1(n)·f_2(n)=O(f_1(n)·f_2(n)) \]
    (适用于while、for等循环结构）
    • 顺序结构，if结构，swith结构 
    for(int i=0;i<n;i++)
  for(int j=0;j<n;j++)
     k++;
    嵌套循环中第一个和第二个for都是O(n)的时间复杂度，两者的乘积是：
    \[ \sum{n-1 \atop i=0}(n-i)=\frac{n(n-1)}{2}=O(n^2)\]

算法渐进分析：大\(\Omega\)表达式

  • 定义：如果存在正数c和\(n_0\)，使得对所有n\(\geq n_0\)，都有f(n)\(\geq\)cg(n)，
    则称f(n)在集合\(\Omega\)(g(n))中，或f(n)=\(\Omega\)(g(n))
  • 大O表示法和大\(\Omega\)表示法的唯一区别在于不等式的方向
  • 采用大\(\Omega\)表示法时，最好找出在函数增值率的所有下限中那个最“紧”（即最大）的下界

增长率大小比较：\[\log_2n \leq n \leq n \log_2n \leq n^2 \leq 2^n\]

算法复杂性分析
例：顺序寻找k值

  • 顺序从一个规模为n的一维数组中找出一个给定的k值
  • 最佳情况 O(1)
    • 数组的第一个元素就是k值
    • 只需要检查第一个元素
  • 最差情况 O(n)
    • 数组的最后一个才是k
    • 检查数组中所有的n个元素
  • 如果等概率分布 O(n)
    • k值出现在n个位置上的概率都是1/n
  • 概率不等
    • 出现在第一个位置的概率为1/2
    • 出现在第二个位置上的概率为1/4
      -出现在其他位置的概率都是$ \frac {1-1/2-1/4}{n-2} $