算法与算法评价

算法与算法评价

程序=数据结构+算法

数据结构:是用数据正确地描述现实世界的问题,并存入计算机。

算法:高效的处理数据,以解决实际问题

算法是对特定问题求解步骤的一种描述,它是指令的有序序列,其中每条指令表示一个或多个操作。

算法的特性

1、有穷性。一个算法必须总在执行有穷步之后结束,且每一步都可以在有穷时间内完成。注意:算法必须是有穷的,而程序可以是无穷的。

2、确定性。算法中每条指令必须有确切的含义,对于相同的输入只能得出相同的输出。

3、可行性。算法中描述的操作都可以通过已经实现的基本运算执行有限次来实现。

4、输入。一个算法有零个或多个输入,这些输入取自于某个特定的对象的集合。

5、输出。一个算法有一个或多个输出,这些输出是与输入有着某种特定关系的量。

"好"算法的特质(设计算法时要尽量追求的目标)

1、正确性。算法应能够正确地解决求解问题。

2、可读性。算法应具有良好的可读性,以帮助人们理解。

3、健壮性。输入非法数据时,算法能适当地做出反应或进行处理,而不会产生莫名其妙的输出结果。

4、高效率与低存储量需求,即时间复杂度空间复杂度低。

如何评估算法时间开销?

我们先让算法程序先运行,再去统计程序的运行时间吗?

这样做是不正确的,因为会有外部的影响因素,比如机器性能(高性能计算机/单片机)、编程语言(高级语言/低级语言)、编译程序产生的机器指令质量和某些不可事后统计的算法(导弹控制)。

所以需要排除外部因素对算法的影响,事前预估算法时间开销T(n)与问题规模n的关系(算法时间复杂度)

#include <stdio.h>
//算法1 逐步递增型爱你

void loveyou(int n){ //n为问题规模
    int i=1; //此语句运行1次
    while(i<=n){  //此语句运行3001次
        i++; //此语句运行3000次
        printf("I Love you %d\n",i); //此语句运行3000次
    }
    printf("I Love you More Than %d\n",n); //此语句运行1次
}
int main() {
    loveyou(3000);
    return 0;
}

此程序已经注释了每条语句的执行次数,所以T(3000)=1+30001+2*3000+1,所以此时时间开销与问题规模n的关系是T(n)=3n+3

但是需要思考两个问题:

1、是否可以忽略表达式的某些部分?

2、如果有好几千行代码,按这种方法需要一行一行去数?

此时可以运用极限的思想,当问题规模n足够大(趋向无穷),可以只考虑阶数高的部分,常数项系数也可以忽略。这种方法常称为大O表示法

大O表示法

时间复杂度运算规则

加法规则:多项相加,只保留最高阶的项,且系数变为1

T(n)=T~1~(n)+T~2~(n)=O(f(n))+O(g(n))=O(max(f(n),g(n)))

乘法规则:多项相乘,都保留

T(n)=T~1~(n)+T~2~(n)=O(f(n))*O(g(n))=O(f(n)*g(n))

此时出现了一个问题,如果有多个不同规模的n相加,怎么知道哪个是高阶呢?如:

高阶加低阶

所以读者需要记忆下面公式,公式表明了不同规模的n的时间复杂度,读者可以使用洛必达对某两个n的规模进行极限运算,注意n要趋向无穷。记忆公式:常对幂指阶。图片出自王道PPT(CSKAOYAN.com)

n规模对比

所以回到第一次的代码,此时用大O表示法可以将时间开销与问题规模n的关系进行化简得T(n)=3n+3=O(n)

#include <stdio.h>
//算法1 逐步递增型爱你

void loveyou(int n){ //n为问题规模
    int i=1; //此语句运行1次

    ...假如在此处插入1000句代码

    while(i<=n){  //此语句运行3001次
        i++; //此语句运行3000次
        printf("I Love you %d\n",i); //此语句运行3000次
    }
    printf("I Love you More Than %d\n",n); //此语句运行1次
}
int main() {
    loveyou(3000);
    return 0;
}

其实可以发现,无论插入多少条代码,只要不在循环内部,其实都是顺序执行而已,影响的也只会是常数项,而常数项对于n来说是微不足道的,可以忽略(此处例子不明显,接下来会有更大规模的n,读者可以继续感受)。其次真正影响代码时间复杂度的,其实是循环语句中n的规模。所以只需挑选循环中的一个基本操作分析它的执行次数与n的关系即可。

#include <stdio.h>
//算法2 嵌套循环型爱你
void loveyou(int n){ //n为问题规模
    int i=1; //此语句运行1次
    while(i<=n){  //外层循环执行n次
        i++; //此语句运行3000次
        printf("I Love you %d\n",i);
        for (int j=1;j<=n;j++){ //嵌套循环
            printf("I am Iron Man\n"); //内层循环共执行n的平方次
        }
    }
    printf("I Love you More Than %d\n",n); //此语句运行1次
}
int main() {
    loveyou(20);
    return 0;
}

时间开销与问题规模n的关系:T(n)=O(n)+O(n^2^)=O(n^2^)

如果有多层嵌套循环,只需关注最深层循环的循环次数。

#include <stdio.h>
//算法3 指数递增型爱你
void loveyou(int n){ //n为问题规模
    int i=1;
    while(i<=n){
        i=i*2;
        printf("I Love you %d\n",i);
    }
    printf("I Love you More Than %d\n",n); //此语句运行1次
}
int main() {
    loveyou(3000);
    return 0;
}

