数据结构与算法之——算法的基本概念

1、什么是算法

程序=数据结构+算法

数据结构是要处理的信息

算法是处理信息的步骤

2、算法的五个特性

2.1 有穷性:有穷时间内能执行完。算法是又穷的,程序可以是无穷的
2.2 确定性:相同输入只会产生相同输出
2.3 输入:一个算法有零个或者有多个输入,这些输入取自于某个特定的对象的集合。
2.4 输出:一个算法有一个或者多个输出,这些输出是与输入有着某种特定关系的量。

3、“好”的算法的特质

3.1 正确性:能正确解决问题
3.2 可读性:对算法的描述要让其他人也看得懂
3.3 健壮性:算法能处理一些异常状况
3.4 高效能与底存储:时间复杂度,空间复杂度低,即算法执行省时,省内存

算法的时间复杂度

是用来衡量时间开销和问题规模n之间的关系

时间复杂度的数量级:

O(1)<O(log2n)<O(n)<O(nlog2n)<O(n2)<O(n3)<O(2n)<O(n!)<O(nn)

算法的空间复杂度

是用来衡量内存开销和问题规模n之间的关系

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

2、对于递归算法,一般把递归层数看作空间复杂度,比如

void loveYou(int n) {
    int a,b,c;
    if(n>1) {
        loveYou(n-1);
    }
    printf("I Love You %d\n",n);
}

以上代码假设开辟变量a,b,c一共需花费x内存,一共有n层递归,那么总共花费xn内存,S(n)=O(xn)=O(n);

不过以上代码只是大多情况,也有其他情况的,比如

void loveYou(int n) {
    int a[n];
    if(n>1) {
        loveYou(n-1);
    }
    printf("I Love You %d\n",n);
}

上面这个算法所需的内存就是n+(n-1)+(n-2)+...+2+1=[n(n+1)]/2=n2/2+n/2=O(n2);

持续更新中。。。。

点赞

发表回复

电子邮件地址不会被公开。必填项已用 * 标注