您的位置:首页 > 财经 > 产业 > 广州网站推广排名_石家庄网页设计_推广赚钱的软件_怎么有自己的网站

广州网站推广排名_石家庄网页设计_推广赚钱的软件_怎么有自己的网站

2024/12/24 8:17:08 来源:https://blog.csdn.net/qq_62917398/article/details/144327072  浏览:    关键词:广州网站推广排名_石家庄网页设计_推广赚钱的软件_怎么有自己的网站
广州网站推广排名_石家庄网页设计_推广赚钱的软件_怎么有自己的网站

时间复杂度与空间复杂度的介绍

  • 一、数据结构的基本概念
    • 1、逻辑结构
      • (1)、线性关系
      • (2)、非线性关系
    • 2、存储形式
  • 二、数据结构的算法分析
    • 1、时间复杂度
    • 2、空间复杂度
    • 3、时空复杂度互换

一、数据结构的基本概念

\quad 数据结构是一门研究如何有效组织数据,并提高数据处理效率的学科。通过研究各种数据内部的逻辑关系,使用某种特定的存储形式,并在此基础上对数据实施各种操作,这些工作被称为称为广义上的算法。

1、逻辑结构

  • 指数据之间的内在关系。通常有集合、线性表、树、图等常见的逻辑结构。
  • 逻辑结构是数据之间本身的属性,跟我们怎么处理它们无关
    在这里插入图片描述

(1)、线性关系

\quad 各个元素之间是一种一对一的关系,比如图书馆中的书架的书,除了首尾两本书之外,其余的任意一本书的编号假设是N,都有且仅有一个直接前驱节
\quad 点N-1,有且仅有一个直接后继节点N+1。这种关系就是典型的线性逻辑。
在这里插入图片描述

(2)、非线性关系

\quad 与上述线性关系的表述不同,如果各个元素之间不是严格一对一的关系,则被称为非线性关系,比如家族中的各个成员、不同城市间的交通道路等,对
\quad 于它们中间的某个元素,都可能有不止一个元素与之关联。这种关系是典型的非线性逻辑。

在这里插入图片描述

2、存储形式

  • 数据的存储方式。比如顺序存储、链式存储等。
  • 不同的存储形式对最终数据的处理效率通常有很大的影响。
  • 逻辑结构与存储形式并无必然联系。

二、数据结构的算法分析

\quad 算法分析是指算法在正确的情况下,对其优劣的分析。一个好的算法通常是指:

  • 算法对应的程序所耗时间少
  • 算法对应的程序所耗存储空间少
  • 算法结构性好、易读、易移植和调试

\quad 数据结构与算法的本质任务,是提高程序的时间空间效率,简单讲就是让程序的执行速度越快越好,所需内存空间越少越好。虽然在很多情况下,程序的时空特性是相互制约的,就像鱼与熊掌不可兼得,但我们可以根据程序实际解决问题的侧重点,去平衡时间和空间的对性能的消耗。

1、时间复杂度

\quad 一般而言,时间复杂度并不考察一段代码运行所需要的绝对时间,因为不同的计算机的硬件参数不同,考察绝对时间没有意义。时间复杂度一般指的是代码的语句执行总次数,称为语句频度。比如:

void counting(int n)
{for(int i=1; i<=n; i++){printf("i:本行语句将会出现%d次\n", i);              // 100次,也就是n次(这个可以忽略,因为没必要)for(int j=1; j<=n; j++){printf(" i*j:本行语句将会出现%d次\n", i*j);    // 100*100次,也就是n*n(只关心多项式的最高次幂)}}
}
  • 程序说明
    在上述代码中,程序执行的语句频度理论是:
    在这里插入图片描述
    一般情况下,我们只关心多项式的最高次幂,于是上述代码的时间复杂度表示为:
    在这里插入图片描述
    这意味着,该程序算法所需要的时间,与传进来的参数n的平方成正比。
  • 相关表达式说明
    T():总的运算次数
    O():时间复杂度(多项式的最高次幂)

2、空间复杂度

\quad 空间复杂度的概念更简单一点,就是一段程序运行时所需的内存字节量

3、时空复杂度互换

\quad 一段程序的性能指标,既要运行快速,又要节省内存,而通常这两者又是相互制约的,很难兼得。因此在实际解决问题时,会根据需要侧重一方,牺牲另一方。

版权声明:

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

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