引入

  • 引入

    1、算法竞赛是思维脑力的较量。一道好的算法题可以区分出好的算法程序(可以获得较高得分)和不那么好的算法程序(低分甚至零分)
    2、评价算法的优劣是有一套标准的。利用这套标准，可以在动手实践之前即可估计这种写法是否靠谱
    3、如果判断这套算法可能超时或超出内存限制而导致无法得分，则应该想想有没有更好的写法
    4、接下来便来学习如何评价一套算法

如何评价算法

  • 代码可实现

    1、按照编程者的能力可以将算法通过代码实现出来
    2、如果想出算法但无法实现，或者需要花费非常多的时间和行数(甚至超出比赛时间)才能编写，显然是不行的

  • 结果正确

    1、程序能够运行完毕，不会在运行过程中出错崩溃
    2、输出的结果必须符合期望，通过测试点

  • 能在限定时间内运行完毕

    1、在结果正确的前提下，运行时间越短越好
    2、对于一些数据量较大的题目，需要尽力优化程序的运行时间，否则会因为超时而无法通过测试点

  • 不超过内存等资源限制

    1、计算机的内存是有限的，所以使用过多的内存也是不行的
    2、竞赛通常也会额外限制内存，因此需注意不要超出内存限制

时间复杂度

  • 定义

    1、一个语句的频度是指该语句在算法中被重复执行的次数
    2、算法中所有语句的频度之和记为 T(n)，它是该算法问题规模 n的函数，时间复杂度主要分析 T(n)的数量级
    3、算法中基本运算的频度(即最深层循环内的语句的频度)与 T(n)同数量级，因此通常采用算法中基本运算的频度f(n)来分析算法的时间复杂度
    4、因此算法的时间复杂度记为 T(n) = O(f(n))
    5、含义上简单概括为算法的执行时间与输入值(问题规模)之间的关系

  • 分类

    1、最坏时间复杂度：指在最坏情况下，算法的时间复杂度
    2、平均时间复杂度：指所有可能输入实例在等概率出现的情况下，算法的期望运行时间
    3、最好时间复杂度：指在最好情况下，算法的时间复杂度

  • 规则

    1、加法规则：T(n) = T1(n) + T2(n) = O(f(n)) + O(g(n)) = O(max(f(n),g(n)))；多项相加，只保留最高阶的项，且系数变为 1(如 O(n2) + O(n3) = O(n3))
    2、乘法规则：T(n) = T1(n) * T2(n) = O(f(n)) * O(g(n)) = O(f(n)*g(n))；多项相乘，都保留
    3、常见的渐进时间复杂度：O(1) < O(log2n) < O(n) < O(n*log2n) < O(n2) < O(n3) < O(2n) < O(n!) < O(nn)；口诀：常对线幂指阶

  • 含义理解

    1、O(1)是最低的时间复杂度，也就是耗时与输入数据大小无关，无论 n 为几，运行步骤都是一样的
    2、O(log2n)，当数据增大 n 倍时，耗时增大 log2n 倍。如数据增大 256 倍，耗时只增加 8 倍，如二分查找算法
    3、O(n)，就代表数据量增大几倍，耗时也增大几倍
    4、以此类推

  • 例题 1

    • 程序

      void fun(int n)
{
    int i = 1;
    while (i <= n)
        i = i * 2;
}

    • 解题步骤

      • 找出基本运算：i = i * 2

      • 设出执行时间：t

      • 分析关系

        t i
        1 2
        2 4
        3 8
        t 2t

      • 因为while()执行i<=n次，即执行 2t<=n 次，t<=log2n，T(n) = O(log2n)

  • 例题 2

    • 程序

      int x = 2;
while (x < n / 2)
    x = 2 * x;

    • 解题步骤

      • 找出基本运算：x = 2 * x

      • 设出执行时间：t

      • 分析关系

        t x
        1 4
        2 8
        3 16
        t 2t+1

      • 因为while()执行x<=n/2次，即执行 2t+1<=n/2 次，t+1<=log2(n/2)，t<log2n - 2，根据加法规则 T(n) = O(log2n)

  • 例题 3

    • 程序

      int fact(int n)
{
    if (n <= 1)
        return 1;
    return n * fact(n - 1);
}

    • 解题步骤

      • if()为递归出口，始终执行一次，即为常数级 O(1)

      • 调用递归的return中，n 始终执行同样的乘法操作，所以为 O(1)；由于问题规模 n 的函数与 T(n)挂钩，因此当问题规模变为 n-1 时，则应为 T(n-1)

      • 此时分类讨论：当 n<=1 时，T(n) = O(1)；当 n>1 时，T(n) = O(1) + T(n-1)

      • 讨论 n>1 的时候，假设 n 无限大。T(n) = O(1) + T(n-1)；此时 T(n-1)继续调用，T(n) = O(1) + O(1) + T(n-2) = 2*O(1) + T(n-2)；再次调用，T(n) = 3*O(1) + T(n-3)

      • 此时出现规律，假设 O(1)前面的系数为 i，则 T(n) = i*O(1) + T(n-i)；我们的目的是要消去 T(n-i)这项，所以要将它化为 T(1)，即令 i=n-1，此时原式 = (n-1)*O(1) + T(1)

      • 得出 T(n) = (n-1)*O(1) + T(1)，常数级都可以忽略不计，根据加法规则，(n-1)的 -1 也可以去除，所以最终 T(n) = O(n)

  • 例题 4

    • 程序

      int count = 0;
