精华内容
下载资源
问答
  • 数据结构学习数据结构Part.1——基本概念和术语1. 什么是数据结构数据数据元素数据结构数据结构的分类数据结构的形式化分类 数据结构 数据结构是相互之间存在某种逻辑关系的数据元素的集合 Part.1——基本概念和...

    数据结构(时间复杂度部分)

    数据结构是相互之间存在某种逻辑关系的数据元素的集合

    Part.0绪论

    1.基本概念和术语

    什么是数据结构

    概括说,数据结构是一门讨论“描述现实世界实体的数学模型(非数值计算)及其上的操作在计算机中如何表示和实现的学科”。

    数据

    数据是对信息的一种符号表示。在计算机科学中是指所有能被输入到计算机中并被计算机程序处理的符号的总称

    数据元素

    是数据的基本单位,在程序中通常作为一个整体进行考虑和处理

    数据结构

    数据结构是相互之间存在某种逻辑关系的数据元素的集合

    数据结构的分类

    1.集合:数据结构中的元素之间除了“同属一个集合” 的相互关系外,别无其他关系;
    2.线性结构:数据结构中的元素存在一对一的相互关系;
    3.树形结构:数据结构中的元素存在一对多的相互关系;
    4.图形结构:数据结构中的元素存在多对多的相互关系。

    数据结构的形式化分类

    数据结构的形式化描述:数据结构是一个二元组。
    Data_Structures=(D,S)
    其中:D是数据元素的有限集,S是D上关系的有限集。
    数据结构包括“逻辑结构”和“物理结构”两个方面(层次):
    逻辑结构是对数据元素之间的逻辑关系的描述,它可以应一个数据元素的集合和定义在此集合上的若干关系来表示;
    **物理结构(存储结构)**是数据结构在计算机中的表示和实现,逻辑结构在存储器中的映象。
    数据元素的映象:用二进制的位串表示数据元素;
    关系的映象方式:顺序映象、非顺序映象(链式、索引存储方式、散列存储方式)

    数据类型

    在一种程序设计语言中,,变量所具有的数据种类

    数据对象

    某种数据类型的集合

    逻辑结构

    关于逻辑结构:
    逻辑结构与数据元素本身的形式、内容无关
    逻辑结构与数据元素的相对位置无关
    逻辑结构与所含数据元素的个数无关
    逻辑结构与数据的存储无关,他是独立于计算机的

    2.算法和算法分析

    什么是算法

    算法:是对特定问题求解步骤的一种描述。算法是指令的有限序列,其中每一条指令表示一个或多个操作。
    特性:有穷性、确定性、可行性、输入、输出

    算法与程序

    一个程序不一定满足有穷性。程序中的指令必须是机器可执行的,而算法中无此要求。算法代表了对问题的解,而程序是算法在计算机上的特定实现。
    一个算法用程序设计语言来实现,它就是程序

    算法与数据结构

    二者是相辅相承的。解决问题时选择不同的数据结构影响算法的效率;一种数据结构的优劣由各种算法的执行来体现。

    算法的设计要求

    评价算法好坏的标准:正确性、可读性、健壮性、效率与存储量需求。
    效率与存储量需求:效率指算法执行时间;存储量指算法执行过程中所需要的最大存储空间

    算法效率衡量方法

    事后统计法:必须执行,掩盖算法本质。

    事前分析估算法:重点考虑算法效率和算法规模(一个特定算法的运行工作量的大小只依赖于问题的规模,或者说他是问题规模的函数)
    假如,随着问题规模n的增长,算法执行时间的增长率和f(n)的增长率相同,则可记作:
    T(n)=O(f(n))
    称T(n)为算法的(渐进)时间复杂度

    估算算法的时间复杂度

    时间复杂度理解参考链接
    在计算机科学中,算法的时间复杂度是一个函数,它定性描述了该算法的运行时间。这是一个关于代表算法输入值的字符串的长度的函数。时间复杂度常用大O符号表述,不包括这个函数的低阶项和首项系数。
    算法=控制结构+原操作(固有的数据类型操作)
    算法的执行时间=原操作(i)的执行次数*原操作(i)的执行时间
    也就是算法的执行时间与原操作的次数成正比。(频度:即重复执行的次数)

    一般情况下,算法中基本操作重复执行的次数是问题规模n的某个函数,用T(n)表示,若有某个辅助函数f(n),使得T(n)/f(n)的极限值(当n趋近于无穷大时)为不等于零的常数,则称f(n)是T(n)的同数量级函数。记作T(n)=O(f(n)),称O(f(n)) 为算法的渐进时间复杂度,简称时间复杂度。

    我们把算法需要执行的运算次数用输入大小n的函数来表示,即T(n)
    此时为了估算算法需要的运行时间和简化算法的分析,引入时间复杂度的概念
    定义:
    存在常数c和F(N),使得当N>=c时,T(N)<=f(N),也就是f(n)是T(n)的,可表示为T(n)=O(f(n))
    因为f(n) 的增长速度是大于或者等于 T(n) 的,即T(n) = O(f(n)),所以我们可以用 f(n) 的增长速度来度量 T(n) 的增长速度,所以我们说这个算法的时间复杂度是 O(f(n))

    时间复杂度的计算方法:
    (1)T(n)=c,c为常数时:
    常数项对函数的增长速度影响不大,这个算法的时间复杂度为O(1),如果T(n)不等于一个常数项时,直接将常数项省略
    (2)对于多次项式:
    高次项对于函数的增长速度的影响时最大的,比如n3的增长速度远超过n2,同时n2的增长速度远超过n。因此因为对精度的要求并不高,所以我们忽略次项
    (3)项的系数:
    因为函数的阶数对函数的增长速度是最显著的,所以我们忽略与最高阶相乘的常数
    综上:如果一个算法的执行次数是T(n),那么只保留最高次项,同时忽略最高项的系数后得到函数f(n),此时算法的时间复杂度为O(f(n))。称为大O推导法。
    推倒大O阶方法
    用常数1取代运行时间中的所有加法常数
    在修改后的运行次数函数中,只保留最高阶项
    如果最高阶项存在且不是一,则去除与这个项相乘的常数
    所得到的结果就是大O阶

    O(1)<O(logn)<O(n)<O(nlogn)<O(n2)<O(n3)
    O(2n)<O(n!)<O(nn)

    在这里插入图片描述

    3.算法的存储空间需求

    算法的空间复杂度定义为:S(n)=O(g(n))
    表示随着问题规模n的增大,算法运行所需的存储量的增长率与g(n)的增长率相同

    算法的存储量:
    1.输入数据所占空间
    2.程序本身所占的空间
    3.辅助变量所占的额外空间

    ####总结(一)
    深刻理解数据结构的概念,掌握数据结构三要素:逻辑结构、物理(存储)结构及在这种结构上所定义的操作运算,掌握计算语句频度和估算算法时间的复杂度的方法
    要掌握一些经典算法的时间复杂度和空间复杂度

    展开全文
  • 文章目录算法与数据结构学习(一)1. 数据结构1.1 什么是数据结构1.2 学习数据结构的必要性2. 算法2.1 怎么衡量算法的好坏2.1.1 时间复杂度2.1.2 空间复杂度2.2 时间复杂度的计算2.3 常见的时间复杂度 算法与数据...

    算法与数据结构学习(一)数据结构基础

    1. 数据结构

    1.1 什么是数据结构

    数据结构是 具有一定关系的同一类数据元素的集合。

    书籍结构研究 数据的逻辑结果、数据的物理结构、数据之间的关系。

    1.2 学习数据结构的必要性

    了解数据结构,可以帮助我们理解数据在计算机中的存储形式。

    合理的使用数据结构,能提高程序的运行效率。

    2. 算法

    没有明确定义,每个人对算法的理解有不同,在我看来算法就是解决问题的一些步骤。

    2.1 怎么衡量算法的好坏

    时间复杂度用来度量 算法执行的时间
    空间复杂度用来度量 算法在执行时内存空间的占用

    随着技术的不断提升,一般牺牲空间来换取时间。

    2.1.1 时间复杂度

    • 计算方法

    事前估算法
    事后统计法

    一般的,事前估算法比较靠谱,因为事后统计法在不同的硬件基础或者环境下,统计的结果可能不同。

    • 时间频度T(n)

    算法语句的执行次数?

    • 时间复杂度O(n)

    • 最坏时间复杂度

    一般我们计算最坏时间复杂度

    • 平均时间复杂度

    了解下得了…

    2.1.2 空间复杂度

    度量算法执行时候占用的空间的大小。

    2.2 时间复杂度的计算

    • 时间频度推算时间复杂度

    例:for循环

    根据时间频度估算时间复杂度

    循环n次数,时间频度为 T(n)=n,时间复杂度O(n)=

    遵循原则:1.忽略常量项;2.忽略低次项;3.忽略系数;

    • 常见的时间复杂度

    常数阶O(1) 无循环
    对数阶O(log(2n))
    线性阶O(n)
    线性对数阶O(n(log(2n)))
    平方阶O(n^2)

    2.3 常见的时间复杂度

    在这里插入图片描述

    在这里插入图片描述

    在这里插入图片描述

    展开全文
  • 数据结构学习笔记:时间复杂度 1、大O函数 O —— Order of Magnitude —— 同阶 2、常用大O函数 3、常用大O函数图像 4、案例演示 a = 500 b = 600 c = 100 for i in range(n): for j in range(n): x...

    数据结构学习笔记:时间复杂度

    1、大O函数

    O —— Order of Magnitude —— 同阶

    2、常用大O函数

    3、常用大O函数图像

    4、案例演示

    a = 500
    b = 600
    c = 100
    for i in range(n):
       for j in range(n):
          x = i * i
          y = j * j
          z = i * j
    for k in range(n):
       w = a * k + 45
       v = b * b
    d = 250

                                

    5、课堂练习

    大家可以看到两种不同算法的差别,当列表长度为10000时,findMin01耗时是findMin02耗时的一万多倍。

    展开全文
  • 数据结构概述 定义: 我们如何把现实中大量而复杂的问题以特定的数据类型和特定的存储结构保存到主存储器(内存)中,以及在此基础上为实现某个功能(比如查找某个元素,删除某个元素,对所有元素进行排序)而执行的...

    数据结构概述

    定义:
    我们如何把现实中大量而复杂的问题以特定的数据类型和特定的存储结构保存到主存储器(内存)中,以及在此基础上为实现某个功能(比如查找某个元素,删除某个元素,对所有元素进行排序)而执行的相应操作,这个相应的操作也叫算法。

    数据结构 = 个体 + 个体的关系
    算法 = 对存储数据的操作

    算法:解题的方法和步骤
    衡量算法的标准:

    • 时间复杂度
      大概程序要执行的次数,而非执行的时间
    • 空间复杂度
      算法执行过程中大概所占用的最大内存
    • 难易程度
    • 健壮性

    预备知识:

    1. 指针

    地址:

    • 地址就是内存单元的编号
    • 从0开始的非负整数
    • 范围:0 —— FFFFFFF【0-4G-1】

    指针:
    指针就是地址,地址就是指针
    指针变量是存放内存单元地址的变量
    指针的本质是一个操作受限的非负整数

    int *p;
    &p==int **p;

    2. 结构体
    为什么会出现结构体

    • 为了表示一些复杂的数据,而普通的基本类型变量无法满足要求

    什么叫结构体

    • 结构体是用户根据实际需要自己定义的复合数据类型

    如何使用结构体
    两种方式:
    struct Student st={1000,“zhangsan”,20};
    struct Student *pst=&st;

    1. st.sid
    2. pst ->sid
      (pst所指向的结构体变量中的sid这个成员)
    #include <stdio.h>
    struct Student //struct Student是一种数据类型,包含sid、name、age三个成员
    {
      int sid;
      char name[200];
      int age;
    }; //分号不能省
    
    int main()
    {
      struct Student st={1000,"zhangsan",20}; //定义了一个变量st,包含学号、姓名、年龄三个成员数据
      printf("%d  %s  %d",st.sid,st.name,st.age); //用【结构体变量名.成员名】的方式输出成员数据
      return 0;
    }
    int main()
    {
      struct Student st ={1000,"zhangsan",20};
      // st.sid=99;//第一种方式
      
      struct Student *pst;
      pst=&st;  //第二种方式
      pst->sid=99; //pst->sid等价于(*pst).std  而(*pst).sid等价于st.sid,所以pst->sid等价于st.sid
    }

    注意事项
    结构体变量不能加减乘除,但可以相互赋值
    普通结构体变量和结构体指针变量作为函数传参的问题

    3. 动态内存的分配和释放
    (这个部分好难T-T,听的吃力)

    #include <stdio.h>
    #include <malloc.h>
    int main()
    {
      int a[5]={4,10,2,8,6};
    int len;
    printf("请输入你需要分配的数组的长度:len=");
    scanf("%d",&len);
    int *pArr=(int *)malloc(sizeof(int)*len);
    *pArr=4; //类似于a[0]=4
    pArr[1]=10; //类似于a[1]=10;
    printf("%d %d\n",*pArr,pArr[1]);
    free(pArr); //把pArr所代表的动态分配的20个字节的内存释放
    return 0;
    }

    数据结构

    模块一:线性结构

    • 连续存储 [数组]
    • 离散存储 [链表]
    • 线性结构的两种常见应用之一 栈
    • 线性结构的两种常见应用之一 队列

    专题:递归

    1. 1+2+3…+100的和
    2. 求阶乘
    3. 汉诺塔
    4. 走迷宫

    模块二:非线性结构

    模块三:查找和排序

    折半查找
    排序:

    • 冒泡
    • 插入
    • 选择
    • 快速排序
    • 归并排序

    Java中容器和数据结构相关知识
    Iterator接口
    Map
    哈希表

    展开全文
  • 数据结构学习有感

    2019-12-11 21:02:17
    学习的课本是 严蔚敏老师的《数据结构》(c语言版)。其实我数买了一段时间,但是一直摸有开始,原因很简单,看不懂结构体。经常看到一大堆莫名其妙的引用 访问什么的,瞬间头大。所以我就抽时间去吧结构体学了...
  • 数据结构学习心得

    千次阅读 2019-02-17 20:18:08
    任意一种数据结构都可以用数组来表示 解决问题的效率与数据组织的方式有关,这就是为什么要学习数据结构。 考虑算法,不仅要考虑时间复杂度还要考虑空间复杂度。  ...
  • 自从博主决定考研了以后,就很长一段时间没有再接触iOS,博客也很久没有写过博文了,最近自己一直在复习考研数据结构,想把自己复习的东西总结起来写成博客,供大家参考。数据结构的内容还是比较多的,有一些算法也...
  • 数据结构学习总结

    2017-12-14 11:25:09
    经过一学期的数据结构学习,一场别样的学习生涯让我收获颇丰(哎呀,好多资源啊都可以在圈里随时随地的瞅两眼了。)但是真正装在脑子里的少得可怜(一味的赶进度,但是你让我说几个专业名词,我每个都能说出来)。...
  • 数据结构学习

    2013-11-13 11:07:00
    我发现在学习数据结构的过程中每次都有这样的困惑,各种类型的书都看了一下,如果书上写的简单一点那么自己就会一带而过,如果书上数学公式算法分析一大堆,那真是不堪入眼,看的一点兴趣全无,以至于一道走来,简单...
  • 数据结构学习1

    2018-08-17 11:54:53
    什么是数据结构数据结构是研究数据与数据之间的关系,包含逻辑结构和物理结构。 算法:解决问题的方法,以数据结构为基础 算法的特点:准确性,健壮性,还有复用性,可扩展性 算法的效率衡量:时间复杂度,空间...
  • 数据结构学习笔记

    2017-09-08 12:11:43
    1.算法+数据结构=程序。 2.数据结构是介于数学、计算机硬件和人机之间的一门核心课程。 3.数据结构的研究内容:研究非数值计算的程序设计问题中计算机的操作对象,以及他们之间的关系和操作。 4.数据结构(Data ...
  • 数据结构基本概念算法基本概念时间复杂度空间复杂度线性表线性表的定义和基本操作线性表的顺序表示 数据机构概述 数据结构在学什么? 数据结构基本概念 算法基本概念 时间复杂度 空间复杂度 线性表 线性表的...
  • 数据结构学习笔记①

    2019-03-13 08:54:42
    数据结构学习笔记①时间复杂度和空间复杂度函数表达式相关时间复杂度空间复杂度其它 时间复杂度和空间复杂度 2019.3.13 参考资料: 数据结构与算法视频,小甲鱼 数据结构与算法教程,解学武,...
  • 数据结构学习顺序安排 数据结构学习顺序安排: c基础复习 函数 结构 动态内存开辟 衡量算法的标准:时间复杂度和空间复杂度 顺序表:定长顺序表 不定长顺序表 链表:单链表 双向链表 循环链表 (带头节点)不带头...
  • 解析:因为,数组可以通过下标直接定位到数据原素,无论数值的长度是多少(即:问题规模的扩大),均可以通过下标直接访问得到。所以,其时间复杂度为:O(1),呈固定的常数变化。 2、访问链表某个位置的值,其时间...
  • 数据结构学习日记

    2017-03-10 22:14:56
    在”中国大学MOOC“上看视频学习,视频是浙江大学陈越、何钦铭老师讲的数据结构。从2017年3月1日-5月31日,今天已经是开课的第二周,因为上周有点忙,所以到了现在才把第一周的视频看完并把习题做了。  期间,学习...
  • 数据结构学习之路一

    千次阅读 2019-04-19 19:50:59
    本狗再学习大数据之余同时还在学习数据结构,今天开始就记录一下数据结构学习过程。 先从栈和队列入手,语言选择Java,以后有时间本狗会更新python版本的,毕竟python更简洁。 栈:就不从书上的定义开始扯了,...
  • 数据结构学习心得体会

    万次阅读 2017-12-14 11:26:52
    时间转眼即逝,一转眼一学期的数据结构课就已经快要结束了,我对第一节课的时候老师向我们介绍云班课时的场景还历历在目,老师兴致勃勃的介绍着数据结构课的作用,重要性。老师每节课都充满活力让我们每节课都...
  • 然而,之前的数据结构学习都不够认真,没有学好。一直想好好重新温习下,却因为这样那样的原因没有实现。究其原因,不是因为缺少时间,也不是认识不到数据结构的重要性,而是平时用java编程,数据结构用的不多,所有...
  • 数据结构、算法总结、学习算法的时间复杂度、空间复杂度、分析算法特点以及应用、Java面试难题、Android面试难题
  • 学习数据结构

    2011-11-10 16:49:57
    数据结构学习   1、数据项:数据结构中最小单元 2、数据元素:由数据项构成 3、数据结构:带结构的数据元素的集合 4、算法的时间复杂度:由该算法中的核心计算所决定,其时间复杂度T(n) = Nm ,...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 12,329
精华内容 4,931
关键字:

数据结构学习时间

数据结构 订阅