美文网首页
数据结构与算法-基础篇

数据结构与算法-基础篇

作者: 收纳箱 | 来源:发表于2020-03-31 23:47 被阅读0次

1. 基础

1.1 数据结构基本术语

  • 数据:程序的操作对象,用于描述客观事物。
    • 可以输入到计算机。
    • 可以被计算机处理。
  • 数据对象:是性质相同的数据元素的集合,是数据的子集。如数组、集合等。
  • 数据元素:组成数据的对象的基本单位。例如,结构体、类等。
  • 数据项:一个数据元素由若干数据项组成。
//声明一个结构体类型
struct Teacher {     //一种数据结构
    char *name;     //数据项--名字
    char *title;    //数据项--职称
    int  age;       //数据项--年龄
};

struct Teacher t1;     //数据元素;
struct Teacher tArray[10]; //数据对象;
  • 结构:数据元素之间不是独立的,存在特定的关系。这些关系即是结构。
  • 数据结构:指的数据对象中的数据元素之间的关系。

1.2 逻辑结构与物理结构

根据逻辑和存储关系,我们将数据结构分为2种:逻辑结构与物理结构。

1.2.1 逻辑结构

逻辑结构:是数据对象中的数据元素之间的相互关系。逻辑结构分为四种:

  • 集合结构
    集合结构中的数据元素除了同属于一个集合外,它们之间没有其他关系。各个数据元素是"平等"的。
  • 线性结构
    线性结构中的数据元素之间是一对一的关系。
    常用的线性结构有:线性表、栈、队列、双队列、数组、串
  • 树形结构
    树型结构中的数据元素之间存在一种一对多的层次关系。
    常见的树形结构:二叉树、B树、哈夫曼树、红黑树等
  • 图形结构
    图形结构的数据元素是多对多的关系。
    常见的图形结构:邻近矩阵、邻接表

具体采用什么的数据结构,是需要根据实际业务需求来进行合理的设计。

1.2.2 物理结构

物理结构:又称“存储结构”,指的是数据的逻辑结构在计算机的存储形式。

数据存储结构应该正确反映数据元素之间的逻辑关系。如何存储数据元素之间的逻辑关系,是实现物理结构的重点和难点。

数据元素的存储结构形式有2种:

  • 顺序存储:把数据元素放在地址连续的存储单元里,其数据间的逻辑关系和物理关系是一致的。
  • 链式存储:把数据元素放在任意的存储单元里,这组存储单元可以是连续的,也可以是不连续的
    数据元素的存储关系并不能直接反映逻辑关系,因此需要用一个指针存放数据元素的地址,通过地址找到相关关联数据元素的位置。

2. 算法基础

算法:解决特定问题求解步骤的描述。在计算机中表现为指令的有限序列,并且每条指令表示一个或多个操作。

算法与数据结构的关系:数据结构如果脱离算法,或者算法脱离数据结构都是无法进行的。

算法的特性:

  • 输入输出:输入提供已知条件,输出产生结果。
  • 有穷性:执行有限的步骤之后,会自动结束。不会死循环。
  • 确定性:相同输入执行后,只有对应唯一的结果,不能有二义性。
  • 可行性:每一步都是可行的。每一步都能通过有限次数完成。

算法设计要求:

  • 正确性:能够得到正确答案。错误答案对于解决问题是没有意义的。
    • 没有语法错误。
    • 对于非法的输入数据能够正确报错。
    • 对于所有合法输入数据都应有正确的输出结果,包括边界情况等。
  • 健壮性:能对输入数据的不合法的情况做出合适的处理。
  • 时间效率高和存储量低:花最少的时间,用最少的存储空间,得到相同的结果。

2.1 复杂度

2.1.1 时间复杂度

时间复杂度:算法的时间复杂度是一个函数,它定性描述该算法的运行时间。这是一个代表算法输入值的字符串的长度的函数。时间复杂度常用大O符号表述,不包括这个函数的低阶项和首项系数。使用这种方式时,时间复杂度可被称为是渐近的,亦即考察输入值大小趋近无穷时的情况。

在考虑复杂度时,想象n→∞的情况,只保留n的最高阶,并移除常数项。

