WalkingSun

数据结构与算法【draft】

2019/02/27 数据结构 算法

为什么要学习数据结构

在计算机的世界中数据结构无处不在，操作系统在多任务间切换，运用到系统栈，优先队列：堆；比如通讯录就用到前缀树；撤销操作运用栈，消息队列运用队列等。数据结构是计算机的基础，设计如此多的数据结构能帮助解决实际遇到的问题，使用 好数据结构能提升软件的性能，为什么那么多计算机语言在不断的优化，迭代，其根本也是依赖于数据结构构建出优秀高性能的算法为基础。我们可以看到大厂都在自己写中间件，组件等，所以学习数据结构很重要，只是现在开发弱化了这些概念，好处 当然是入门很快，熟悉这些开发语言，框架就可以上手工作，但是往后面要想有所提升，还是得回到计算机基础上面。

时间复杂度

将算法中基本操作的执行次数作为算法的时间复杂度。时间复杂度不是执行完一段程序的总时间，而是其中基本操作的总次数。

计算一个算法时间复杂度的步骤如下： 1.确定算法中的基本操作，以及问题的规模。 2.根据基本操作执行情况计算出规模n的函数f(n)，并确定时间复杂度为T(n)=O(f(n)中增长最快的项/此项的系数)。

常用的各种时间复杂度大小的比较关系如下：

O(1)≤O(log2n)≤O(n)≤O(nlog2n)≤O(n2)≤O(n3)≤……≤O(nk)≤O(2n)

大O描述的是算法的运行时间和输入数据之间的关系。

<?php
 function sum($nums=[]){
    $sum=0;
    
    foreach($nums as $v){
        $sum +=$v;
    }
     return $sum;
}

O(n) n是nums中的元素个数，算法和n呈线性关系；


T = 2*n+2        O(n)      #忽略常数

T = 2000*n+10000 O(n)      #渐进时间复杂度

T = n*n+1000     O(n^2)    #描述n趋近于无穷的情况

T = 2*n*n+300n+100 O(n^2)

空间复杂度

算法的空间复杂度指算法在运行时所需存储空间的度量，主要考虑在算法运行过程中临时占用的存储空间的大小（和时间复杂度一样，以数量级的形式给出）。

数据结构

数据结构是指相互之间存在一种或多种特定关系的数据元素的集合。数据结构包括3方面的内容：逻辑结构，存储结构和对数据的运算

逻辑结构

对数据之间关系的描述，与数据存储结构无关，同一种逻辑结构有多种存储结构。通常有4类的逻辑结构： 1）集合结构 2）线性结构 3）树形结构 4）图状结构

示意图： image

集合是数据元素之间比较松散的一种结构，不做探讨，主要讨论下线性结构（表、栈、队、串等）和非线性结构两大类；

  1. 线性结构 线性结构是一个数据元素的有序（次序）集合。四个基本特征：
    • 集合中必存在唯一的一个“第一个元素”。
    • 集合中必存在唯一的一个“最后的元素”。
    • 除最后元素之外，其它数据元素均有唯一的“后继”。
    • 除第一元素之外，其它数据元素均有唯一的“前驱”。

数据据结构中线性结构指的是数据元素之间存在着“一对一”的线性关系的数据结构。如（a1,a2,a3,…..,an）,a1为第一个元素，an为最后一个元素，此集合即为一个线性结构的集合。

  1. 非线性结构 非线性结构 与线性结构不同，非线性结构中的结点存在着一对多的关系，它又可以细分为树形结构和图形结构。

物理结构

数据的物理结构又称为存储结构，是数据的逻辑结构在计算机中的表示（又称映像）。

在数据结构中有以下4种常用的存储方法。

  1. 顺序存储方法 顺序存储结构是存储结构类型中的一种，该结构是把逻辑上相邻的结点存储在物理位置上相邻的存储单元中，结点之间的逻辑关系由存储单元的邻接关系来体现。由此得到的存储结构为顺序存储结构，通常顺序存储结构式借助于计算机程序设计语言（例如C/C++）的数组来描述的。

  2. 链式存储方法 该方法不要求逻辑上相邻的结点在物理位置上亦相邻，结点间的逻辑关系是由附加的指针字段表示的。由此得到的存储表示称为链式存储结构，通常借助于计算机程序设计语言（例如C/C++）的指针类型来描述它。

  3. 索引存储方法 该方法在存储结点信息时除建立存储结点信息外，还建立附加的索引表来标识结点的地址。索引项的一般形式一般是<关键字，地址>。关键字标识唯一一个结点：地址作为指向结点的指针。

  4. 散列（或哈希）存储方法 该方法的基本思想是根据结点的关键字通过哈希函数直接计算出该结点的存储地址。这种存储方法本质上是顺序存储方法的扩展。

串和数组

栈和队列

树和二叉树

集合

承载元素的容器，但每个元素 都只能存在一次；能够快速实现去重的这个工作。

排序算法

排序是计算机程序设计中的一项重要操作，其功能是将一个数据元素集合或序列重新排列成一个按数据元素某个项值有序的序列。

https://www.cnblogs.com/onepixel/p/7674659.html

参考：

https://segmentfault.com/a/1190000002465832

Search

    Table of Contents