算法 - 数学基础和时间复杂度

发表于 | 分类于 | 阅读次数

算法相关的数学基础，以及时间复杂度的计算方式。

数学基础

指数 Exponent

指数是幂运算 aⁿ(a≠0) 中的一个参数，a 为底数，n 为指数，指数位于底数的右上角，幂运算表示指数个底数相乘。

0085-exponent.png

0085-exponent-function.png

对数 Logarithm

对数是对求幂的逆运算，用于求解出幂运算中的指数。

在计算机科学中，除非有特别声明，所有的对数都是以 2 为底的，比如 logN 是标准写法。有些计算机相关书籍中提到的 lgN 也是以 2 为底的（这点需要特别注意，并不是数学中的以 10 为底）。

0085-logarithm.png

0085-logarithm-function.png

  • 如果 a(a>0，a≠1) 的 b 次幂等于 N，即 aᵇ=N，那么数 b 叫做以 a 为底 N 的对数，记作：logₐN=b，其中 a 叫做对数的底数，N 叫做真数
  • 以 10 为底的对数叫常用对数，记作 log10N，简记为 lgN
  • 以无理数 e(e=2.718 28…) 为底的对数叫做自然对数，记作 logₑN，简记为 lnN

级数 Series

0085-geometric-progression.png

0085-arithmetic-progression.png

0085-series-1.png

0085-series-2.png

0085-series-3.png

模运算

如果 N 整除 A - B，那么我们就说 A 与 B 模 N 同余 congruent，记为 A≡B(mod N)。直观地看，这意味着无论 A 还是 B 被 N 去除，所得余数都是相同的。于是：81≡61≡1(mod 10)。如同等号的情形一样，若 A≡B(mod N)，则 A+C ≡ B+C(mod N) 以及 AD≡BD(mod N) 。

证明方法

数学归纳法 Mathematical induction

归纳法证明有两个标准部分：

  • 基准情形 base case
    确定定理对于某个小的值的正确性，这一步通常很简单，只需要验证最小值是否满足定理。
  • 归纳假设 inductive hypothesis
    假设定理对直到某个有限数 k 的所有情况都是成立的，然后使用这个假设证明：定理对下一个值 k+1 也是成立的。

0085-mathematical-induction.png

反证法 Reductio ad absurdum

反证法证明是通过假设定理不成立，然后证明该假设导致某个已知的性质不成立，从而证明原假设是错误的。