执⾏行行次数 函数阶 术语
12 O(1) 常数阶
2n+3 O(n) 线性阶
3n^2+2n+1 O(n^2) 平方阶
6n^3+2n^2+3n+4 O(n^3) 立方阶
5log2n+20 O(logn) 对数阶
2n+3nlog_2n+19 O(nlogn) nlog
2^n O(2^n) 指数阶

O(1) < O(log n) < O(n) < O(nlog n) < O(n^2) < O(n^3) < O(2^n) < O(n!) < O(n^n)

对于算法的分析:

  • 平均时间复杂度:计算所有情况的平均值。
  • 最坏时间复杂度:计算最坏的情况下时间复杂度。

注意:一般没有特殊情况下,都是指最坏时间复杂度。

2.2 空间复杂度

空间复杂度:通过计算算法所需的存储空间实现,算法空间复杂度的计算公式记做:S(n) = n(f(n)),其中,n为问题的规模,f(n)为语句关于n所占存储空间的函数。

除了需要寄存本身所用的指令、常数、变量和输入数据外,还需要一些对数据进行操作的辅助存储空间。
考量空间复杂度是,主要考虑算法执行时所需要的辅助空间

举例:数组逆序,将一维数组a中的n个数逆序存放在原数组中。

int n = 5;
int a[10] = {1,2,3,4,5,6,7,8,9,10};
/*
算法(1),仅仅通过借助一个临时变量temp,与问题规模n大小无关。
空间复杂度为O(1)。
*/
int temp;
for(int i = 0; i < n/2 ; i++){
    temp = a[i];
    a[i] = a[n-i-1];
    a[n-i-1] = temp;
}
for(int i = 0;i < 10;i++)
    printf("%d\n",a[i]);
/*
算法(2),借助一个大小为n的辅助数组b。
空间复杂度为O(n)。
*/
int b[10] = {0};
for(int i = 0; i < n;i++)
    b[i] = a[n-i-1];
for(int i = 0; i < n; i++)
    a[i] = b[i];
for (int i = 0;i < 10;i++)
    printf("%d\n",a[i]);

相关文章

  • 数据结构与算法-目录

    数据结构与算法-目录 C语言篇 数据结构和算法-C语言篇1-绪论数据结构和算法-C语言篇2-初识算法数据结构与算法...

  • 如何学习数据结构与算法

    算法学习经验 推荐: 入门: 数据结构启蒙:《数据结构与算法分析——C 语言描述》 算法启蒙:《算法设计与分析基础...

  • 编程基础 - 目录

    目录第一篇:1. java基础第二篇:2. 设计模式与架构第三篇:3. 算法与数据结构基础第四篇:4. 计算机基础...

  • 算法与数据结构

    数据结构 数据结构与算法分析_Java语言描述(第2版) 算法 计算机算法基础算法导论编程之法_面试和算法心得 c...

  • #算法与数据结构书籍

    数据结构 数据结构与算法分析_Java语言描述(第2版) 算法 计算机算法基础算法导论编程之法_面试和算法心得 c...

  • 数据结构 -- C++ STL中的数据结构与算法[2]

    数据结构 -- C++ STL中的数据结构与算法[2] 接前一篇 数据结构 -- C++ STL中的数据结构与算法...

  • 数据结构 & 算法 in Swift (一):Swift

    数据结构 & 算法 in Swift (一):Swift基础和数据结构 数据结构 & 算法 in Swift (一...

  • 数据结构与算法学习开篇

    数据结构与算法知识图谱 20个最常用的、最基础数据结构与算法 10个数据结构:数组、链表、栈、队列、散列表、二叉树...

  • Java数据结构与算法初级篇之数组、集合和散列表

    Java数据结构与算法初级篇之数组、集合和散列表> 数据是基础,算法是灵魂 本文出自门心叼龙的博客,属于原创类容,...

  • 数据结构与算法 - 查找

    数据结构与算法系列文章数据结构与算法 - 时间复杂度数据结构与算法 - 线性表数据结构与算法 - 树形结构数据结构...

网友评论

      本文标题:数据结构与算法-基础篇

      本文链接:https://www.haomeiwen.com/subject/xkmguhtx.html