数据结构 --- 复杂度概念及计算讲解(时间复杂度,空间复杂度)

这篇具有很好参考价值的文章主要介绍了数据结构 --- 复杂度概念及计算讲解(时间复杂度,空间复杂度)。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

数据结构 --- 复杂度概念及计算讲解(时间复杂度,空间复杂度),数据结构,算法,java,c语言,笔记,经验分享,链表
今天没有sao话,今天认真学习

一、时间复杂度

1、概念讲解

2、计算讲解

二、空间复杂度

1、概念讲解

2、计算讲解

三、常见复杂度对比

四、完结撒❀

前言:

经常刷题的人都知道,我们在解决一道题时可能有多个解法,那么如何判断那个解法才是最优解呢?
我们通常从代码的两个方面进行判断:1.时间 2.空间。
–❀–❀–❀–❀–❀–❀–❀–❀–❀–❀–❀–❀–❀–❀–❀–❀–❀–❀–❀–❀–❀–❀–❀–❀–❀–❀–❀–❀–❀–❀–❀–❀–❀–❀–❀–❀–❀–❀–❀–❀–❀–❀–❀–❀–❀–

一、时间复杂度

我们通常可能会认为一个算法的实现方式越短越简洁就越好,其实不是,比如对于以下斐波那契数列:

long long Fib(int N)
{
 if(N < 3)
 return 1;
 
 return Fib(N-1) + Fib(N-2);
}

斐波那契数列的递归实现方式非常简洁,但简洁就一定好吗?那该如何衡量其好坏呢?
算法在编写为可执行程序后,运行时需要消耗时间资源和空间(内存)资源。因此衡量一个算法的好坏,一般是从时间和空间两个维度来衡量的,即时间复杂度和空间复杂度。

1、概念讲解

时间复杂度的定义:

在计算机科学中,算法的时间复杂度是一个函数,它定量描述了该算法的运行时间。

从理论上来说,一个算法执行所消耗的时间是不能计算出来的,只有把代码放到机器上跑起来才能知道,而我们如果将每一个算法都进行上机测试,那么这是非常麻烦的,所以才有了时间复杂度这个分析方式。
一个算法所花费的时间与其中语句的执行次数成正比例,算法中基本操作的执行次数,为算法的时间复杂度

2、计算讲解

实际中我们计算时间复杂度时,我们其实并不一定要计算精确的执行次数,而只需要大概执行次数,那么这里我们使用大O的渐进表示法

这里简单提一下大O的渐进表示法

大O符号(Big O notation):是用于描述函数渐进行为的数学符号。
推导大O阶方法:

1、用常数1取代运行时间中的所有加法常数
2、在修改后的运行次数函数中,只保留最高阶项
3、如果最高阶项存在且不是1,则去除与这个项目相乘的常数。得到的结果就是大O阶。

下面进行举例讲解:

