数据结构 算法系列 基本概念和顺序列表

基础总结 12/06 阅读 4 views次 人气 0
摘要:

​数据结构是计算机存储、组织数据的方式。数据结构是指相互之间存在一种或多种特定关系的数据元素的集合。通常情况下,精心选择的数据结构可以带来更高的运行或者存储效率。数据结构往往同高效的检索算法和索引技术有关。

逻辑结构

简单说,逻辑结构就是数据之间的关系。而按数据之间的关系来说,逻辑结构大概可以分为两种:线性结构和非线性结构(集合、树、网)。

1、线性结构:有且只有一个开始结点和一个终端结点,并且所有结点都最多只有一个直接前驱和一个直接后继。例如:线性表,典型的线性表有:顺序表、链表、栈(顺序栈、链栈)和队列(顺序队列、链队列)。它们共同的特点就是数据之间的线性关系,除了头结点和尾结点之外,每个结点都有唯一的前驱和唯一的后继,也就是所谓的一对一的关系。

2、非线性结构:对应于线性结构,非线性结构也就是每个结点可以有不止一个直接前驱和直接后继。常见的非线性结构包括:树(二叉树)、图(网)等。

存储结构

逻辑结构指的是数据间的关系,而存储结构是逻辑结构的存储映像。通俗的讲,可以将存储结构理解为逻辑结构用计算机语言的实现。常见的存储结构有顺序存储、链式存储、索引存储以及散列存储(哈希表)。

1、顺序存储:把逻辑上相邻的节点存储在物理位置上相邻的存储单元中,结点之间的逻辑关系由存储单元的邻接关系来体现。由此得到的存储结构为顺序存储结构,通常顺序存储结构是借助于数组来描述的。优点:节省空间,可以实现随机存取;缺点:插入、删除时需要移动元素,效率低。

2、链式存储:在计算机中用一组任意的存储单元存储线性表的数据元素(这组存储单元可以是连续的,也可以是不连续的)。特点是元素在物理上可以不相邻,所以每个数据元素包括了一个数据域和一个指针域,数据域用来存放数据,而指针域用来指向其后继结点的位置。优点:插入、删除灵活;缺点:不能随机存取,查找速度慢。


算法的概念

算法(Algorithm)是指解题方案的准确而完整的描述,是一系列解决问题的清晰指令,算法代表着用系统的方法描述解决问题的策略机制。也就是说,能够对一定规范的输入,在有限时间内获得所要求的输出。如果一个算法有缺陷,或不适合于某个问题,执行这个算法将不会解决这个问题。不同的算法可能用不同的时间、空间或效率来完成同样的任务。一个算法的优劣可以用空间复杂度与时间复杂度来衡量。

程序好坏=时间复杂度+空间复杂度+具体的场景

时间复杂度

T(n)=Ο(f(n))

问题的规模n 越大,算法执行的时间的增长率与f(n) 的增长率正相关

下面两种算法的时间复杂度是相同的
function1() {
   for(int i = 0; i < n; i++) {
        for(int j = 0; j < n; j ++) {
        // dosomething;
        }   
    }

    for(int i = 0; i < n; i++) {
    //dosomething   
    }

   // dosomething
}

时间复杂度 O(n)= n^2+n+1  

function2() {
    for(int i = 0; i < n; i++) {
        for(int j = 0; j < n; j ++) {
          // dosomething;
        } 
}
时间复杂度 O(n) =n^2

空间复杂度

S(n)=O(f(n))

空间复杂度(SpaceComplexity)是对一个算法在运行过程中临时占用存储空间大小的量度

变量交换的三种方式
int a = 5;
int b = 6;
//第一种
int t = a;
a = b;
b = t;
// 第二种
a = a + b;
b = a - b;
a = a - b;
//第三种 性能最优,但可读性不强
a = a^b;
b = a^b;
a = a^b;


评论

表情

分享到: