数据结构与算法分析(c++描述)-02-算法分析

本文最后更新于：2021年7月7日

  • 如何估计一个程序所需要的时间。

  • 如何将一个程序的运行时间从天或年降低到不足一秒。

  • 粗心地使用递归的后果。

  • 用于将一个数自乘得到其幂以及计算两个数的最大公因数的非常有效的算法。

2.1 数学基础

相对增长率(relative rates of growth)：在函数间建立一种相对的级别

例：

大O记法：

当我们说$T(N)=O(f(N))$时，我们是在保证函数$T(N)$在以不快于$f(N)$的速度增长。

典型的增长率

  • N的增长要快于log的任意的幂。
函数 名称
$c$ 常量
$logN$ 对数
$log^2N$ 对数的平方
$N$ 线性
$NlogN$
$N^2$ 二次
$N^3$ 三次
$2^N$ 指数

2.2 模型

为了在形式的框架中分析算法，我们需要一个计算模型。

  • 模型机做任何一件简单的工作都恰好花费一个时间单位
  • 假设模型机有无限的内存

2.3 要分析的问题

运行时间，所使用的算法，算法的输入

  • 平均情形反应典型的结果
  • 最坏的情形代表对任何可能的输入在性能上的一种保证
  • 若无特殊说明，所需要的量是最坏情况的运行时间

最大的子序列和问题：

给定整数，可能有负数，求$\sum_{k=i}^jA_k$ 的最大值。如果所有整数均为负数，则最大子序列和为0。

例如：-2，11，-4，13，-5，-2。答案为20。

2.4 运行时间计算

计算大O运行时间。

2.4.1 一个简单的例子

计算$\sum_{k=i}^ji^3$

1
2
3
4
5
6
7
8
int sum(int n)
{
    int partialSum  = 0;			//1个时间单位
    for (int i = 0; i < n; i++){	//初始化1个时间单位，测试N+1个时间单位，自增运算N个时间单位
        partialSum += i*i*i;		//4个时间单位（两个乘法，一次加法，一次赋值）
    }
    return partialSum;				//1个时间单位
}

1+1+N+1+N+4N+1=6N+4 -> O(N)

2.4.2 一般法则

法则1：for循环

一个for循环的运行时间至多是该for循环内语句（包括测试）的运行时间乘以迭代的次数

法则2：嵌套循环

从里向外分析这些循环。在一组嵌套循环内部的一条语句总的运行时间为该语句的运行时间乘以该组所有循环的大小的乘积。

下列程序片段为$O(N^2)$

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

法则3：顺序语句

将各个语句的运行时间求和即可（这意味着，其中的最大值就是所得的运行时间）。

作为一个例子，下面的程序片段先是花费$O(N)$，接着是$O(N^2)$，因此总量也是$O(N^2)$：

1
2
3
4
5
for(int i = 0; i < n; i++)
    a[i] = 0;
for(int i = 0; i < n; i++)
    for(int j = 0; j < n; j++)
        a[i] += a[j] + i + j;

法则4：If/Else语句

1
2
3
4
if(condition)
    S1
else
    S2

一个if/else语句的运行时间从不超过判断再加上S和S2中运行时间较长者的总的运行时间。

2.4.3 最大子序列和问题的解

算法1：穷举。$O(N^3)$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
int maxSubSym1(const vector<int> & a)
{
    int maxSum = 0;
    for(int i = 0; i < a.size(); i++){
        for(int j = i; j < a.size(); j++){
            int thisSum = 0;
            for (int k = i; k < j; k++)
                thisSum += a[k];
            if (thisSum > maxSum)
                maxSum = thisSum;                      
        }
    }
    return maxSum;
}

算法2：$O(N^2)$

1
2
3
4
5
6
7
8
9
10
11
12
13
int maxSubSym2(const vector<int> & a)
{
    int maxSum = 0;
    for(int i = 0; i < a.size(); i++){
        int thisSum = 0;
        for(int j = i; j < a.size(); j++){
            thisSum += a[j];
            if (thisSum > maxSum)
                maxSum = thisSum;        
        }
    }
    return maxSum;
}

算法3：递归。$O(NlogN)$

