分析和设计算法

前言

循环不变式

n位二进制整数相加问题

RAM模型

使用RAM模型分析

代码的最坏情况和平均情况分析

插入排序最坏情况分析

插入排序平均情况分析

设计算法

分治法

总结

前言

循环迭代，分析算法和设计算法作为算法中的三个重要的角色，下面从一些程序示例入手，介绍如何使用有效的方法来设计和分析算法。

循环不变式

代码：

int f(int n) {
    int res = 1;
    for(int i = 1; i <= n; i++) {
        res = res * i;
    }
    return res;
}

这是求n!的函数， res是每次迭代的(i-1)!的结果，可以看到每趟迭代下来，它的形式都是res，没有变更过，我们称之为循环不变式。

循环不变式有初始化，保持和终止三要素。

初始化：循环的第一次迭代，它为真。代码中如果res = 0; 则第一次迭代的结果res = 0;

结果为假，初始化错误。

保持：如果本次迭代结果为真，则下一次的结果也为真。本次res = i!, 下一次res = res * (i+1) = i! * (i + 1) = (i+1)!. 可以理解为迭代保持了。

终止：迭代终止的条件， i > n时，迭代终止。数学归纳法中只有初始化和保持的证明，但是没有终止这一步。当i叠加到n+1时，上一次迭代结果时res = res*i = i! = n!已经是正确结果了，所以迭代条件终止时，结果正确。

n位二进制整数相加问题

初始化：A[MAXSIZE] = {0}, B[MAXSIZE] = {0}, C[MAXSIZE] = {0}.

保持：C[i+1] = (A[i] + B[i] + C[i])/2; C[i] = (A[i] + B[i] + C[i])%2.

终止条件：A[i]和B[i]中全部为零，迭代终止.

代码：

void num_to_binary(int num, int B[MAXSIZE]) {
    for (int i = 0; num > 0; i++)
    {
        B[i] = num % 2;
        num = num / 2;
        printf("%d", B[i]);
    }
    printf("\n");
    
}

void binary_add(int A[MAXSIZE], int B[MAXSIZE], int C[MAXSIZE + 1]) {
    int i;
    for (i = 0; B[i] || A[i] ; i++)
    {
        C[i+1] = (A[i] + B[i] + C[i]) / 2;
        C[i] = (A[i] + B[i] + C[i]) % 2;
        printf("%d", C[i]);
    }
    printf("%d\n", C[i]);
}

输出结果：

RAM模型

在分析算法时，我们经常提到时间复杂度和空间复杂度。这些都是基于代码中的指令是一条一条地在CPU中执行的，不存在并行操作。这种前提可以理解位RAM模型。

使用RAM模型分析

代码	代价	次数
int res = 1;	C1	1
for(int i = 1; i <= n; i++)	C2	n
res = res * i;	C3	n
return res;	C4	1

上述代码的运行时间位Tn=c1+c2*n+c3*n+c4.

T(n)为n的线性函数，所以可以说改代码的时间复杂度为O(n).

代码的最坏情况和平均情况分析

  for(int i = 0; i < 10; i++) {
        while (p->next)
        {
            lnode *q = p->next;
            if(q->data > data[i]) {
                lnode *node = (lnode *) malloc(sizeof(lnode));
                node->data = data[i];
                node->next = q;
                p->next = node;
                break;
            }
            p = p->next;
        }
        p = list;
}
}

插入排序最坏情况分析

10个元素参与插入排序，最坏情况下，每趟插入的位置都是表尾：

第一趟比较1次

第二趟比较2次

。。。

第n趟比较n次

T(n) = (1+2+3+…+n) + c = (n+1)*n/2 + cn.(c为插入一个结点的时间复杂度)。

插入排序平均情况分析

平均比较次数：

第一趟比较（1+1）/2

第二趟比较（1+2）/2

。。。

第n趟比较（1+n）/2

T(n) = n*n/4 + cn.

在n足够大的时候，可以认为插入排序的最坏情况和平均情况的时间复杂度均为O(n*n).

设计算法

分治法

分治三个步骤：

分解：分解原问题为子问题，这些子问题为原问题的较小规模的问题。

解决：递归地解决这些子问题，如果规模小到一定程度，则直接得出答案。

合并：合并上述解决地子问题地解，得出最终解。

前提：该集合S经过归并排序之后的序列再进行如下算法运算。

分解：集合S的n个问题分解成两个规模n/2的问题。

解决：递归的解决和分解这些子问题，直到规模为2时，两个数相加与x比较，如果相等则存在，否则返回不存在。

合并：合并两个子问题，两个子问题中不存在和等于x的情况，所以需要判断是否存在跨集合相加和等于x的情况。

代码：

#include "stdio.h"
#define OK 1
#define ERROR 0
#define MAXSIZE 10
int FLAG = 0;
int is_x(int a1[MAXSIZE], int x, int low, int mid, int high);
void jude_add_x(int a[MAXSIZE], int x, int low, int high);

void main() {
    int b[10] = {-1,2,3,5,9,27,29,38,49,74};
    int x = 8;
    jude_add_x(b, x, 0, 9);
    printf("The result is %d", FLAG);
}

int is_x(int a1[MAXSIZE], int x, int low, int mid, int high) {
    
    int i = low, j = mid+1, k = low;
    while (i <= mid || j <= high)
    {
        if(a1[i] + a1[j] == x) 
        {
            return OK;
        }else if(a1[i] + a1[j] < x) {
            if(i < mid) i++;
            else if( j <= high) j++;
            else return ERROR;
        }else {
            return ERROR;
        }
    } 
    return ERROR;
}

void jude_add_x(int a[MAXSIZE], int x, int low, int high) {

    if(low == high) {
        return;
    }
    int mid = (low + high) / 2;
    jude_add_x(a, x, low, mid);
    jude_add_x(a, x, mid + 1, high);
    if(low != high && is_x(a, x, low, mid, high)) FLAG = 1;
}

输出结果：