![0085-reductio-ad- absurdum.png](https://raw.githubusercontent.com/redspider110/blog-images/master/_images/0085-reductio-ad- absurdum.png)

递归

递归的四条基本法则：

  • 基准情形 base case
    必须要有某些基准情形，它们不需要递归就能求解。
  • 不断推进 making progress
    对于那些需要递归求解的情形，递归调用必须能够朝着产生基准情形的方向推进。
  • 设计法则 design rule
    假设所有的递归调用都能运行。
  • 合成效益法则 compound interest rule
    在求解一个问题的同一个实例时，切勿在不同的递归调用中做重复性的工作。

通常使用数学归纳法来梳理递归的思路。

递归就是方法中调用自己，我们换个思路来理解递归，包含三要素：

  • 递归总有一个最简单的情况。也就是说方法的第一条语句通常是 return 的条件语句
  • 递归总是去尝试一个规模更小的子问题，这样递归才能收敛到最简单的情况
  • 递归调用的父问题和尝试解决的子问题不应该有交集

不等式

四个常见定义

  • 如果存在正常数 c 和 n0 使得当 N≥n0 时 T(N)≤cf(N)，则记为 T(N)=Ο(f(N))
  • 如果存在正常数 c 和 n0 使得当 N≥n0 时 T(N)≥cg(N)，则记为 T(N)=Ω(g(N))
  • T(N)=Θ(h(N)) 当且仅当 T(N)=Ο(h(N)) 且 T(N)=Ω(h(N))
  • 如果 T(N)=Ο(p(N)) 且 T(N)≠Θ(p(N))，则 T(N)=ο(p(N))

ΟΩΘο 的读音和意义

这四个记号表示的是比较它们的相对增长率 relative rate of growth 。

  • Ο
    读作 大O；表示 T(N) 的增长率小于等于 f(N) 的增长率。即最大增长率为 f(N) ，f(N) 是 T(N) 的上界。
  • Ω
    读作 omega:[oʊˈmegə]，欧米伽；表示 T(N) 的增长率大于等于 g(N) 的增长率。即最小增长率为 g(N) ，g(N) 是 T(N) 的下界。
  • Θ
    读作 theta[ˈθetə, ˈθi-] ；表示 T(N) 和 h(N) 的增长率相等。
  • ο
    读作 小ο ；表示 T(N) 的增长率小于 p(N) 的增长率。它不同于 大O，因为 Ο 包含增长率相同的可能性。

ΟΩΘο 统称：渐进符号 Asymptotically notation，在离散数学有详细的介绍，核心是极限的概念。

重要结论

为了证明某个函数 T(N)=Ο(f(N)) ，通常不是形式的使用定义，而是使用一些已知结果。也就是锁证明是非常简单的，并不涉及到微积分相关。

0085-expression.png

  • 如果 T1(N)=O(f(N)) 且 T2(N)=O(g(N))，那么： 

    1
    2
    T1(N) + T2(N) = max(O(f(N)), O(g(N)))
    T1(N) * T2(N) = O(f(N) * g(N))

  • 如果 T(N) 是一个 k 次多项式，则 T(N)=Θ(Nᵏ)

  • 对任意常数 k，logᵏN=O(N)，它告诉我们对数增长得非常缓慢。

注意事项

  • 关于 大O
    将常数或低阶项放进 大O 是非常坏的习惯。通常在需要 大O 的任何分析中，需要各种简化：低阶项可以被忽略，常数可以舍弃。此时，要求精度很低。
  • 极限
    0085-lim.png

常见函数增长率

  • 常见函数
    0085-table-function.png

  • 数学特征函数图
    0085-Comparison_computational_complexity.png

  • y 轴为时间图
    0085-elements-operations.png

时间复杂度

时间复杂度 Time Complexity：主要关心算法的平均运行时间和最坏情况下的运行时间。
D.E.Knuth 认为一个程序运行的总时间主要和两点有关：

  • 执行每条语句的耗时
  • 执行每条语句的频率

每条语句的耗时和操作系统、计算机硬件等都高度相关；所以算法关注的时间复杂度主要是计算执行频率。

示例

0085-time-complexity-samples.png

时间计算一般法则

  • 法则 1：FOR 循环
    一次 for 循环的运行时间至多是该 for 循环内语句的运行时间乘以迭代次数。通常为 O(N)。

  • 法则 2：嵌套的 FOR 循环
    从里到外分析这些循环，在一组嵌套循环内部的一条语句总的运行时间为该语句的运行时间乘以该组所有的 for 循环的大小的乘积。如下面程序为 O(N²) 。 

    1
    2
    3
    for(i=0; i<N; i++)
      for(j=0; j<N; j++)
        k++;

  • 法则 3：顺序语句
    将各个语句的运行时间求和，即其中的最大值就是最终的运行时间。
    第一个 for 循环花费为 O(N)，第二个 for 循环花费为 O(N²)，最终总的开销为最大值 O(N²) 。 

    1
    2
    3
    4
    5
    for(i=0; i<N; i++)
      A[i] = 0;
    for(i=0; i<N; i++)
      for(j=0; j<N; j++)
        A[i] += A[j] + i + j;

  • 法则 4：IF/ELSE 语句
    一个 if/else 语句的运行时间，不超过判断再加上 max(S1, S2) 的总运行时间。 

    1
    2
    3
    4
    if(condition)
      S1;
    else
      S2;

对数

分析算法时间复杂度最混乱的方面大概集中在对数上面。对数最长出现的规律概括为：

  • 如果一个算法用常数时间 O(1) 将问题的大小消减为其一部分（通常为一半 1/2），那么该算法就是 O(logN)。也就是说，通常的二分法或者对半分治等算法。
  • 如果使用常数时间只是将问题减少一个常数（如将问题减少 1），那么该算法就是 O(N)

常见时间复杂度

0085-common-time-complexity.png

典型示例

递归转换为 for 循环

0085-recursion-sample-time-complexity.png

最大子序列和的估算与精算

0085-max-sequence.png

例如：输入整数序列：-2, 11, 8, -4, -1, 16, 5, 0，则输出答案为 35，即从 A2～A6 。
根据求和公式，很容易写出代码（简单的扩展求和公式）。 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
int MaxSubsequenceSum(const int A[], int N)
{
    int ThisSum, MaxSum, i, j, k;
    MaxSum = 0;
    for(i=0; i<N; i++)
        for(j=i; j<N; j++)
        {
            ThisSum = 0;
            for(k=i; k<=j; k++)
                ThisSum += A[k];
            
            if(ThisSum > MaxSum)
                MaxSum = ThisSum;
        }
    return MaxSum;
}
  • 估算
    上述算法由三重嵌套 for 循环语句组成，根据法则 2，估算出时间复杂度为 O(N³) 。
  • 精确计算
    精确计算出来的时间复杂度仍然是 O(N³)，所以通常只需要估算，精确的计算往往涉及到复杂的数学运算。
    0085-time-complexity-calculator.png

其他数学知识

数论基础

  • 约数和倍数
    整数 a 除以整数 b(b≠0)，除得的商正好是整数而没有余数，我们就说 a 能被 b 整除，或 b 能整除 a。
    a 称为 b 的倍数，b 称为 a 的约数，约数也称为因数。
  • 最大公约数
    gcd: greatest common divisor，也称最大公因数、最大公因子：指两个或多个整数共有约数中最大的一个。
    欧几里得算法：两个整数的最大公约数等于其中较小的那个数和两数相除余数的最大公约数。
    gcd(a,b) = gcd(b,a mod b) (不妨设a>b 且r=a mod b ,r不为0)
  • 最小公倍数
    lcm: least common multiple，两个或多个整数公有的倍数叫做它们的公倍数，除 0 以外最小的一个公倍数就叫做这几个整数的最小公倍数。
  • 质数和合数
    质数 prime number 又称素数，有无限个。质数：在大于 1 的自然数中，除了 1 和它本身以外不再有其他因数；否则称为合数。
    判断方法：对正整数 n，如果用 2 到 n 的根号之间的所有整数去除，均无法整除，则 n 为质数。

矩阵乘方

只有在第一个矩阵的列数 column 和第二个矩阵的行数 row 相同时才有意义。
设 A 为 m × p 的矩阵，B 为 p × n 的矩阵，那么称 m × n 的矩阵 C 为矩阵 A 与 B 的乘积，记作 C=AB，其中矩阵 C 中的第 i 行第 j 列元素可以表示为：

0085-array-product-a-b.png

示例：

0085-array-product-sample.png

后续

参考文档

0%