欢迎来到尧图网

客户服务 关于我们

您的位置:首页 > 房产 > 家装 > 数据结构与算法之美:复杂度分析

数据结构与算法之美:复杂度分析

2025/4/20 5:13:46 来源:https://blog.csdn.net/2401_87995839/article/details/144209656  浏览:    关键词:数据结构与算法之美:复杂度分析

        Hello大家好!很高兴我们又见面啦!给生活添点passion,开始今天的编程之路!

今天我们学习新的内容:复杂度

e24d0ea52f1b428687227cf46db7e4fd.gif

我的博客:<但凡.

我的专栏:《题海拾贝》、《编程之路》

欢迎点赞、关注!

1、 什么是复杂度

        我们在编写程序时,程序运行会消耗时间和占用内存。为了靠时间和占用内存来评判一个算法的好坏,我们抽象出了复杂度这个概念。其中,复杂度又包含时间复杂度和空间复杂度。

        时间复杂度的全称是渐进时间复杂度(asymptotic time complexity),表示算法的执行时间与数据规模之间的增长关系

        空间复杂度全称就是渐进空间复杂度(asymptotic space complexity),表示算法的存储空间与数据规模之间的增长关系

2、时间复杂度

        假设有所有代码的执行时间T(n)与每行代码的执行次数成正比,那么大O复杂度表示为:

T(n)=O(f(n))

        n表示数据规模的大小;f(n)表示每行代码执行的次数总和; O代表代码的执行时间T(n)与 f(n) 表达式成正比。

不理解也没关系,我们直接上手分析几个程序就明白了:


#include<stdio.h>
int main()
{int i = 0;int N = 0;scanf("%d",&N);for (i = 0;i < N;i++){printf("%d", i);}return 0;
}

        在这个程序中,我们实际上消耗时间的代码就是for循环。因为for循环一共循环了N次,这个程序的时间复杂度就是O(N)


#include<stdio.h>
int main()
{int i = 0;int N = 0;int j = 0;scanf("%d",&N);for (i = 0;i < N;i++){for(j=0;j<N;j++){printf("%d",j);}}return 0;
}

        在这串代码中,出现了for循环嵌套,也就是说我们一共进行了N*N次循环,那么时间复杂度就是O(N^2)

大O阶规则

        现在我们介绍推导大O阶规则,这里我简单概括一下:

        1、如果N有多个阶级出现,只保留最高阶。

举例:

#include<stdio.h>
int main()
{int i = 0;int N = 0;int j = 0;scanf("%d",&N);for (i = 0;i < N;i++){for(j=0;j<N;j++){printf("%d",j);}}for (i = 0;i < N;i++){printf("%d", i);}return 0;
}

        这个程序的时间复杂度照常理来说应该是O(N^2+N),但是由于我们只保留最高阶,所以他的时间复杂度是O(N^2)。

2、如果最高阶存在,则去除常数系数

举例:

#include<stdio.h>
int main()
{int i = 0;int N = 0;int j = 0;scanf("%d",&N);for (i = 0;i < N;i++){printf("%d",i);}for (i = 0;i < N;i++){printf("%d", i);}return 0;
}

        这个程序照常理来说应该是O(N+N)=O(2N),但实际上我们要去掉他的常数系数,所以他的时间复杂度是O(N)。

3、如果没有与N相关的项目,只有常数项,就用1代替所有加法常数

举例:

#include<stdio.h>
int main()
{int i = 0;int N = 0;int j = 0;scanf("%d", &N);for (i = 0;i < 100;i++){printf("%d",i);}return 0;
}

        因为我们计算次数与N没关系,是个常数,所以他的时间复杂度就是O(1)。


现在我们来分析一下这串代码的时间复杂度:

void test(int N)
{int cnt = 1;while (cnt < N){cnt *= 2;}
}

这里我们不妨举几个例子:

如果N等于2 , 循环1次

如果N等于4,  循环2次

如果N等于8,  循环3次

如果N等于16,循环4次

……

           观察并找寻规律,我们不难得出循环次数=log2N(2为底数),所以他的时间复杂度就是O(logN)。因为在计算机中打不出底数,而底数的大小对于log函数的图线涨幅变化没有差别(图线形状都一样),所以人们默认写成logN。


现在我们来看递归代码的时间复杂度:

int test(int N)
{if (N == 0){return 1;}return test(N - 1) * N;
}

        递归代码的时间复杂度=单次递归的时间复杂度*递归次数,在这串代码中,单次递归的时间复杂度为1,递归次数为N,所以时间复杂度为O(N)。

3、空间复杂度

        空间复杂度表示算法的存储空间与数据规模之间的增长关系。

        如果说时间复杂度看的是运行次数,那么空间复杂度看的就是内存的使用次数。

例如:

void test(int N,int *a)
{int i = 0;for (i = 0;i < N;i++){a[i] = i;}
}

        在这串代码中,我们对数组a进行了N次赋值,所以他的空间复杂度就是O(N)。

空间复杂度同样遵循大O阶的推导规则,例如下面这串代码的空间复杂度就是O(1):

void test(int N,int *a)
{int i = 0;a[0] = i;
}

        实际上,随着内存越来越多(目前电脑内存大多为16G,8G,甚至32G),我们没必要太过于珍惜内存,空间复杂度就的优先级就小于时间复杂度了,但是这并不意味着空间复杂度不重要。

        好了,今天的内容就分享到这,我们下期再见!

版权声明:

本网仅为发布的内容提供存储空间,不对发表、转载的内容提供任何形式的保证。凡本网注明“来源:XXX网络”的作品,均转载自其它媒体,著作权归作者所有,商业转载请联系作者获得授权,非商业转载请注明出处。

我们尊重并感谢每一位作者,均已注明文章来源和作者。如因作品内容、版权或其它问题,请及时与我们联系,联系邮箱:809451989@qq.com,投稿邮箱:809451989@qq.com

热搜词