for (int k = 1; k <= n; k *= 2)
    for (int j = 1; j <= n; j++)
        count++;

    • 解题步骤

      • 找出基本运算：count++

      • 设出执行时间：t

      • 易得内层循环次数为 n，设外层循环次数为 q

      • 分析关系

        q k
        1 2
        2 4
        3 8
        q 2q

      • 因为k<=n，所以 2q<=n，q<=log2n

      • 外层循环循环一次，内层循环循环 n 次，那么外层 log2n 次，内层则应为 n*log2n 次

      • 所以最终 T(n) = O(n*log2n)

  • 例题 5

    • 程序

      int func(int n)
{
    int i = 0, sum = 0;
    while (sum < n)
        sum += ++i;
    return i;
}

    • 解题步骤

      • 找出基本运算：sum += ++i

      • 设出执行时间：t

      • 分析关系

        t sum
        1 0+1
        2 1+2
        3 1+2+3
        4 1+2+3+4
        t 1+2+3+…+t

      • 因为sum < n，所以1+2+3+...+t < n，等差数列 t(t+1) / 2 < n，化为 t(t+1) < 2n，可以忽略常数项，即 t2 < n，则 t < √(n)

      • 因此最终 T(n) = O(n1/2)

  • 例题 6

    • 程序

      for (int i = n - 1; i > 1; i--)
    for (int j = 1; j < i; j++)
        if (a[j] > a[j + 1])
            // (省略代码)a[j]与a[j+1]对调

    • 解题步骤

      • 找出基本运算：a[j]与a[j+1]对调

      • 设出执行时间：t

      • 易得外层循环次数为 n，设内层循环次数为 q

      • 分析关系

        i q t
        n-1 n-1 (n-1)*(n-1)
        n-2 n-2 (n-2)*(n-2)
        n-3 n-3 (n-3)*(n-3)

      • 易得 T(n) = O(n2)

  • 例题 7

    • 程序

      int x = 0;
while (n >= (x + 1) * (x + 1))
    x = x + 1;

    • 解题步骤

      • 找出基本运算：x = x + 1

      • 设出执行时间：t

      • 分析关系

        t x
        1 1
        2 2
        3 3
        t t

      • 因为n >= (x + 1) * (x + 1)，即 n >= (t+1)2

      • 所以 t+1<=√(n)，即 t <= n1/2 -1

      • 根据加法规则，T(n) = O(n1/2)

空间复杂度

  • 定义

    1、与时间复杂度类似，类比时间复杂度指算法的运行时间与输入值(问题规模)之间的关系
    2、由此空间复杂度便可简单概述为算法的存储空间与输入值(问题规模)之间的关系
    3、算法的空间复杂度记为 S(n) = O(f(n))

  • 例题 1

    • 程序

      int sum(int n)
{
    int value = 0;
    int ii = 1;
    while (ii <= n)
    {
        value = value + ii;
        ii++;
    }
    return value;
}

    • 解题步骤

      • 对于该程序而言，无论 n 是多少，都只声明value、ii两个变量

      • 因此n 对于空间没有影响，S(n) = O(1)

  • 例题 2

    • 程序

      int sum(int n)
{
    int value = 0;
    int ii[n];
    // ...
}

    • 解题步骤

      • 如果 int 所占空间为 4B，那么该程序所需空间为 4+4n

      • 根据加法规则，S(n) = O(n)

      • 该题目若改为int ii[n][n];二维数组，则 S(n) = O(n2)

  • 例题 3

    • 程序

      int sum(int n)
{
    if (n == 0)
        return 0;
    int ii, jj, kk;
    return n + sum(n - 1);
}

    • 解题步骤

      • 同样分类讨论，显然当 n=0 时 S(n) = O(1)，接下来讨论 n>0 时的情况

      • 与时间复杂度方法类似，得出该函数共递归执行 n 次，每次创建一组新的变量，因此 S(n) = O(n)

      • 注意如果没有int ii,jj,kk;空间复杂度 S(n)仍为 O(n)，因为递归函数每次递归时，新一次函数调用的形参也需要新的空间

  • 例题 4

    • 程序

      int sum(int n)
{
    if (n == 0)
        return 0;
    int arr[n];
    return n + sum(n - 1);
}

    • 解题步骤

      • 分析关系

        n(向下递归的过程) arr 所需空间
        5 5
        4 4
        3 3
        2 2
        1 1

      • 可以得出 arr 所需的平均空间与 n 的关系为 n/2，而函数形参所需空间为 n，每次递归都声明一组 arr

      • 因此 S(n) = O(n/2)*O(n)，根据乘法规则，S(n) = O(n2)

  • 例题 5

    • 程序

      int sum(int n)
{
    if (n == 0)
        return 0;
    int value = n + sum(n-1);
    int arr[n];
    return value;
}

    • 解题步骤

      • 注意该程序与例题 4 的程序的区别，该程序的数组定义在递归之后

      • 这意味着在递去的过程中，没有创建数组，在归来的过程中创建。因此在递去过程中其他变量的复杂度为 O(n)，在归来过程中，创建完数组后函数就结束释放内存了，并不会继续占用空间，所以 arr 最大占用空间也为 n

      • 因此最终 S(n) = O(n) + O(n) = O(n)

页底评论