设最深层循环语句的执行频度(总共循环的次数)为x,由循环的条件可知,循环结束时,满足2^x^>n,x=log~2~n+1

T(n)=O(x)=O(log~2~n)

#include <stdio.h>
//算法4 搜索数字型爱你
void loveyou(int flag[],int n){ //n为问题规模
    printf("I am Caijx\n");
    for(int i=0;i<n;i++){
        if(flag[i]==n);
        printf("I Love you %d\n",n);
        break;
    }
}
int main() {
    int flag[20]={1,2,3,...,4,5,6};//伪代码 flag数组中乱序存放了1~n
    int n=2;
    loveyou(flag,n);
    return 0;
}

该程序的时间复杂度需要分情况讨论

1、最好情况:元素n在第一个位置。T(n)=O(1)

2、最坏情况:元素n在最后一个位置。T(n)=O(n)

3、平均情况:假设元素n在任意一个位置的概率同为1/n。T(n)=O(n)

时间复杂度一般情况

最坏时间复杂度:最坏情况下算法的时间复杂度

平均时间复杂度:所有输入示例等概率出现的情况下 ,算法的期望运行时间

最好时间复杂度:最好情况下算法的时间复杂度

空间复杂度

空间复杂度:空间开销(内存开销)与问题规模n之间的关系。

使用算法1作为例子

//算法1 逐步递增型爱你

void loveyou(int n){ //n为问题规模
    int i=1; //此语句运行1次
    while(i<=n){  //此语句运行3001次
        i++; //此语句运行3000次
        printf("I Love you %d\n",i); //此语句运行3000次
    }
    printf("I Love you More Than %d\n",n); //此语句运行1次
}

无论问题规模怎么变,算法运行所需的内存空间都是固定的常量,算法空间复杂度为S(n)=O(1)

void space(int n){
    int flag[n];
    int i;
    //其他代码...
}

假设一个int字节占4字节,那么该程序运行的空间=4+4n+4=4n+8,所有S(n)=O)(n)。注意,形参声明的变量n也需要占用内存空间。

void space(int n){
    int flag[n][n]; //声明n*n的二维数组
    int i;
    //其他代码...
}

S(n)=O(n^2^)

void space(int n){
    int flag[n][n]; //声明n*n的二维数组
    int other[n]; //声明一个长度为n的数组
    int i;
    //其他代码...
}

S(n)=O(n^2^)+O(n)+O(1)=O(n^2^)

同样的在空间复杂度的计算里,也可以适用加法规则和优先级。

递归函数的内存开销
#include <stdio.h>
//算法5 递归型爱你
void loveyou(int n){
    int a,b,c;
    //省略部分代码
    if(n>1){
        loveyou(n-1);
    }
    printf("I Love you %d\n",n);
}
int main() {
    loveyou(5);
    return 0;
}
  1. 递归函数定义: loveyou 函数接受一个整数参数 n,它的目的是打印出 "I Love you" 以及一个数字。

  2. 递归基本情况: 在函数内部,首先检查参数 n 是否大于 1。如果 n 大于 1,它会再次调用 loveyou 函数,传递参数值为 n-1。这就是递归的部分。递归基本情况是当 n 等于 1 时,递归停止,不再进行递归调用。

  3. 递归调用栈:loveyou 函数被调用时,它会创建一个新的栈帧(stack frame),其中包含局部变量 abc,以及参数 n。然后,它会检查 n 是否大于 1,如果是,则调用 loveyou(n-1),从而创建另一个栈帧。这样递归调用会一直进行下去,直到 n 等于 1。

  4. 递归返回:n 等于 1 时,不再进行递归调用。此时,当前函数调用的栈帧会被弹出栈,控制权返回到上一次函数调用的栈帧。然后,它打印出 "I Love you" 后跟着参数 n 的值,然后继续返回到更高一层的栈帧,以此类推,直到返回到 main 函数。

  5. 输出: 最终的输出将是依次打印出 "I Love you" 后跟着数字 1、2、3、4、5。这是因为递归调用在打印之前,所以会从 1 开始打印直到 5,而不是从 5 开始打印。

    代码输出的结果如下:

    I Love you 1
    I Love you 2
    I Love you 3
    I Love you 4
    I Love you 5

    S(n)=O(n),空间复杂度等于递归调用的深度。

    如果将上述代码声明的变量a、b、c修改为数组呢,空间复杂度是否会发生变化?

    #include 
    //算法5 递归型爱你
    void loveyou(int n){
       int flag[n]; //声明一个数组
       //省略部分代码
       if(n>1){
           loveyou(n-1);
       }
       printf("I Love you %d\n",n);
    }
    int main() {
       loveyou(5);
       return 0;
    }

这段代码的空间复杂度取决于 loveyou 函数递归调用的深度以及每次递归调用所分配的空间。

在每次递归调用中,都会分配一个大小为 n 的整型数组 flag,以及函数调用所需的其他局部变量的空间(例如 int n)。因此,每次递归调用的空间复杂度为 O(n)。

假设递归的深度为 k,则总的空间复杂度为 O(n * k),其中 n 是每次递归调用所需的空间,k 是递归调用的次数。

在这个特定的例子中,递归调用的次数等于参数 n 的值。因此,假设参数 n 的值为 m,则递归调用的次数也为 m,总的空间复杂度为 O(m * n)。