分治(divide-and-conquer)策略，其想法是把问题分成两个大致相等的子问题，然后递归地对它们求解，这是“分”的部分。“治”阶段将两个子问题的解合并到一起并可能再做少量的附加工作，最后得到整个问题的解。

最大子序列和可能出现在三处地方：或者整个出现在输入数据的左半部，或者整个出现在右半部，或者跨越输入数据的中部从而占据左右两半部分。

  • 前两种情况可以递归求解。

  • 第三种情况的最大和可以通过求出前半部分的最大和（包含前半部分的最后一个元素）以及后半部分的最大和（包含后半部分的第一个元素）而得到。然后将这两个和加在一起。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
int max3(int a, int b, int c){
    int max = 0;
    max = (a > b)? a : b;
    max = (max > c)? max : c;
    return max;
}

int maxSumRec(const vector<int> & a, int left, int right)
{
    //Base case: only one value
    if (left == right){
        if(a[left] > 0)
            return a[left];
        else
            return 0;
    }
    
    int center = (left + right) / 2;
    int maxLeftSum = maxSumRec(a, left, center);
    int maxRightSum = maxSumRec(a, center + 1, right);

    int maxLeftBorderSum = 0, leftBorderSum = 0;
    for (int i = center; i > left; i--){
        leftBorderSum += a[i];
        if(leftBorderSum > maxLeftBorderSum)
            maxLeftBorderSum = leftBorderSum;
    }

    int maxRightBorderSum = 0, rightBorderSum = 0;
    for(int j = center + 1; j <= right; j++){
        rightBorderSum += a[j];
        if(rightBorderSum > maxRightBorderSum)
            maxRightBorderSum = rightBorderSum;
    }
    return max3(maxLeftSum, maxRightSum, maxLeftBorderSum + maxRightBorderSum);
}

// N 必须是偶数
int maxSubSum3(const vector<int>& a)
{
    return maxSumRec(a, 0, a.size() -1);
}

算法4：$O(N)$

1
2
3
4
5
6
7
8
9
10
11
12
13
int maxSubSum4(const vector<int>& a)
{
    int maxSum = 0, thisSum = 0;
    for(int i = 0; i < a.size(); i++){
        thisSum += a[i];
        
        if(thisSum > maxSum)
            maxSum = thisSum;
        else if(thisSum < 0)
            thisSum = 0;
    }
    return maxSum;
}

2.4.4 运行时间中的对数

如果一个算法用常数时间($O(1)$)将问题的大小削减为其一部分(通常是1/2)，那么该算法就是$O(logN)$的。

1. 二分搜索(binary search)

给定一个整数$X$和整数，后者已经预先排序并在内存中，求下标$i$使得$A_i＝X$，如果$X$不在数据中，则返回$i＝-1$。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
template <typename Comparable>
int binarySearch(const vector<Comparable> & a, const Comparable & x)
{
    int low = 0, high = a.size() - 1;
    while (low < high)
    {
        int mid = (low + high) / 2;
        if(a[mid] < x)
            low = mid + 1;
        else if(a[mid] > x)
            high = mid - 1;
        else
            return mid; //Found
    }
    return -1;  //not_found
}

应用场景：

  • 数据稳定（不允许插入和删除操作）
  • 数据是排序的

2. 欧几里得算法

计算最大公因数（同时整除二者得最大整数）

1
2
3
4
5
6
7
8
9
long gcd(long m, long n)
{
    while (n != 0){
        long rem = m % n;
        m = n;
        n = rem;
    }
    return m;
}

3. 幂运算

使用递归算法，$N \leq 1$是递归的基本情形。

如果$N$是偶数，$X^N=X^{N/2}X^{N/2}$

如果$N$是奇数，$X^N=X^{(N-1)/2}X^{(N-1)/2}X$

1
2
3
4
5
6
7
8
9
10
long pow(long x, int n){
    if(n == 0)
        return 1;
    if(n == 1)
        return x;
    if(isEven(n))
        return pow(x * x, n / 2);
    else
        return pow(x * x, n / 2) * x;
}
编程
学习笔记 c++ 数据结构和算法

本博客所有文章除特别声明外，均采用 CC BY-SA 3.0协议 。转载请注明出处！