精华内容
下载资源
问答
  • 数据结构与算法学习笔记

    万次阅读 多人点赞 2018-09-25 13:55:49
    本文是王争老师的《算法与数据结构之美》的学习笔记,详细内容请看王争的专栏。有不懂的地方指出来,我做修改。 数据结构与算法思维导图 数据结构指的是“一组数据的存储结构”,算法指的是“操作数据的一组...

    本文是王争老师的《算法与数据结构之美》的学习笔记,详细内容请看王争的专栏 。有不懂的地方指出来,我做修改。

     

    数据结构与算法思维导图

    数据结构指的是“一组数据的存储结构”,算法指的是“操作数据的一组方法”。
    数据结构是为算法服务的,算法是要作用再特定的数据结构上的。

    最常用的数据结构预算法:

    • 数据结构:数组、链表、栈、队列、散列表、二叉树、堆、跳表、图、Tire树
    • 算法: 递归、排序、二分查找、搜索、哈希算法、贪心算法、分治算法、回溯算法、动态规划、字符串匹配算法

    1  算法的复杂度

    1.1大O复杂度表示法

     公式:

     

    T(n)表示代码执行的时间; n表示数据规模的大小; f(n) 表示每行代码执行的次数总和。因为这是一个公式, 所以用f(n)来表示。公式中的O,表示代码的执行时间T(n)与f(n)表达式成正比。

          所以,第一个例子中的T(n) = O(2n+2),第二个例子中的T(m) = 0(2n2 +2n+3)。这就是大O时间复杂度表示法。大O时间复杂度实际上并不具体表示代码真正的执行时间,而是表示代码执行时间随数据规模增长的变化趋势,所以,也叫作渐进时间复杂度(asymptotic time complexity),简称时间复杂度。

          当n很大时,你可以把它想象成10000、100000。 而公式中的低阶、常量、系数三部分并不左右增长趋势,所以都可以忽略。我们只需要记录-个最大量级就可以了,如果用大O表示法表示刚讲的那两段代码的时间复杂度,就可以记为: T(n) = O(n); T(n)= 0(n2)。
     

    1.2.复杂度分析法则

    1)单段代码看高频:比如循环。
    2)多段代码取最大:比如一段代码中有单循环和多重循环,那么取多重循环的复杂度。
    3)嵌套代码求乘积:比如递归、多重循环等
    4)多个规模求加法:比如方法有两个参数控制两个循环的次数,那么这时就取二者复杂度相加。

     

    1.3 时间复杂度分析

    • 只关注循环执行次数最多的一段代码
    • 加法法则:总复杂度等于量级最大的那段代码的复杂度
    • 乘法法则:嵌套代码的复杂度等于嵌套内外代码复杂度的乘积

    1.4 几种常见时间复杂度实例分析

    多项式阶:随着数据规模的增长,算法的执行时间和空间占用,按照多项式的比例增长。包括,
    O(1)(常数阶)、O(logn)(对数阶)、O(n)(线性阶)、O(nlogn)(线性对数阶)、O(n^2)(平方阶)、O(n^3)(立方阶)
    非多项式阶:随着数据规模的增长,算法的执行时间和空间占用暴增,这类算法性能极差。包括,
    O(2^n)(指数阶)、O(n!)(阶乘阶)

    • O(1) :

    常量级时间复杂度,只要代码的执行时间不随 n 的增大而增长,这样代码的时间复杂度我们都记作 O(1)。

    • O(logn)、O(nlogn)
    i=1;
    while(i<=n) {
        i = i*2;
    }

    x=log2n,所以,这段代码的时间复杂度就是 O(log2n)

    • O(m+n)、O(m*n)

     

       int cal(int m, int n) {
          int sum_1=0;
          int i=1;
          for(;i<m;++i){
             sum_1 = sum_1 + i;
          }
          int sum_2 = 0;
          int j=1;
          for (;j<n;++j){
             sum_2 = sum_2 + j;
          }
          return sum_1 + sum_2;
       }

    从代码中可以看出,m和n是表示两个数据规模。我们无法事先评估m和n谁的量级大,所以我们在表示复杂度的时候,就不能简单地利用加法法则,省略掉其中一个。所以,上面代码的时间复 杂度就是0(m+n)。

    针对这种情况,原来的加法法则就不正确了,我们需要将加法规则改为: T1(m) + T2(m) = O(f(m) + g(n))。但是乘法法则继续有效: T1(m)*T2(n) = O(f(m) * f(n))。

    1.5 空间复杂度分析

    表示算法的存储空间与数据规模之间的增长关系。

    void print(int n) {
        inti=0;
        int[] a = new int[n];
        for (i; i <n; ++i) {
            a[i] =i* i;
        }
        for(i=n-1;i>=0;--i){
            print out a[i]
        }
    }

    跟时间复杂度分析一样,我们可以看到,第2行代码中,我们申请了一个空间存储变量i,但是它是常最阶的,跟数据规模n没有关系,所以我们可以忽略。第3行申请了一个大小为n的int类型数组,除此之外,剩下的代码都没有占用更多的空间,所以整段代码的空间复杂度就是O(n)。

    我们常见的空间复杂度就是O(1)、O(n)、 O(n2), 像O(logn)、O(nlogn) 这样的对数阶复杂度平时都用不到。而且,空间复杂度分析比时间复杂度分析要简单很多。所以,对于空间复杂度,掌握刚我说的这些内容已经足够了。

    1.6 复杂度增长趋势图:

    最好情况时间复杂度、最坏时间复杂度、平均情況时间复杂度、均摊时间复杂度。

    一、复杂度分析的4个概念
    1.最坏情况时间复杂度:代码在最坏情况下执行的时间复杂度。
    2.最好情况时间复杂度:代码在最理想情况下执行的时间复杂度。
    3.平均时间复杂度:代码在所有情况下执行的次数的加权平均值。
    4.均摊时间复杂度:在代码执行的所有复杂度情况中绝大部分是低级别的复杂度,个别情况是高级别复杂度且发生具有时序关系时,可以将个别高级别复杂度均摊到低级别复杂度上。基本上均摊结果就等于低级别复杂度。

    二、为什么要引入这4个概念?
    1.同一段代码在不同情况下时间复杂度会出现量级差异,为了更全面,更准确的描述代码的时间复杂度,所以引入这4个概念。
    2.代码复杂度在不同情况下出现量级差别时才需要区别这四种复杂度。大多数情况下,是不需要区别分析它们的。

    三、如何分析平均、均摊时间复杂度?
    1.平均时间复杂度
    代码在不同情况下复杂度出现量级差别,则用代码所有可能情况下执行次数的加权平均值表示。
    2.均摊时间复杂度
    两个条件满足时使用:1)代码在绝大多数情况下是低级别复杂度,只有极少数情况是高级别复杂度;2)低级别和高级别复杂度出现具有时序规律。均摊结果一般都等于低级别复杂度。

    1、数组

    线性表:   线性表就是数据排成像一条线一样的结构.每个现行表上的数据最多只有前和后两个方向.常见的线性表结构:数组,链表、队列、栈等。

     

    什么是数组:

    1.  数组(Array)是一种线性表数据结构。它用一组连续的内存空间,来存储一组具有相同类型的数据
    2.  连续的内存空间和相同类型的数据(随机访问的前提)
    3. 优点:两限制使得具有随机访问的特性缺点:删除,插入数据效率低
    • 数组怎么根据下标随机访问的?

    通过寻址公式:a[i]_address = base_address + i * data_type_size
    其中data_type_size表示数组中每个元素的大小,base_address 是首元素地址,i数组下标。

     

    为何数组插入和删除低效:

    插入:
    若有一元素想往int[n]的第k个位置插入数据,需要在k-n的位置往后移。
    最好情况时间复杂度 O(1)

    如果数组中的数据不是有序的,也就是无规律的情况下,可以直接把第k个位置上的数据移到最后,然后将插入的数据直接放在第k个位置上。

    最坏情况复杂度为O(n)


    平均负责度为O(n)

    2. 低效的插入和删除
    1) 插入:从最好O(1) 最坏O(n) 平均O(n)
    2) 插入:数组若无序,插入新的元素时,可以将第K个位置元素移动到数组末尾,把心的元素,插入到第k个位置,此处复杂度为O(1)。
    3) 删除:从最好O(1) 最坏O(n) 平均O(n)
    4) 多次删除集中在一起,提高删除效率
    记录下已经被删除的数据,每次的删除操作并不是搬移数据,只是记录数据已经被删除,当数组没有更多的存储空间时,再触发一次真正的删除操作。即JVM标记清除垃圾回收算法。

     

    2、链表

    • 什么是链表

    1.和数组一样,链表也是一种线性表。
    2.从内存结构来看,链表的内存结构是不连续的内存空间,是将一组零散的内存块串联起来,从而进行数据存储的数据结构。
    3.链表中的每一个内存块被称为节点Node。节点除了存储数据外,还需记录链上下一个节点的地址,即后继指针next。

     

    • 链表的特点

    1.插入、删除数据效率高O(1)级别(只需更改指针指向即可),随机访问效率低O(n)级别(需要从链头至链尾进行遍历)。


    2.和数组相比,内存空间消耗更大,因为每个存储数据的节点都需要额外的空间存储后继指针。

    • 常用链表

    1.单链表


    1)每个节点只包含一个指针,即后继指针。
    2)单链表有两个特殊的节点,即首节点和尾节点。为什么特殊?用首节点地址表示整条链表,尾节点的后继指针指向空地址null。
    3)性能特点:插入和删除节点的时间复杂度为O(1),查找的时间复杂度为O(n)。

     

    2.循环链表


    1)除了尾节点的后继指针指向首节点的地址外均与单链表一致。
    2)适用于存储有循环特点的数据,比如约瑟夫问题。

     

    3.双向链表


    1)节点除了存储数据外,还有两个指针分别指向前一个节点地址(前驱指针prev)和下一个节点地址(后继指针next)。
    2)首节点的前驱指针prev和尾节点的后继指针均指向空地址。
    3)性能特点:
    和单链表相比,存储相同的数据,需要消耗更多的存储空间。
    插入、删除操作比单链表效率更高O(1)级别。以删除操作为例,删除操作分为2种情况:给定数据值删除对应节点和给定节点地址删除节点。对于前一种情况,单链表和双向链表都需要从头到尾进行遍历从而找到对应节点进行删除,时间复杂度为O(n)。对于第二种情况,要进行删除操作必须找到前驱节点,单链表需要从头到尾进行遍历直到p->next = q,时间复杂度为O(n),而双向链表可以直接找到前驱节点,时间复杂度为O(1)。
    对于一个有序链表,双向链表的按值查询效率要比单链表高一些。因为我们可以记录上次查找的位置p,每一次查询时,根据要查找的值与p的大小关系,决定是往前还是往后查找,所以平均只需要查找一半的数据。

    4.双向循环链表:

    首节点的前驱指针指向尾节点,尾节点的后继指针指向首节点。

    • 选择数组还是链表?

    1.插入、删除和随机访问的时间复杂度
    数组:插入、删除的时间复杂度是O(n),随机访问的时间复杂度是O(1)。
    链表:插入、删除的时间复杂度是O(1),随机访问的时间复杂端是O(n)。

    2.数组缺点
    1)若申请内存空间很大,比如100M,但若内存空间没有100M的连续空间时,则会申请失败,尽管内存可用空间超过100M。
    2)大小固定,若存储空间不足,需进行扩容,一旦扩容就要进行数据复制,而这时非常费时的。
    3.链表缺点
    1)内存空间消耗更大,因为需要额外的空间存储指针信息。
    2)对链表进行频繁的插入和删除操作,会导致频繁的内存申请和释放,容易造成内存碎片,如果是Java语言,还可能会造成频繁的GC(自动垃圾回收器)操作。
    4.如何选择?
    数组简单易用,在实现上使用连续的内存空间,可以借助CPU的缓冲机制预读数组中的数据,所以访问效率更高,而链表在内存中并不是连续存储,所以对CPU缓存不友好,没办法预读。
    如果代码对内存的使用非常苛刻,那数组就更适合。

    • 应用

    1.如何分别用链表和数组实现LRU缓冲淘汰策略?
    1)什么是缓存?
    缓存是一种提高数据读取性能的技术,在硬件设计、软件开发中都有着非广泛的应用,比如常见的CPU缓存、数据库缓存、浏览器缓存等等。
    2)为什么使用缓存?即缓存的特点
    缓存的大小是有限的,当缓存被用满时,哪些数据应该被清理出去,哪些数据应该被保留?就需要用到缓存淘汰策略。
    3)什么是缓存淘汰策略?
    指的是当缓存被用满时清理数据的优先顺序。
    4)有哪些缓存淘汰策略?
    常见的3种包括先进先出策略FIFO(First In,First Out)、最少使用策略LFU(Least Frenquently Used)、最近最少使用策略LRU(Least Recently Used)。
    5)链表实现LRU缓存淘汰策略
    当访问的数据没有存储在缓存的链表中时,直接将数据插入链表表头,时间复杂度为O(1);当访问的数据存在于存储的链表中时,将该数据对应的节点,插入到链表表头,时间复杂度为O(n)。如果缓存被占满,则从链表尾部的数据开始清理,时间复杂度为O(1)。
    6)数组实现LRU缓存淘汰策略
    方式一:首位置保存最新访问数据,末尾位置优先清理
    当访问的数据未存在于缓存的数组中时,直接将数据插入数组第一个元素位置,此时数组所有元素需要向后移动1个位置,时间复杂度为O(n);当访问的数据存在于缓存的数组中时,查找到数据并将其插入数组的第一个位置,此时亦需移动数组元素,时间复杂度为O(n)。缓存用满时,则清理掉末尾的数据,时间复杂度为O(1)。
    方式二:首位置优先清理,末尾位置保存最新访问数据
    当访问的数据未存在于缓存的数组中时,直接将数据添加进数组作为当前最有一个元素时间复杂度为O(1);当访问的数据存在于缓存的数组中时,查找到数据并将其插入当前数组最后一个元素的位置,此时亦需移动数组元素,时间复杂度为O(n)。缓存用满时,则清理掉数组首位置的元素,且剩余数组元素需整体前移一位,时间复杂度为O(n)。(优化:清理的时候可以考虑一次性清理一定数量,从而降低清理次数,提高性能。)
    2.如何通过单链表实现“判断某个字符串是否为水仙花字符串”?(比如 上海自来水来自海上)
    1)前提:字符串以单个字符的形式存储在单链表中。
    2)遍历链表,判断字符个数是否为奇数,若为偶数,则不是。
    3)将链表中的字符倒序存储一份在另一个链表中。
    4)同步遍历2个链表,比较对应的字符是否相等,若相等,则是水仙花字串,否则,不是。
    六、设计思想
    时空替换思想:“用空间换时间” 与 “用时间换空间”
    当内存空间充足的时候,如果我们更加追求代码的执行速度,我们就可以选择空间复杂度相对较高,时间复杂度小相对较低的算法和数据结构,缓存就是空间换时间的例子。如果内存比较紧缺,比如代码跑在手机或者单片机上,这时,就要反过来用时间换空间的思路。

     

     

    3、队列

     

    什么是队列:

    队列是一种受限的线性表数据结构,只支持两个操作:入栈push()和出栈pop0,队列跟非常相似,支持的操作也 ,很有限,最基本的操作也是两个:入队enqueue(),放一个数据到队列尾部;出队dequeue0),从队列头部取一个元素。

    特点:

    1 . 队列跟栈一样,也是一种抽象的数据结构。

    2. 具有先进先出的特性,支持在队尾插入元素,在队头删除元素。

     

    实现:

    队列可以用数组来实现,也可以用链表来实现。

    用数组实现的队列叫作顺序队列,用链表实现的队列叫作链式队列。

     

    基于数组的队列:

    实现思路:

    实现队列需要两个指针:一个是head指针,指向队头;一个是tail指针,指向队尾。你可以结合下面这幅图来理解。当a,b,c,d依次入队之后,队列中的head指针指向下标为0的位置, tail指针指向下标为4的位置。

    当我们调用两次出队操作之后,队列中head指针指向下标为2的位置, tail指针仍然指向下标为4的位置.

    随着不停地进行入队、出队操作, head和tail都会持续往后移动。当tail移 . ,动到最右边,即使数组中还有空闲空间,也无法继续往队列中添加数据了。这个问题该如何解决呢?

    在出队时可以不用搬移数据。如果没有空闲空间了,我们只需要在入队时,再集中触 ,发一次数据的搬移操作。

    当队列的tail指针移动到数组的最右边后,如果有新的数据入队,我们可以将 head到tail之间的数据,整体搬移到数组中0到tail-head的位置。

    基于链表的实现: 

    需要两个指针: head指针和tail指针,它们分别指向链表的第一个结,点和最后一个结点。

    如图所示,入队时, tail->next= new node, tail = tail->next:出队时, head = head->next.

     

    循环队列:

    我们刚才用数组来实现队列的时候,在tail==n时,会有数据搬移操作,这样入队操作性能就会受到影响。那有没有办法能够避免数据搬移呢?我们来看看循环队列的解决思路。循环队列,顾名思义,它长得像一个环。原本数组是有头有尾的,是一条直线。现在我们把首尾相,连,板成了一个环。我画了一张图,你可以直观地感受一下。

    我们可以看到,图中这个队列的大小为8,当前head-4, tail-7,当有一个新的元素a入队时, .我们放入下标为7的位置。但这个时候,我们并不把tail更新为8,而是将其在环中后移一位,到下标为0的位置。当再有一个元素b入队时,我们将b放入下标为0的位置,然后tail加1更新为1,所以,在a, b依次入队之后,循环队列中的元素就变成了下面的样子:

    队列为空的判断条件是head == tail,但队列满的判断条件就稍微有点复杂了。我画了一张队列满的图,你可以看一下,试着总结一下规律,

    就像我图中画的队满的情况, tail=3, head-4, n=8,所以总结一下规律就是: (3+1)%8-4,多画几张队满的图,你就会发现,当队满时, (tail+1)%n=head..你有没有发现,当队列满时,图中的tail指向的位置实际上是没有存储数据的。所以,循环队列会浪费一个数组的存储空间。

    解决浪费一个存储空间的思路:定义一个记录队列大小的值size,当这个值与数组大小相等时,表示队列已满,当tail达到最底时,size不等于数组大小时,tail就指向数组第一个位置。当出队时,size—,入队时size++

    阻塞队列和并发队列(应用比较广泛)

    阻塞队列其实就是在队列基础上增加了阻塞操作。

    简单来说,就是在队列为空的时候,从队头取数 , 据会被阻塞。因为此时还没有数据可取,直到队列中有了数据才能返回;如果队列已经满了,那么插入数据的操作就会被阻塞,直到队列中有空闲位置后再插入数据,然后再返回。

    你应该已经发现了,上述的定义就是一个"生产者-消费者模型" !是的,我们可以使用阻塞队列,轻松实现一个"生产者-消费者模型" !这种基干阴寒队列实现的"生产者-消费者模型" ,可以有效地协调生产和消费的速度。当"生产 , 者"生产数据的速度过快, "消费者"来不及消费时,存储数据的队列很快就会满了。这个时候,生产者就阻塞等待,直到"消费者"消费了数据, "生产者"才会被唤醒继续"生产而且不仅如此,基于阻塞队列,我们还可以通过协调"生产者"和"消费者"的个数,来提高数据,的处理效率。比如前面的例子,我们可以多配置几个"消费者" ,来应对一个"生产者"

     

    小结:

    队列最大的特点就是先进先出,主要的两个操作是入队和出队。

    它既可以用数组来实现,也可以用链表来实现。用数组实现的叫顺序队列,用链表实现的叫链式队列。

    长在数组实现队列的时候,会有数据搬移操作,要想解决数据搬移的问题,我们就,需要像环一样的循环队列。要想写出没有bug的循环队列实现代码,关键要确定好队空和队满的,判定条件。

    阻塞队列、并发队列,底层都还是队列这种数据结构,只不过在之上附加了很多其他功能。阻塞队列就是入队、出队操作可以阴寒,并发队列就是队列的操作多线程安全。

     

    4、递归算法

     

    一、什么是递归?

    1.递归是一种非常高效、简洁的编码技巧,一种应用非常广泛的算法,比如DFS深度优先搜索、前中后序二叉树遍历等都是使用递归。
    2.方法或函数调用自身的方式称为递归调用,调用称为递,返回称为归。
    3.基本上,所有的递归问题都可以用递推公式来表示,比如
    f(n) = f(n-1) + 1; 
    f(n) = f(n-1) + f(n-2);
    f(n)=n*f(n-1);

    二、为什么使用递归?递归的优缺点?

    1.优点:代码的表达力很强,写起来简洁。
    2.缺点:空间复杂度高、有堆栈溢出风险、存在重复计算、过多的函数调用会耗时较多等问题。

    三、什么样的问题可以用递归解决呢?

    一个问题只要同时满足以下3个条件,就可以用递归来解决:
    1.问题的解可以分解为几个子问题的解。何为子问题?就是数据规模更小的问题。
    2.问题与子问题,除了数据规模不同,求解思路完全一样
    3.存在递归终止条件

    四、如何实现递归?

    1.递归代码编写
    写递归代码的关键就是找到如何将大问题分解为小问题的规律,并且基于此写出递推公式,然后再推敲终止条件,最后将递推公式和终止条件翻译成代码。
    2.递归代码理解
    对于递归代码,若试图想清楚整个递和归的过程,实际上是进入了一个思维误区。
    那该如何理解递归代码呢?如果一个问题A可以分解为若干个子问题B、C、D,你可以假设子问题B、C、D已经解决。而且,你只需要思考问题A与子问题B、C、D两层之间的关系即可,不需要一层层往下思考子问题与子子问题,子子问题与子子子问题之间的关系。屏蔽掉递归细节,这样子理解起来就简单多了。
    因此,理解递归代码,就把它抽象成一个递推公式,不用想一层层的调用关系,不要试图用人脑去分解递归的每个步骤。

    递归的关键是终止条件
    五、递归常见问题及解决方案

    1.警惕堆栈溢出:可以声明一个全局变量来控制递归的深度,从而避免堆栈溢出。
    2.警惕重复计算:通过某种数据结构来保存已经求解过的值,从而避免重复计算。

    六、如何将递归改写为非递归代码?

    笼统的讲,所有的递归代码都可以改写为迭代循环的非递归写法。如何做?抽象出递推公式、初始值和边界条件,然后用迭代循环实现。

    5、排序



    一、排序方法与复杂度归类
    (1)几种最经典、最常用的排序方法:冒泡排序、插入排序、选择排序、快速排序、归并排序、计数排序、基数排序、桶排序。
    (2)复杂度归类
    冒泡排序、插入排序、选择排序 O(n^2)
    快速排序、归并排序 O(nlogn)
    计数排序、基数排序、桶排序 O(n)

    二、如何分析一个“排序算法”?
    <1>算法的执行效率
    1. 最好、最坏、平均情况时间复杂度。
    2. 时间复杂度的系数、常数和低阶。
    3. 比较次数,交换(或移动)次数。
    <2>排序算法的稳定性
    1. 稳定性概念:如果待排序的序列中存在值相等的元素,经过排序之后,相等元素之间原有的先后顺序不变。
    2. 稳定性重要性:可针对对象的多种属性进行有优先级的排序。
    3. 举例:给电商交易系统中的“订单”排序,按照金额大小对订单数据排序,对于相同金额的订单以下单时间早晚排序。用稳定排序算法可简洁地解决。先按照下单时间给订单排序,排序完成后用稳定排序算法按照订单金额重新排序。
    <3>排序算法的内存损耗
    原地排序算法:特指空间复杂度是O(1)的排序算法。

    常见的排序算法:

     


    冒泡排序


    冒泡排序只会操作相邻的两个数据。每次冒泡操作都会对相邻的两个元素进行比较,看是否满足大小关系要求,如果不满足就让它俩互换。

    代码:

      public int[] bubbleSort(int[] a) {
            int n = a.length;
            if (n<=1) {
                return a;
            }
            for (int i = 0; i < n; i++) {
                //提前退出冒泡循环的标志
                boolean flag = false;
                for (int j = 0; j < n-i-1; j++) {
                    if (a[j]>a[j+1]) {//
                        int temp = a[j];
                        a[j] = a[j+1];
                        a[j+1] = temp;
    
                        flag = true;//表示有数据交换
                    }
                    if (!flag) {
                        break; //没有数据交换(说明已排好序无需再进行冒泡),提前退出
                    }
                }
            }
            return a;
        }


    四、插入排序


    插入排序将数组数据分成已排序区间和未排序区间。初始已排序区间只有一个元素,即数组第一个元素。在未排序区间取出一个元素插入到已排序区间的合适位置,直到未排序区间为空。

    代码:

        public int[] insertionSort(int[] a) {
    		int n = a.length;
    		if (n<=1) return a;
    		
    		for (int i = 1; i < n; i++) {
    			int value = a[i];
    			int j = i-1;
    			for (; j >=0; j--) {
    				if (a[j] > value) {
    					a[j+1] = a[j];//移动数据
    				}else {
    					break;
    				}
    			}
    			a[j+1] = value;//插入数据
    		}
    		
    		return a;
    	}


    五、选择排序


    选择排序将数组分成已排序区间和未排序区间。初始已排序区间为空。每次从未排序区间中选出最小的元素插入已排序区间的末尾,直到未排序区间为空。
    代码:

    public int[] selectionSort(int[] a) {
    		int n = a.length;
    		
    		for (int i = 0; i < a.length - 1; i++) {
    			for (int j = i+1; j < a.length; j++) {
    				//交换
    				if (a[i] > a[j]) {
    					int temp = a[i];
    					a[i] = a[j];
    					a[j] = temp;
    				}
    			}
    		}
    		
    		return a;
    	}

    六、归并排序

    如果要排序一个数组,我们先把数组从中间分成前后两部分,然后对前后两部分分别排序,再将排好序的两部分合并在一起,这样整个数组就都有序了。

     实现思路:

    merge-sort(p...r)表示,给下标从p到r之间的数组排序。我们将这个排序问题转化为了两个子问 ,题, merge_sort(p...q)和merge-sort(q+1..r),其中下标q等于p和r的中间位置,也就是, (p+r)/2,当下标从p到q和从q+1到r这两个子数组都排好序之后,我们再将两个有序的子数组合并在一起,这样下标从p到r之间的数据就也排好序了。

    代码:

     // 归并排序算法, a是数组,n表示数组大小
      public static void mergeSort(int[] a, int n) {
        mergeSortInternally(a, 0, n-1);
      }
    
      // 递归调用函数
      private static void mergeSortInternally(int[] a, int p, int r) {
        // 递归终止条件
        if (p >= r) return;
    
        // 取p到r之间的中间位置q
        int q = (p+r)/2;
        // 分治递归
        mergeSortInternally(a, p, q);
        mergeSortInternally(a, q+1, r);
    
        // 将A[p...q]和A[q+1...r]合并为A[p...r]
        merge(a, p, q, r);
      }
    
      private static void merge(int[] a, int p, int q, int r) {
        int i = p;
        int j = q+1;
        int k = 0; // 初始化变量i, j, k
        int[] tmp = new int[r-p+1]; // 申请一个大小跟a[p...r]一样的临时数组
       
        // 1 排序
        while (i<=q && j<=r) {
          if (a[i] <= a[j]) {
            tmp[k++] = a[i++]; // i++等于i:=i+1
          } else {
            tmp[k++] = a[j++];
          }
        }
    
        // 2 判断哪个子数组中有剩余的数据
        int start = i;
        int end = q;
        if (j <= r) {
          start = j;
          end = r;
        }
    
        // 3 将剩余的数据拷贝到临时数组tmp
        while (start <= end) {
          tmp[k++] = a[start++];
        }
    
        // 4 将tmp中的数组拷贝回a[p...r]
        for (i = 0; i <= r-p; ++i) {
          a[p+i] = tmp[i];
        }
      }
    

    merge是这样执行的:

    代码分析:

     

     

     

    七、快速排序

    快排的思想:    如果要排序数组中下标从p到r之间的一组数据,我们选择p到r之间的任意一个数据作为pivot (分区点) 。我们遍历p到r之间的数据,将小于pivot的放到左边,将大于pivot的放到右边,将pivot放到中间。经过这一步骤之后,数组p到r之间的数据就被分成了三个部分,前面p到q-1之间都是小于pivot的,中间是pivot,后面的q+1到r之间是大于pivot的。

    快排利用的分而治之的思想

     

    八、线性排序:

    时间复杂度O(n)

    我们把时间复杂度是线性的排序算法叫作线性排序(Linear sort)常见的线性算法有: 桶排序、计数排序、基数排序

    特点:

    非基于比较的排序算法 

     

    桶排序

     

    桶排序,顾名思义,会用到“桶" ,核心思想是将要排序的数据分到几个有序的桶里,每个桶里的数据再单独进行排序。桶内排完序之后,再把每个桶里的数据按照顺序依次取出,组成的序列就是有序的了。

    对排序的数据要求苛刻:

    1, 要排序的数据需要很容易就能划分成m个桶,并且,桶与桶之间有着天然的大小顺序。

    2 ,数据在各个桶之间的分布是比较均匀的。

    3 ,桶排序比较适合用在外部排序中。所谓的外部排序就是数据存储在外部磁盘中,数据量比较大,内存有限,无法将数据全部加载到内存中。

     

     

    计数排序

    计数排序只能用在数据范围不大的场景中,如果数据范围k比要排序的数据n大很多,就不适合用计数排序了。

    计数排序只能给非负整数排序,如果要排序的数据是其他类型的,要将其在不改变相对大小的情况下,转化为非负整数。

    代码:

     // 计数排序,a是数组,n是数组大小。假设数组中存储的都是非负整数。
      public static void countingSort(int[] a) {
    	int n = a.length;
        if (n <= 1) return;
    
        // 查找数组中数据的范围
        int max = a[0];
        for (int i = 1; i < n; ++i) {
          if (max < a[i]) {
            max = a[i];
          }
        }
    
        // 申请一个计数数组c,下标大小[0,max]
        int[] c = new int[max + 1];
        for (int i = 0; i < max + 1; ++i) {
          c[i] = 0;
        }
    
        // 计算每个元素的个数,放入c中
        for (int i = 0; i < n; ++i) {
          c[a[i]]++;
        }
    
        // 依次累加
        for (int i = 1; i < max + 1; ++i) {
          c[i] = c[i-1] + c[i];
        }
    
        // 临时数组r,存储排序之后的结果
        int[] r = new int[n];
        // 计算排序的关键步骤了,有点难理解
        for (int i = n - 1; i >= 0; --i) {
          int index = c[a[i]]-1;
          r[index] = a[i];
          c[a[i]]--;
        }
    
        // 将结果拷贝会a数组
        for (int i = 0; i < n; ++i) {
          a[i] = r[i];
        }
      }

    散列表

    什么是散列表:

    散列表用的是数组支持按照下标随机访问数据的特性,所以散列表其实就是数组的一种扩展,由数组演化而来。可以说,如果没有数组,就没有散列表。

    原理:

    散列表用的就是数组支持按照下标随机访问的时候,时间复杂度是0(1)的特性。我们通过散列函数把元素的键值映射为下标,然后将数据存储在数组中对应下标的位置。当我们按照键值查询元素时,我们用同样的散列函数,将键值转化数组标标,从对应的数组下标的位置取数据。

    散列函数的设计要求:

    1. 散列函数计算得到的散列值是一个非负整数;.
    2. 如果key1 = key2,那hash(key1) == hash(key2);
    3. 如果key1 != key2,那hash(key1)  !=  hash(key2),

    散列函数的设计不能太复杂,散列函数生成值要尽可能随机并且均匀分布

    如果不符合3 那么就出现了散列冲突,散列冲突是无法避免的

    解决散列冲突的方法有两种: 

    开放寻址法(open addressing)和链表法(chaining)

    开放寻址法:如果出现了散列冲突,我们就重新探测一个空闲位置,将其插入。

    装在因子:  散列表中一定比例的空闲槽位。公式: 散列表的装载因子 = 填入表中的元素个数 / 散列表的长度

    装载因子越大,说明空闲位置越少,冲突越多,散列表的性能会下降。

    链表法:

    链表法是一种更加常用的散列冲突解决办法,相比开放寻址法,它要简单很多。我们来看这个图,在散列表中,每个"桶(bucket) "或者"槽(slot) "会对应一条链表,所有散列值相同的元素我们都放到相同槽位对应的链表中。

     

     

    展开全文
  • 算法与数据结构】—— 并查集

    万次阅读 多人点赞 2020-03-26 20:29:47
    并查集的主要作用是求连通分支数(如果一个图中所有点都存在可达关系(直接或间接相连),则此图的连通分支数为1;如果此图有两大子图各自全部可达,则此图的连通分支数为2……) 问题引入 话说江湖上散落...

    并查集



    1. 概论

    定义:
    并查集是一种树型的数据结构,用于处理一些不相交集合的合并及查询问题(即所谓的并、查)。比如说,我们可以用并查集来判断一个森林中有几棵树、某个节点是否属于某棵树等。

    主要构成:
    并查集主要由一个整型数组pre[ ]和两个函数find( )、join( )构成。
    数组 pre[ ] 记录了每个点的前驱节点是谁,函数 find(x) 用于查找指定节点 x 属于哪个集合,函数 join(x,y) 用于合并两个节点 x 和 y 。

    作用:
    并查集的主要作用是求连通分支数(如果一个图中所有点都存在可达关系(直接或间接相连),则此图的连通分支数为1;如果此图有两大子图各自全部可达,则此图的连通分支数为2……)




    2. 并查集的现实意义

    故事引入:
    话说在江湖中散落着各式各样的大侠,他们怀揣着各自的理想和信仰在江湖中奔波。或是追求武林至尊,或是远离红尘,或是居庙堂之高,或是处江湖之远。尽管大多数人都安分地在做自己,但总有些人会因为彼此的信仰不同而聚众斗殴。因此,江湖上常年乱作一团,纷纷扰扰。
    这样长期的混战,难免会打错人,说不定一刀就把拥有和自己相同信仰的队友给杀了。这该如何是好呢?于是,那些有着相同信仰的人们便聚在一起,进而形成了各种各样的门派,比如我们所熟知的“华山派”、“峨嵋派”、“,崆峒派”、“少林寺”、“明教”……这样一来,那些有着相同信仰的人们便聚在一起成为了朋友。以后再遇到要打架的事时,就不会打错人了。
    江湖门派
    但是新的问题又来了,原本互不相识的两个人如何辨别是否共属同一门派呢?
    这好办!我们可以先在门派中选举一个“大哥”作为话事人(也就是掌门人,或称教主等)。这样一来,每当要打架的时候,决斗双方先自报家门,说出自己所在门派的教主名称,如果名称相同,就说明是自己人,就不必自相残杀了,否则才能进行决斗。于是,教主下令将整个门派划分为三六九等,使得整个门派内部形成一个严格的等级制度(即树形结构)。教主就是根节点,下面分别是二级、三级、……、N级队员。每个人只需要记住自己的上级名称,以后遇到需要辨别敌友的情况时,只需要一层层往上询问(网上询问)就能知道是否是同道中人了。
    等级划分
    数据结构的角度来看:
    由于我们的重点是在关注两个人是否连通,因此他们具体是如何连通的,内部结构是怎样的,甚至根节点是哪个(即教主是谁),都不重要。所以并查集在初始化时,教主可以随意选择(就不必再搞什么武林大会了),只要能分清敌友关系就行。

    备注:上面所说的“教主”在教材中被称为“代表元”。
    即:用集合中的某个元素来代表这个集合,则该元素称为此集合的代表元。




    3. find( )函数的定义与实现

    故事引入:
    子夜,小昭于骊山下快马送信,发现一头戴竹笠之人立于前方,其形似黑蝠,倒挂于树前,甚惧,正系拔剑之时,只听四周悠悠传来:“如此夜深,姑凉竟敢擅闯明教,何不下坐陪我喝上一盅?”。小昭听闻,后觉此人乃明教四大护法之一的青翼蝠王韦一笑,答道:“在下小昭,乃紫衫龙王之女”。蝠王轻惕,急问道:“尔等既为龙王之女,故同为明教中人。敢问阁下教主大名,若非本教中人,于明教之地肆意走动那可是死罪!”。小昭吓得赶紧打了个电话问龙王:“龙王啊,咱教主叫啥名字来着?”,龙王答道:“吾教主乃张无忌也!”,小昭遂答蝠王:“张无忌!”。蝠王听后,抱拳请礼以让之。
    在上面的情境中,小昭向他的上级(紫衫龙王)请示教主名称,龙王在得到申请后也向他的上级(张无忌)请示教主名称,此时由于张无忌就是教主,因此他直接反馈给龙王教主名称是“张无忌”。同理,青翼蝠王也经历了这一请示过程。
    在并查集中,用于查询各自的教主名字的函数就是我们的find()函数。find(x)的作用是用于查找某个人所在门派的教主,换言之就是用于对某个给定的点x,返回其所属集合的代表。

    实现:
    首先我们需要定义一个数组:int pre[1000]; (数组长度依题意而定)。这个数组记录了每个人的上级是谁。这些人从0或1开始编号(依题意而定)。比如说pre[16]=6就表示16号的上级是6号。如果一个人的上级就是他自己,那说明他就是教主了,查找到此结束。也有孤家寡人自成一派的,比如欧阳锋,那么他的上级就是他自己。
    每个人都只认自己的上级。比如小昭只知道自己的上级是紫衫龙王。教主是谁?不认识!要想知道自己教主的名称,只能一级级查上去。因此你可以视find(x)这个函数就是找教主用的。
    下面给出这个函数的具体实现:

    int find(int x)					//查找x的教主
    {
    	while(pre[x] != x)			//如果x的上级不是自己(则说明找到的人不是教主)
    		x = pre[x];				//x继续找他的上级,直到找到教主为止
    	return x;					//教主驾到~~~
    }
    



    4. join( )函数的定义与实现

    故事引入:
    虚竹和周芷若是我个人非常喜欢的两个人物,他们的教主分别是玄慈方丈和灭绝师太,但是显然这两个人属于不同门派,但是我又不想看到他们打架。于是,我就去问了下玄慈和灭绝:“你看你们俩都没头发,要不就做朋友吧”。他们俩看在我的面子上同意了,这一同意非同小可,它直接换来了少林和峨眉的永世和平。

    实现:
    在上面的情景中,两个已存的不同门派就这样完成了合并。这么重大的变化,要如何实现?要改动多少地方?其实很简单,我对玄慈方丈说:“大师,麻烦你把你的上级改为灭绝师太吧。这样一来,两派原先所有人员的教主就都变成了师太,于是下面的人们也就不会打起来了!反正我们关心的只是连通性,门派内部的结构不要紧的”。玄慈听后立刻就不乐意了:“我靠,凭什么是我变成她手下呀,怎么不反过来?我抗议!”。抗议无效,我安排的,最大。反正谁加入谁效果是一样的,我就随手指定了一个,join()函数的作用就是用来实现这个的。

    join(x,y)的执行逻辑如下:
    1、寻找 x 的代表元(即教主);
    2、寻找 y 的代表元(即教主);
    3、如果 x 和 y 不相等,则随便选一个人作为另一个人的上级,如此一来就完成了 x 和 y 的合并。
    下面给出这个函数的具体实现:

    void join(int x,int y)                     //我想让虚竹和周芷若做朋友
    {
        int fx=find(x), fy=find(y);            //虚竹的老大是玄慈,芷若MM的老大是灭绝
        if(fx != fy)                           //玄慈和灭绝显然不是同一个人
            pre[fx]=fy;                        //方丈只好委委屈屈地当了师太的手下啦
    }
    



    5. 路径压缩算法之一(优化find( )函数)

    问题引入:
    前面介绍的 join(x,y) 实际上为我们提供了一个将不同节点进行合并的方法。通常情况下,我们可以结合着循环来将给定的大量数据合并成为若干个更大的集合(即并查集)。但是问题也随之产生,我们来看这段代码:

    if(fx != fy)  
    	pre[fx]=fy;
    

    这里并没有明确谁是谁的前驱(上级)的规则,而是我直接指定后面的数据作为前面数据的前驱(上级)。那么这样就导致了最终的树状结构无法预计,即有可能是良好的 n 叉树,也有可能是单支树结构(一字长蛇形)。试想,如果最后真的形成单支树结构,那么它的效率就会及其低下(树的深度过深,那么查询过程就必然耗时)。
    而我们最理想的情况就是所有人的直接上级都是教主,这样一来整个树的结构就只有两级,此时查询教主只需要一次。因此,这就产生了路径压缩算法。
    设想这样一个场景:两个互不相识的大将夏侯惇和许褚碰面了,他们都互相看不惯,想揍对方。于是按照江湖规矩,先打电话问自己的上级:“你是不是教主?” 上级说:“我不是呀,我的上级是***,我帮你问一下。” 就这样两个人一路问下去,直到最终发现他们的教主都是曹操。具体结构如下:
    找掌门人
    “失礼失礼,原来是自己人,在下军机处前将军夏侯惇!”
    “幸会幸会,不打不相识嘛,在下军情处上将许褚!”
    紧接着,两人便高高兴兴地手拉手喝酒去了。
    “等等等等,两位同学请留步,还有事情没完成呢!”我叫住他俩:“还要做路径压缩!”
    两人醒悟,夏侯惇赶紧打电话给他的上级郭嘉:“军师啊,我查过了,我们的教主都是曹丞相。不如我们直接拜在丞相手下吧,省得级别太低,以后找起来太麻烦。”郭嘉答道:“所言甚是” 。
    许褚接着也打电话给刚才拜访过的荀彧,做了同样的事。于是此时,整个曹操阵营的结构如下所示:
    路径压缩
    这样一来,在刚才查询过程中涉及到的人物就都聚集在了曹操的直接领导下,以后再需要查询教主名称的时候,就只需要询问一级便可得到。所以,在经过一次查询后,整个门派树的高度都将大大降低,路径压缩所实现的功能就是这么个意思。

    实现:
    从上面的查询过程中不难看出,当从某个节点出发去寻找它的根节点时,我们会途径一系列的节点(比如上面的例子中,从夏侯惇→郭嘉→曹植→曹操),在这些节点中,除了根节点外(即曹操),其余所有节点(即夏侯惇、郭嘉、曹植)都需要更改直接前驱为曹操。
    因此,基于这样的思路,我们可以通过递归的方法来逐层修改返回时的某个节点的直接前驱(即pre[x]的值)。简单说来就是将x到根节点路径上的所有点的pre(上级)都设为根节点。下面给出具体的实现代码:

    int find(int x)     				//查找结点 x的根结点 
    {
        if(pre[x] == x) return x;		//递归出口:x的上级为 x本身,即 x为根结点        
        return pre[x] = find(pre[x]);	//此代码相当于先找到根结点 rootx,然后pre[x]=rootx 
    }
    

    该算法存在一个缺陷:只有当查找了某个节点的代表元(教主)后,才能对该查找路径上的各节点进行路径压缩。换言之,第一次执行查找操作的时候是实现没有压缩效果的,只有在之后才有效。




    6. 路径压缩算法之二(加权标记法)

    备注:
    不要一看到“加权标记”这种比较高大上的名词就害怕,其实他也是属于路径压缩算法,不同的是其思想更加高级(更不容易想到)罢了。不过我还是说一下,掌握了前面几点内容就能应对绝大多数ACM问题,下面的“加权标记法”供有兴趣的同学学习交流。

    主要思路:
    加权标记法需要将树中所有节点都增设一个权值,用以表示该节点所在树中的高度(比如用rank[x]=3表示 x 节点所在树的高度为3)。这样一来,在合并操作的时候就能通过这个权值的大小来决定谁当谁的上级(玄慈哭了:“正义终会来到,但永不会缺席”)。
    在合并操作的时候,假设需要合并的两个集合的代表元(教主)分别为 x 和 y,则只需要令pre[x] = y 或者pre[y] = x 即可。但我们为了使合并后的树不产生退化(即:使树中左右子树的深度差尽可能小),那么对于每一个元素 x ,增设一个rank[x]数组,用以表达子树 x 的高度。在合并时,如果rank[x] < rank[y],则令pre[x] = y;否则令pre[y] = x。
    举个例子,我们对以A,F为代表元的集合进行合并操作(如下图所示):
    路径压缩
    由于rank(A) > rank(F) ,因此令pre[F]= A。合并后的图形如下图所示:
    路径压缩
    可以看出,合并前两个树的最大高度为3,合并后依然是3,这也就达到了我们的目的。但如果令pre[A]= F,那么就会使得合并后的树的总高度增加,这里我就不上图了,同学们不信可以自己画出来看看。
    我们常说,鱼和熊掌不可兼得,同理,时间复杂度和空间复杂度也很难兼得。由于给每个节点都增加了一个权值来标记其在树中的高度,这也就意味着需要额外的数据结构来存放权重信息,所以这将导致额外的空间开销。

    实现:
    加权标记法的核心在于对rank数组的逻辑控制,其主要的情况有:
    1、如果rank[x] < rank[y],则令pre[x] = y;
    2、如果rank[x] == rank[y],则可任意指定上级;
    3、如果rank[x] > rank[y],则令pre[y] = x;
    在实际写代码时,为了使代码尽可能简洁,我们可以将第1点单独作为一个逻辑选择,然后将2、3点作为另一个选择(反正第2点任意指定上级嘛),所以具体的代码如下:

    void union(int x,int y)
    {
        x=find(x);							//寻找 x的代表元
        y=find(y);							//寻找 y的代表元
        if(x==y) return ;					//如果 x和 y的代表元一致,说明他们共属同一集合,则不需要合并,直接返回;否则,执行下面的逻辑
        if(rank[x]>rank[y]) pre[y]=x;		//如果 x的高度大于 y,则令 y的上级为 x
        else								//否则
        {
            if(rank[x]==rank[y]) rank[y]++;	//如果 x的高度和 y的高度相同,则令 y的高度加1
            pre[x]=y;						//让 x的上级为 y
        }
    }
    



    7. 总结

    1、用集合中的某个元素来代表这个集合,则该元素称为此集合的代表元;
    2 、一个集合内的所有元素组织成以代表元为根的树形结构;
    3 、对于每一个元素 x,pre[x] 存放 x 在树形结构中的父亲节点(如果 x 是根节点,则令pre[x] = x);
    4 、对于查找操作,假设需要确定 x 所在的的集合,也就是确定集合的代表元。可以沿着pre[x]不断在树形结构中向上移动,直到到达根节点。
    因此,基于这样的特性,并查集的主要用途有以下两点:
    1、维护无向图的连通性(判断两个点是否在同一连通块内,或增加一条边后是否会产生环);
    2、用在求解最小生成树的Kruskal算法里。


    一般来说,一个并查集对应三个操作:
    1、初始化( Init()函数 )
    2、查找函数( Find()函数 )
    3、合并集合函数( Join()函数 )


    下面给出上述所有内容的代码汇总:

    const int  N=1005					//指定并查集所能包含元素的个数(由题意决定)
    int pre[N];     					//存储每个结点的前驱结点 
    int rank[N];    					//树的高度 
    void init(int n)     				//初始化函数,对录入的 n个结点进行初始化 
    {
        for(int i = 0; i < n; i++){
            pre[i] = i;     			//每个结点的上级都是自己 
            rank[i] = 1;    			//每个结点构成的树的高度为 1 
        } 
    }
    int find(int x)     	 		    //查找结点 x的根结点 
    {
        if(pre[x] == x) return x;  		//递归出口:x的上级为 x本身,则 x为根结点 
        return find(pre[x]); 			//递归查找 
    } 
     
    int find(int x)     				//改进查找算法:完成路径压缩,将 x的上级直接变为根结点,那么树的高度就会大大降低 
    {
        if(pre[x] == x) return x;		//递归出口:x的上级为 x本身,即 x为根结点 
        return pre[x] = find(pre[x]);   //此代码相当于先找到根结点 rootx,然后 pre[x]=rootx 
    } 
    
    bool isSame(int x, int y)      		//判断两个结点是否连通 
    {
        return find(x) == find(y);  	//判断两个结点的根结点(即代表元)是否相同 
    }
    
    bool join(int x,int y)
    {
        x = find(x);						//寻找 x的代表元
        y = find(y);						//寻找 y的代表元
        if(x == y) return false;			//如果 x和 y的代表元一致,说明他们共属同一集合,则不需要合并,返回 false,表示合并失败;否则,执行下面的逻辑
        if(rank[x] > rank[y]) pre[y]=x;		//如果 x的高度大于 y,则令 y的上级为 x
        else								//否则
        {
            if(rank[x]==rank[y]) rank[y]++;	//如果 x的高度和 y的高度相同,则令 y的高度加1
            pre[x]=y;						//让 x的上级为 y
    	}
    	return true;						//返回 true,表示合并成功
    }
    



    趁热打铁!!!
    下面给出两道涉及到并查集知识的典型例题(含题解),请同学们务必练习下:
    蓝桥杯 历届试题 合根植物
    蓝桥杯 历届试题 国王的烦恼




    展开全文
  • 算法数据结构关系

    千次阅读 2019-07-16 16:11:41
    算法数据结构关系 概述 很多场景或者书籍都会讲算法数据结构捆绑在一起进行讲解,那为什么算法数据结构密不可分呢? 概念 数据结构: 是指一组数据的存储结构。 举个例子:电影院里面的座位是按照几排几号...

    算法和数据结构的关系

    概述

    • 很多场景或者书籍都会讲算法和数据结构捆绑在一起进行讲解,那为什么算法和数据结构密不可分呢?

    概念

    • 数据结构: 是指一组数据的存储结构。
      • 举个例子:电影院里面的座位是按照几排几号进行"存储"观影者。这里的几排几号就是一种数据结构。
    • 算法: 操作数据的一组方法。
      • 举个例子:我们拿到电影票通过电影票上的几排几号就能定位到我们的具体位置,这个找位置的方法就是一种算法。

    两者之间的关系

    • 其实通过上面的概念已经很清楚了,两个是相互依赖的关系。数据结构是为算法服务的,算法要作用在特定的数据结构之上
      • 通过上面的例子来说明两者之间的关系:
      • 数据结构为算法服务 ->几排几号(数据结算)为我们要想快速的找到自己的位置提供了很好的服务。
      • 算法要作用在特定的数据结构之上:这个很简单理解,我们要通过几排几号进行定位自己的位置,首先电影院”存储“观影者的方式要以排和号来存储。

    总结

    • 要想成为一个优秀的软件工程师算法和数据结构是我们绕不开的一道坎,希望本文可以帮忙大家理解算法和数据结构之间的关系。有什么理解有误的地方还希望各位小伙伴能够指出。
    • 如果文章有帮助到你欢迎关注微信公众号《后端学长》 在这里插入图片描述
    展开全文
  • 它覆盖了《计算机学科教学计划1993》中开列的关于算法与数据结构主科目的所有知识单元。其主要内容有:算法与数据结构的概念、抽象数据类型(ADT)、基于序列的ADT(如表,栈,队列和串等)。反映层次关系的ADT(如...
  • 算法与数据结构

    千次阅读 2017-11-20 19:40:47
    算法是计算机处理信息的本质,因为计算机程序本质上是一个算法来告诉计算机确切的步骤来执行一个指定的任务,一般,当算法在处理信息时,会从输入设备或数据的存储地址读取数据,把结果写入输出设备或某个存储地址供...

    算法的概念

    算法是计算机处理信息的本质,因为计算机程序本质上是一个算法来告诉计算机确切的步骤来执行一个指定的任务,一般,当算法在处理信息时,会从输入设备或数据的存储地址读取数据,把结果写入输出设备或某个存储地址供以后再调用。

    算法重要的是其的思想,而不是其所实现的某种语言,它是独立存在的一种解决问题的方法和思想。

    算法的特性

    输入:算法具有0个或多个输入

    输出:算法至少有1个或多个输出

    有穷性:算法在有限的步骤之后会自动结束,而不会无限循环,并且每一个步骤可以在可接受的时间内完成

    确定性:算法中的每一步都有确定的含义,不会出现二义性

    可行性:算法的每一步都是可行的,也就是说每一步都能够执行有限的次数完成

    算法的效率

    执行时间反应算法效率,实现算法程序的执行时间可以反应出算法的效率,也就是算法的优劣

    但是单纯的依靠运行时间来比较算法的优劣并不一定是客观准确的,程序的运行,还依靠了运行环境等客观条件,所以并不能单纯的从运行时间来分别算法的好坏。

    时间复杂度

    假定计算机执行算法每一个基本操作的时间是一个固定的时间单位,那么有多少个基本操作就代表会花费多少时间单位,即使对于不同的程序运行环境来说,确切的程序运行时间是不同的,但是对于算法运行所花费的时间单位的数量级是相同的,所以可以忽略机器环境的影响而客观的反应算法的时间效率。我们采用“大O记法来表示”

    大O记法

    “大O记法”:对于单调的整数函数f,如果存在一个整数函数g和实常数c>0,使得对于充分大的n总有f(n)<=c*g(n),就说函数g是f的一个渐近函数(忽略常数),记为f(n)=O(g(n))。也就是说,在趋向无穷的极限意义下,函数f的增长速度受到函数g的约束,亦即函数f与函数g的特征相似。

    时间复杂度:假设存在函数g,使得算法A处理规模为n的问题示例所用时间为T(n)=O(g(n)),则称O(g(n))为算法A的渐近时间复杂度,简称时间复杂度,记为T(n).

    算法完成工作最少需要多少时间单位,就是最优时间复杂度

    算法完成工作最多需要所少时间单位,就是最坏时间复杂度

    算法完成工作平均需要多少基本操作,就是平均时间复杂度

    时间复杂度的基本计算规则

    基本操作,即只有常数项,认为其时间复杂度为O(1)

    顺序结构,时间复杂度按加法进行计算

    循环结构,时间复杂度按乘法进行计算

    分支结构,时间复杂度取最大值

    判断一个算法的效率时,往往只要关注操作数量的最高次项,其它次要项和常数项可以忽略

    在没有特殊说明时,我们往往分析的算法时间复杂度是指最坏时间复杂度

    常见时间复杂度


    常见时间复杂度之间的关系

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

    数据结构

    为了解决问题,将数据保存下来,然后根据数据的存储方式来设计算法实现进行处理,那么数据的存储方式不同就会导致需要不同的算法进行处理,我们希望算法解决问题的效率越快越好,所以就需要思考如何保存数据,这就是数据结构。换句话说,数据结构指数据对象中数据元素之间的关系。高效的程序需要在数据结构的基础上设计和选择算法。也可以说程序是数据结构和算法之和。

    抽象数据类型(Abstract Data Type)

    ADT的含义是指一个数据模型以及定义在此模型上的一组操作。即把数据类型和数据类型上的运算联合在一起,进行封装。引入抽象数据类型的目的是把数据类型的表示和数据类型上的运算实现与这些数据类型和运算在程序中的引用隔开,使其相互独立。

    最常用的数据运算类型有:插入、删除、修改、查找、排序


    展开全文
  • 数据结构:是指相互之间存在一种或多种特定关系的数据元素的集合用计算机存储、组织数据的方式。数据结构分别为逻辑结构、(存储)物理结构和数据的运算三个部分。 为什么要学数据结构? 首先,因为数据结构作为...
  • 数据结构与算法】如何高效学习数据结构与算法

    千次阅读 多人点赞 2020-05-23 23:30:44
    如果想成为一个高级开发工程师或者进入大厂,不论岗位是前端、后端还是AI,算法都是重中之重。也无论我们需要进入的公司的岗位是否最后是做算法工程师,前提面试就需要考算法。所以`小时不学算法,长大掉头发`。
  • 程序、算法数据结构关系

    万次阅读 2017-10-24 10:29:00
    本文为原创博客,仅供技术学习使用。未经允许,禁止将其复制下来上传到百度...数据结构与算法要通过程序的实现,才能由计算机系统来执行。可以这样理解,数据结构算法形成了可执行的程序。而程序能否快速而有效地完
  • 数据结构与算法数据结构+算法=程序 数据结构 计数机的处理能力来源于cpu, 通过计算机汇编语言(Assembly Language)进行运算工作,cpu只可以做一些简单的二进制操作. 那么问题来了 ? 计算机如何处理 视频/mp3等应用...
  • 数据结构算法关系

    千次阅读 2017-06-05 15:36:48
    数据结构:数据数据之间的结构关系(数组、队列、树、图等结构)算法:解决问题的步骤总结:1、程序 = 数据结构 + 算法 。数据是程序的中心。数据结构算法两个概念间的逻辑关系贯穿了整个程序世界,首先二者表现...
  • 算法与数据结构(面向对象思想)

    千次阅读 2018-07-19 20:44:10
    算法与数据结构和编程之间关系 计算机就是算法与数据结构, 当你选择搜索这类的文章的时候,你已经在翻大山了 编程就是当你翻过一座山的时候,你发现前面还有一座更高的山.   LZ从事java工作一年了,最近听见同事...
  • 数据结构与算法

    千次阅读 2021-04-27 22:23:16
    数据结构与算法的区别联系 1. 数据结构   数据结构(Data Structure)是计算机存储、组织数据的方式。数据结构是指相互之间存在一种或多种特定关系的数据元素的集合。通常情况下,精心选择的数据结构可以带来更...
  • 算法与数据结构的python概述

    千次阅读 2019-12-23 15:17:39
    算法与数据结构概述 引子 **问题一:1+2+3+4+5+......+10000=?** 第一种解法: 1+2=3,3+3=6,6+4=10,10+5=15… 这是要算到猴年马月的节奏呀 果断弃之 第二种解法: 聪明的高斯,这样玩: (1+10000)×10000÷2=...
  • 数据结构与算法:为什么要学习数据结构与算法 数据结构与算法到底是什么 数据结构数据结构指的是计算机中数据的组织形式,分为逻辑结构和物理结构两个维度。其中,逻辑结构是对数据组织形式在逻辑上的抽象,物理...
  • 数据结构与算法关系

    千次阅读 2019-07-02 09:35:31
    数据结构与算法关系 数据结构算法的重要性 算法是程序的灵魂,优秀的程序可以在海量数据计算是,依然保持高速计算 一般来讲,程序会使用内存计算框架(比如spark)和缓存技术(比如redis等)来优化程序。 那...
  • 数据结构算法、程序的关系

    千次阅读 2020-06-02 01:14:18
    这里写目录标题初衷数据结构算法、程序的联系 初衷    数据结构算法、程序的联系 数据结构 = 数据 + 结构 算法 = 算 + 法 程序 = (流)程 + (顺)序 反爬虫措施,读者略过: 转载请标明转自:...
  • 数据结构与算法必知基础知识

    千次阅读 多人点赞 2021-01-06 22:58:12
    数据结构与算法是程序员内功体现的重要标准之一,且数据结构也应用在各个方面,业界更有程序=数据结构+算法这个等式存在。各个中间件开发者,架构师他们都在努力的优化中间件、项目结构以及算法提高运行效率和降低...
  • 数据结构与算法—前导

    千次阅读 2019-07-25 23:53:34
    数据结构与算法是程序员内功体现的重要标准之一,而数据结构的也应用在各个方面,更有程序=数据结构+算法这个被人认证的等式存在。并且数据结构与算法的应用无处不在,各个中间件开发者,架构师。他们都在努力的优化...
  • 数据结构算法常见面试考题

    万次阅读 多人点赞 2018-11-08 09:29:44
    数据结构上几种树集中的讨论一下: 1.AVLtree 定义:最先发明的自平衡二叉查找树。在AVL树中任何节点的两个子树的高度最大差别为一,所以它也被称为高度平衡树。查找、插入和删除在平均和最坏情况下都是O(log n)...
  • 算法与数据结构入门必看(通俗易懂)

    千次阅读 多人点赞 2019-10-01 19:27:40
    算法与数据结构开篇 你真的会数据结构吗? 公司开发一个客服电话系统,小菜需要完成客户排队模块的开发,经过三次修改: 第一次:小菜使用了数据库设计了一张客户排队表,并且设置了一个自动增长的整型id字段,来...
  • 数据结构与算法数据结构概念(已完成迁移)

    千次阅读 多人点赞 2019-01-17 21:23:59
    数据结构:对数据的一种存储和组织方式,相互之间存在一种或者多种特定关系的数据的集合。数据就是存储的 有用的信息 数据元素:数据的基本单位,又称节点、元素 2.数据整体结构:逻辑结构、存储结构、运算 三者...
  • 数据结构与算法】常见数据结构及基本操作

    万次阅读 多人点赞 2019-06-16 21:42:44
    数据结构与算法常见概念2.数据逻辑结构2.1线性结构2.2树形结构2.3图形结构2.4集合结构3.排序算法冒泡排序简单选择排序直接插入排序希尔排序堆排序归并排序快速排序4.查找算法顺序表查找有序表查找线性索引查找二叉...
  • 数据结构与算法简介

    千次阅读 2018-09-06 15:41:21
    数据结构算法关系数据结构是底层,算法是高层。数据结构算法提供服务,算法围绕数据结构操作。从狭义上看:算法和数据的存储方式密切相关,两者之间密不可分,但是从广义上来说,算法和数...
  • 021_《Delphi算法与数据结构

    千次阅读 2010-11-25 09:11:00
    Delphi开发人员Julian Bucknall从实用角度为广大程序员提供了有关使用算法数据结构的一个详尽的介绍。Bucknall先从算法性能的讨论开始,涵盖了诸如数组、链表和二叉树等内容。这本书强调了查找算法(如顺序和二分...
  • Java数据结构算法(一)——开篇

    万次阅读 多人点赞 2014-09-15 07:03:40
    看的是——《Java数据结构算法》一书,作者Robert Lafore。 目录 1)数据结构算法有什么用? 2)技术通俗 3)驱动力学习 1)数据结构算法有什么用? 当你用着java里面的容器类很爽的时候,你有没有想过,怎么...
  • Java数据结构与算法入门

    万次阅读 多人点赞 2018-04-29 11:53:50
    数据结构:Data_Structure,它是储存数据的一种结构体,在此结构中储存一些数据,而这些数据之间有一定的关系。而各数据元素之间的相互关系,又包括三个组成成分,数据的逻辑结构,数据的存储结构和数据运算结构。而...
  • 数据结构与算法设计基础

    千次阅读 2020-09-18 21:44:33
    数据结构地位2 基本概念和术语基本概念数据结构的两个层次:逻辑结构划分方法一:划分方法二:存储结构(物理结构)存储结构分为:3 抽象数据类型的表示实现数据类型抽象数据类型(ADT: Abstract Data Types)4 算法...
  • 数据结构往往同高效的检索算法和索引技术有关。 数据结构里面的一些重要概念: 1.逻辑结构物理结构 1.1逻辑结构(重点) 指反映数据元素之间的逻辑关系数据结构,其中的逻辑关系是指数据元素之间的

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 525,473
精华内容 210,189
关键字:

关于算法与数据结构的关系

数据结构 订阅