// 请计算一下Func1中++count语句总共执行了多少次?
void Func1(int N)
{
int count = 0;
for (int i = 0; i < N ; ++ i)
{
 for (int j = 0; j < N ; ++ j)
 {
 ++count;
 }
}
 
for (int k = 0; k < 2 * N ; ++ k)
{
 ++count;
}
int M = 10;
while (M--)
{
 ++count;
}

计算Func1函数的时间复杂度。
脑袋冥想调试法可以运行出来Func1函数对++count语句一共执行的次数为:

F(N)=N^2+2*N+10

我们将N设置为具体数字,并且以10倍增长的方式计算F(N)的数值:
··· N=10 F(N)= 130
··· N=100 F(N)= 10210
···N=1000 F(N)= 1002010

可以看到到越大时,F(N)之间的差距会越来越微不足道,所以我们使用大O的渐进表示法去掉了那些对结果影响不大的项,得到的就是时间复杂度,那么Func1的时间复杂度为O(N^2)。

可以看成时间复杂度是按照等级来进行划分范围的,我们只需要知道函数时间复杂度的范围来判断其代码的执行是否高效就够了。

那么时间复杂度一般有这几个等级:
O(1):表示代码运行的次数为已经指定的常熟次。
O(logN):比如二分查找。
O(N):根据问题规模N的值,确定时间复杂度。
O(N+M):根据两个未知数N,M,的问题规模的值,确定时间复杂度。
O(N^2):比如冒泡排序,斐波那契递归。

这里特别强调一下:
在所给的问题规模是未知数的情况下,有些算法的时间复杂度存在最好、平均和最坏的情况

最坏情况:任意输入规模的最大运行次数(上界)
平均情况:任意输入规模的期望运行次数
最好情况:任意输入规模的最小运行次数(下界)

在实际中一般情况关注的是算法的最坏运行情况,所以数组中搜索数据时间复杂度为O(N)

二、空间复杂度

在计算机发展的早期,计算机的存储容量很小。所以对空间复杂度很是在乎。但是经过计算机行业的迅速发展,计算机的存储容量已经达到了很高的程度,所以对于空间复杂度的关注没有时间复杂度那么高,甚至有时可以牺牲一些空间来换取时间上的提升

1、概念讲解

空间复杂度也是一个数学表达式,是对一个算法在运行过程中临时占用存储空间大小的量度

空间复杂度不是程序占用了多少bytes的空间,因为这个也没太大意义,所以空间复杂度算的是变量的个数。空间复杂度计算规则基本跟时间复杂度类似,也使用大O渐进表示法

2、计算讲解

函数运行时所需要的栈空间(存储参数、局部变量、一些寄存器信息等)在编译期间已经确定好了,因此空间复杂度主要通过函数在运行时候显式申请的额外空间来确定。

下面我们举讲解:

// 计算阶乘递归Fac的空间复杂度?
long long Fac(size_t N)
{
 if(N == 0)
 return 1;
 
 return Fac(N-1)*N;
}

空间复杂度主要通过函数在运行时候显式申请的额外空间来确定,所以我们需要知道Fac函数在递归过程中一共开辟了多少次空间来调用函数,学过函数栈帧的创建和销毁的同学可能一眼就看出来答案了。
我们在每一次调用函数时都会在栈区开辟一块空间,上面我们可以假设N等于10,那么Fac函数的递归在栈区中一共就会开辟10次空间进行调用,所以空间复杂度为O(N)。

三、常见复杂度对比

一般算法常见的复杂度如下:
常数阶

5201314 O(1)

线性阶

3n+4 O(n)

平方阶

3n^2+4n+5 O(n^2)

对数阶

3log(2)n+4 O(logn)

nlogn阶

2n+3nlog(2)n+14 O(nlogn)

立方阶

n^3+2n ^2+4n+6 O(n^3)

指数阶

2^n O(2^n)

四、完结撒❀

如果以上内容对你有帮助不妨点赞支持一下,以后还会分享更多编程知识,我们一起进步。
最后我想讲的是,据说点赞的都能找到漂亮女朋友
数据结构 --- 复杂度概念及计算讲解(时间复杂度,空间复杂度),数据结构,算法,java,c语言,笔记,经验分享,链表文章来源地址https://www.toymoban.com/news/detail-842260.html

到了这里,关于数据结构 --- 复杂度概念及计算讲解(时间复杂度,空间复杂度)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 【数据结构】二叉树的顺序结构实现及时间复杂度计算(二)

    目录 一,二叉树的顺序结构实现         1,二叉树的顺序结构         2,堆的概念及结构         3,堆的接口实现 1,堆的创建 2,接口函数 3,初始化 4,销毁 5,是否增容 6,交换数据 7,堆向上调整算法 8,插入数据 9,删除数据 10,堆向下调整算法 11,打印数

    2024年02月09日
    浏览(37)
  • 【初识数据结构】手把手教会你时间复杂度的计算方法

    前言   大家好啊,这里是幸麟 一名普通的大学牲 🧩希望可以不断的进步,因此也一直在学习 如果有写的不好或者写错的地方 欢迎在评论区指正 前言后的小前言 不知道在大家学习算法时有没有遇到这样一种情况,在看大佬题解或者讲解视频时 总能找到一个叫 时间复杂度

    2024年02月09日
    浏览(91)
  • 数据结构(时间复杂度,空间复杂度)

    算法的时间复杂度是一个数学函数,算法中的基本操作的执行次数,为算法的时间复杂度。 1.大O的表示法 2.推导大O表示法 1、用常数1取代运行时间中的所有加法常数。 2、在修改后的运行次数函数中,只保留最高阶项。 3、如果最高阶项存在且不是1,则去除与这个项目相乘的

    2024年02月07日
    浏览(51)
  • 数据结构 — 时间复杂度、空间复杂度

    数据结构_空间复杂度_时间复杂度讲解_常见复杂度对比 本文介绍数据结构中的时间复杂度和空间复杂度 ***文章末尾,博主进行了概要总结,可以直接看总结部分*** 博主博客链接:https://blog.csdn.net/m0_74014525 点点关注,后期持续更新系列文章 算法效率指的是算法在处理数据时

    2024年02月13日
    浏览(53)
  • 数据结构之时间复杂度-空间复杂度

    大家好,我是深鱼~ 目录 1.数据结构前言 1.1什么是数据结构 1.2什么是算法 1.3数据结构和算法的重要性 1.4如何学好数据结构和算法 2.算法的效率 3.时间复杂度 3.1时间复杂度的概念 3.2大O的渐进表示法 【实例1】:双重循环的时间复杂度:O(N) 【实例2】:双重循环的时间复杂度

    2024年02月14日
    浏览(42)
  • 【数据结构】时间复杂度与空间复杂度

    在学习C语言的时候,大多数的小伙伴们并不会对算法的效率了解,也许算法也是一个陌生的领域,当进入了数据结构这个模块,就应该对算法的效率做一个清晰的认识。但是算法的效率是什么呢?这里就引出来时间复杂度与空间复杂度的概念了。 算法效率 指的是算法解决问

    2024年02月07日
    浏览(44)
  • 数据结构--时间复杂度与空间复杂度

    在计算机科学中,算法的时间复杂度是一个函数,它定量描述了该算法的运行时间。一个算法执行所耗费的时间,从理论上说,是不能算出来的,只有程序在机器上跑起来,才能知道,但是如果所有的算法都需要在机器上运行起来去测试时间复杂度就会很麻烦,所以才有了时

    2024年02月16日
    浏览(43)
  • 【数据结构】---时间复杂度与空间复杂度

    💐 🌸 🌷 🍀 🌹 🌻 🌺 🍁 🍃 🍂 🌿 🍄🍝 🍛 🍤 📃 个人主页 :阿然成长日记 👈点击可跳转 📆 个人专栏: 🔹数据结构与算法🔹C语言进阶 🚩 不能则学,不知则问,耻于问人,决无长进 🍭 🍯 🍎 🍏 🍊 🍋 🍒 🍇 🍉 🍓 🍑 🍈 🍌 🍐 🍍 · 时间复杂度的定义

    2024年02月15日
    浏览(53)
  • 数据结构——时间复杂度和空间复杂度

    1.算法效率 2.时间复杂度 3.空间复杂度 4. 常见时间复杂度以及复杂度oj练习 1.算法效率 1.1 如何衡量一个算法的好坏 如何衡量一个算法的好坏呢?比如对于以下斐波那契数的计算 我们看到虽然用递归的方式实现斐波那契很简单,但是简单一定代表效率高吗? 我们接着往下看。

    2024年02月13日
    浏览(49)
  • 数据结构入门 — 时间复杂度、空间复杂度

    数据结构_空间复杂度_时间复杂度讲解_常见复杂度对比 本文介绍数据结构中的时间复杂度和空间复杂度 ***文章末尾,博主进行了概要总结,可以直接看总结部分*** 博主博客链接:https://blog.csdn.net/m0_74014525 点点关注,后期持续更新系列文章 算法效率指的是算法在处理数据时

    2024年02月13日
    浏览(54)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包