数据结构与算法学习之 基础概念

@[TOC] 数据结构与算法学习之 基础概念

什么是数据结构?

数据结构：是指相互之间存在一种或多种特定关系的数据元素的集合用计算机存储、组织数据的方式。数据结构分别为逻辑结构、（存储）物理结构和数据的运算三个部分。

数据结构的主要任务是通过分析数据对象的结构特征，包括逻辑结构及数据对象之间的关系，然后把逻辑结构表示成计算机课实现的物理结构，从而便于计算机处理。

1.数据结构概念

（1）数据（Data）是能被计算机处理的符号或符号集合，含义广泛，可理解为“原材料”。如字符、图片、音视频等。

（2）数据元素（data element）是数据的基本单位。例如一张学生统计表。

（3）数据项（data item）组成数据元素的最小单位。例如一张学生统计表，有编号、姓名、性别、籍贯等数据项。

（4）数据对象（data object）是性质相同的数据元素的集合，是数据的一个子集。例如正整数N={1，2，3，····}。

（5）数据结构（data structure）是数据的组织形式，数据元素之间存在的一种或多种特定关系的数据元素集合。

（6）数据类型（data type）是按照数据值的不同进行划分的可操作性。在C语言中还可以分为原子类型和结构类型。原字类型是不可以再分解的基本类型，包括整型、实型、字符型等。结构类型是由若干个类型组合而成，是可以再分解的。

2.数据逻辑结构

1）集合结构：集合的数据元素没有其他关系，仅仅是因为他们挤在一个被称作“集合”的盒子里。

（2）线性结构：线性的数据元素结构关系是一对一的，并且是一种先后的次序，就像a-b-c-d-e-f-g·····被一根线穿连起来。

（3）树形结构：树形的数据元素结构关系是一对多的，这就像公司的部门级别，董事长-CEO\CTO-技术部\人事部\市场部…。

（4）图结构：图的数据元素结构关系是多对多的。就是我们常见的各大城市的铁路图，一个城市有很多线路连接不同城市。

3.算法

算法（algorithm）是解决特定问题求解步骤的描述，在计算机中表现为有限的操作序列。在数据类型建立起来之后，就要对这些数据类型进行操作，建立起运算的集合即程序。运算的建立、方法好坏直接决定着计算机程序原型效率的高低。

（1）数据结构和算法的关系

两者基友联系又有区别。联系是程序=算法+数据结构。数据结构是算法实现的基础，算法总是要依赖某种数据结构来实现的。算法的操作对象是数据结构。区别是数据结构关注的是数据的逻辑结构、存储结构有一集基本操作，而算法更多的是关注如何在数据结构的基本上解决实际问题。算法是编程思想，数据结构则是这些思想的基础。

算法的五大特性

有穷性，是指算法在执行有限的步骤之后，自动结束而不是出现无限循环，并且每一个步骤在可接受的时间内完成。

确定性，是指算法执行的每一步骤在一定条件下只有一条执行路径，也就是相同输入只能有一个唯一的输出结果。

可行性，是指算法每一步骤都必须可行，能够通过有限的执行次数完成。

输入，是指算法具有零个或多个输入。

输出，是指算法至少有一个或多个输出。

4.时间复杂度

在进行算法分析时，语句总是执行次数 T(n) 是关于问题规模 n 的函数。进而分析次数T(n)随规模n的变化情况并确定T(n)的数量级。算法的时间复杂度就是算法的时间度量，记作T(n) = O（f（n））。它表示随问题规模n的增大，算法的执行时间的增长率和f（n）的增长率相同，称作算法的渐进时间复杂度，简称为时间复杂度。其中，f（n）是问题规模n的某个函数。

算法的时间复杂度是衡量一个算法好坏的重要指标。一般情况下，随着规模n的增大，次数T(n)的增长较慢的算法为最优算法。常见时间复杂度从小到大依次排列：O(1) < O(log2n) < O(n) < O(n²）<O(n³) ····<O(n!)

5.空间复杂度

空间复杂度（space complexity）作为算法所需存储空间的量度，记做S(n) = O (f(n))。其中，n为问题的规模；f（n）为语句关于n的所占存储空间的函数。
一般情况下，一个程序在机器上运行时，除了需要存储程序本身的指令、常数、变量和输入数据外，还需要存储对数据操作的存储单位。若输入数据所占空间只取决于问题本身，和算法无关，这样只需要分析该算法在实现时所需的辅助单元即可。若算法执行时所需的辅助空间相对于输入数据量而言是个常量，则称此算法为原地工作，空间复杂度为O(1)。