search
HomeDatabaseMysql Tutorial你必须背下的几个经典算法[2nd]
你必须背下的几个经典算法[2nd]Jun 07, 2016 pm 03:00 PM
excellentseveralalgorithmclassichimself

(三) 红黑树 红黑树 自身具有优秀的平衡性,具有很高效的检索速度,很适于对有权重的数据进行组织和查找。红黑树首先是一种二叉搜索树,因而具有“左下最

(三)红黑树

       红黑树自身具有优秀的平衡性,具有很高效的检索速度,很适于对有权重的数据进行组织和查找。红黑树首先是一种二叉搜索树,因而具有“左下最小、右下最大”的性质。红黑树的每个节点(node)至少包括了5个域: 父节点指针、左孩子指针、右孩子指针、关键字、颜色,红黑树具有如下特性,才使得它具有如此优秀的性质: 

[1]红黑树的节点要么是黑色,要么是红色。
[2]根节点是黑色
[3]叶子节点是黑色(根节点和叶子节点一般用一个唯一的域值为null的null节点表示)
[4]红色节点的孩子必须是黑色
[5]从任意节点到达叶子节点,所经过的黑色节点数目相等
(其中黑高可以用来特指某个节点到达它的叶子节点的路径上黑色节点数目,不包括其自身)
       一个红黑树的建树时间是O(n*lg(n)),插入时间是O(lg(n)),删除时间是O(lg(n)),检索时间是O(lg(n))。  
       二叉搜索树的旋转操作: 
        X
      /   \
    a      Y
          /   \
        b      r
旋转为:
           Y
         /   \
       X      r
     /  \
   a     b


        不需要额外的指针就能进行旋转操作,步骤如下
[1] y = x.right 这里用到了两个指针,包括一个参数
[2] x.p.left_or_right = y; y.p = x.p; 
[3] x.right = y.left; y.left.p = x; 
[3] y.left = x; x.p = y; 
        红黑树的插入:
步骤一: 根据二叉搜索树的方法插入节点并且标记为红色,不考虑节点插入对4个性质的违背
步骤二: 由于可能违背了性质2、(非根)必须违背性质4,进行着色调整。调用RB-INSERT-FIXUP,分三种情况进行处理:
(1)叔节点为红色,自身为左孩子或者右孩子均可
(2)叔节点为黑色,自身为左孩子
(3)叔节点为黑色,自身为右孩子


(1)将祖父节点的黑色变为红色,将黑色分给父节点和叔节点,继续针对祖父节点递归,这样黑高向下“移”而不变,而且操作仅仅使着色发生变化

(2)对父节点进行右旋操作,并且保持树的颜色分布,这样颜色分布不变,仅仅是父节点进行了右旋


(四)基数排序

        基数排序的思想是将n个待排元素对应到一个多位的整数,一共有d位,每一位都可以取值k个值; 对每一位为标准位进行一次稳定的排序,整个元素的顺序按照这个标准位进行排列,继续从低位排序到高位,并对这个元素重新排序; 如果每一次稳定排序的时间是O(n+k),那么最终时间是O(d*(n+k))。


(五)桶排序

       桶排序是针对在一定区间内均匀分布(或近似于均匀分布)的数据进行排序的,所以是一种特殊(非普适)的算法。我们假设分布的区间是[0, 1),对这个长度为1的区间分成n个小区间(我们称之为桶),每个区间长度为1/n,每一个小区间对应一个链表,当新数据输入时,我们将输入数据逐个地和桶的标准分界值比较,当输入数据落入某个区间时,将它插入到对应的链表中去,在插入的时候又可以进行比较从而使得链表内数据有序。当所有输入完成后,将所有链表(除了头节点)链接起来,形成一个总的链表。

(六)动态规划

算法基本思想是分治:将问题分解为若干个子问题,但是要进行中间结果(即子问题的解)的记录,在继续计算时,会多次使用前面的中间结果,将这些子问题的解有序地组合起来,一般可以组成一个二维数组,备存便用,这成为了动态规划的最大特征。可见动态规划是一种牺牲空间换取时间为代价的,中间结果放在存储表中。利用这种思想对递归方法进行改进得到了记忆型递归,即每次递归到子问题时先查询是否有中间解,没有继续递归,否则直接使用已得结果,如矩阵链乘法。

动态规划的使用还有一个重要的原则:即子问题的原问题的最优解的必要条件,即如果最终的解是最优的,那么解的每一个细分(按照子问题划分)或每一个步骤都是最优的。比如最短路径问题,它的子步骤是到达终点的路径分段,即包含终点的子路径的选择(从后向前),要确保每一个字分段都是最优的。即如果你必须背下的几个经典算法[2nd]是最优的,则有你必须背下的几个经典算法[2nd]是最优的。这里0-1背包问题和最短路径问题都是最优解问题。

(七)0-1背包问题

算法的思想简单,是基本的递归思路,只不过在每一层递归时,考虑下一个物品的取舍,以及下一物品是否“超重”,总是遵循“累计”价值最大以及“超重不取”的原则,而不是“能装则取”。

不过在构造存储表时需要更多的技巧,这是一个矩阵(二维数组),i下标代表剩余的物品数,j下标代表剩余的容量。由于二维数组下标是连续变化的,所以对每一个单位的剩余重量都要分配存储空间和初始化值,这里考虑的临界条件比较巧妙,对数组元素赋的初值经过了精心设计:a.对于取最后一个物品的,即剩余n个物品的初值,假设W[n] M[n][W[n]...C] = W[n],;这里进一步考虑对于第n个物品,元素下标j为0到W[n]-1的情况,虽然在目前看来不可能,因为我们的物品n重量W[n]M[n][0...W[n]-1] = 0,即不能选取物品,考虑物品n后,总的最大的价值是0。b.如果W[n]>C,装不下最后一个物品,对于则只能对这些值赋0,即考虑第n个物品的取舍之后,得到的总的最大价值仍然是0,也就是M[n][0...C] = 0。归纳以上两种情况,令MaxJ = min(W[n] - 1, C),有M[n][0...MaxJ] = 0; M[n][W[n]...C] =  W[n]; (注意:这里W[n]...C在遇到W[n] > C的情况时,认为赋值不会被执行)

重复以上思路,对于0...C(...表“到”)即全部的重量范围,无论还剩余多少个n-1以内的物品,都无法估算出,考虑了这些物品后,能够获得的最大价值;因为在考虑这些物品时,至少还要考虑对是否选择第n个物品,由此产生的最大价值的比较问题(第n个物品有可能选有可能在装不下时不选),从而无法赋初值。其中又可以分为两种情况:a.W[i] C,放不下物品i,M[i][j] = M[i+1][j],j = 0...C。归纳来说,就是MaxJ = min(W[i] - 1, C),有M[i][j] = M[i+1][j],j = 0...MaxJ;M[i][j] = max(M[i+1][j-W[i]] + V[i], M[i+1][j]),j = W[i]...C。

在这里,又有一个细节性的关键问题,在这个算法中,取第i件物品影响的不是还没有的取得物品,而是自身的问题最大价值,这里要考虑的是选取物品i使得剩余空间减少的情况下子问题的最大值 和 不选取物品i的剩余空间下子问题的最大值,而不是第i+1件物品已经确定,剩余容量大小和i的增减之间也没有正相关的关系,只是第i+1件物品的子问题提供了在不同剩余空间下最大价值的子问题解的选择而已;具体地说,这里用到的反向思维方式,即我们的问题的最优解取决于子问题的最优解,而子问题的最优解是已经解决的问题的解和当前考虑的新元素对应的情况处理组合,而不是仅仅是在子问题解中选择最大价值的解,这里我们要在i+1物品的考虑点上,对两个不同的剩余容量存储值对应的价值之间进行选择,即选择采用M[i+1][j]还是M[i+1][j-W[i]]。这有悖于正常思维,因为我们可能认为第i+1个物品已经选过,而对它的选择取还是不取,考虑时剩余的背包容量空间应该固定的,而这里却受到第i个物品的取舍的影响。这里,正是这个算法的精髓所在,即在考虑某个物品时,要考虑所有的容量空间,在这些容量空间下,取舍该物品所能得到的总的价值都要计算。 这样,在选取之后的第i件物品时,第i件物品的取舍直接影响到对于第i+1个子问题解的选择范围,这里的选择范围是取或不取第i件物品造成的剩余容量的限制,具体地说,就是选取第i件物品时在剩余容量下取最大价值的子问题的解,和在不取第i件物品时在剩余容量下取最大价值的子问题的解,在这基础上再考虑第i件物品的选取带来的价值,由此作出选择。

用数学表达式表示如下:

你必须背下的几个经典算法[2nd]

Statement
The content of this article is voluntarily contributed by netizens, and the copyright belongs to the original author. This site does not assume corresponding legal responsibility. If you find any content suspected of plagiarism or infringement, please contact admin@php.cn
特斯拉自动驾驶算法和模型解读特斯拉自动驾驶算法和模型解读Apr 11, 2023 pm 12:04 PM

特斯拉是一个典型的AI公司,过去一年训练了75000个神经网络,意味着每8分钟就要出一个新的模型,共有281个模型用到了特斯拉的车上。接下来我们分几个方面来解读特斯拉FSD的算法和模型进展。01 感知 Occupancy Network特斯拉今年在感知方面的一个重点技术是Occupancy Network (占据网络)。研究机器人技术的同学肯定对occupancy grid不会陌生,occupancy表示空间中每个3D体素(voxel)是否被占据,可以是0/1二元表示,也可以是[0, 1]之间的

基于因果森林算法的决策定位应用基于因果森林算法的决策定位应用Apr 08, 2023 am 11:21 AM

译者 | 朱先忠​审校 | 孙淑娟​在我之前的​​博客​​中,我们已经了解了如何使用因果树来评估政策的异质处理效应。如果你还没有阅读过,我建议你在阅读本文前先读一遍,因为我们在本文中认为你已经了解了此文中的部分与本文相关的内容。为什么是异质处理效应(HTE:heterogenous treatment effects)呢?首先,对异质处理效应的估计允许我们根据它们的预期结果(疾病、公司收入、客户满意度等)选择提供处理(药物、广告、产品等)的用户(患者、用户、客户等)。换句话说,估计HTE有助于我

Mango:基于Python环境的贝叶斯优化新方法Mango:基于Python环境的贝叶斯优化新方法Apr 08, 2023 pm 12:44 PM

译者 | 朱先忠审校 | 孙淑娟引言模型超参数(或模型设置)的优化可能是训练机器学习算法中最重要的一步,因为它可以找到最小化模型损失函数的最佳参数。这一步对于构建不易过拟合的泛化模型也是必不可少的。优化模型超参数的最著名技术是穷举网格搜索和随机网格搜索。在第一种方法中,搜索空间被定义为跨越每个模型超参数的域的网格。通过在网格的每个点上训练模型来获得最优超参数。尽管网格搜索非常容易实现,但它在计算上变得昂贵,尤其是当要优化的变量数量很大时。另一方面,随机网格搜索是一种更快的优化方法,可以提供更好的

因果推断主要技术思想与方法总结因果推断主要技术思想与方法总结Apr 12, 2023 am 08:10 AM

导读:因果推断是数据科学的一个重要分支,在互联网和工业界的产品迭代、算法和激励策略的评估中都扮演者重要的角色,结合数据、实验或者统计计量模型来计算新的改变带来的收益,是决策制定的基础。然而,因果推断并不是一件简单的事情。首先,在日常生活中,人们常常把相关和因果混为一谈。相关往往代表着两个变量具有同时增长或者降低的趋势,但是因果意味着我们想要知道对一个变量施加改变的时候会发生什么样的结果,或者说我们期望得到反事实的结果,如果过去做了不一样的动作,未来是否会发生改变?然而难点在于,反事实的数据往往是

使用Pytorch实现对比学习SimCLR 进行自监督预训练使用Pytorch实现对比学习SimCLR 进行自监督预训练Apr 10, 2023 pm 02:11 PM

SimCLR(Simple Framework for Contrastive Learning of Representations)是一种学习图像表示的自监督技术。 与传统的监督学习方法不同,SimCLR 不依赖标记数据来学习有用的表示。 它利用对比学习框架来学习一组有用的特征,这些特征可以从未标记的图像中捕获高级语义信息。SimCLR 已被证明在各种图像分类基准上优于最先进的无监督学习方法。 并且它学习到的表示可以很容易地转移到下游任务,例如对象检测、语义分割和小样本学习,只需在较小的标记

​盒马供应链算法实战​盒马供应链算法实战Apr 10, 2023 pm 09:11 PM

一、盒马供应链介绍1、盒马商业模式盒马是一个技术创新的公司,更是一个消费驱动的公司,回归消费者价值:买的到、买的好、买的方便、买的放心、买的开心。盒马包含盒马鲜生、X 会员店、盒马超云、盒马邻里等多种业务模式,其中最核心的商业模式是线上线下一体化,最快 30 分钟到家的 O2O(即盒马鲜生)模式。2、盒马经营品类介绍盒马精选全球品质商品,追求极致新鲜;结合品类特点和消费者购物体验预期,为不同品类选择最为高效的经营模式。盒马生鲜的销售占比达 60%~70%,是最核心的品类,该品类的特点是用户预期时

人类反超 AI:DeepMind 用 AI 打破矩阵乘法计算速度 50 年记录一周后,数学家再次刷新人类反超 AI:DeepMind 用 AI 打破矩阵乘法计算速度 50 年记录一周后,数学家再次刷新Apr 11, 2023 pm 01:16 PM

10 月 5 日,AlphaTensor 横空出世,DeepMind 宣布其解决了数学领域 50 年来一个悬而未决的数学算法问题,即矩阵乘法。AlphaTensor 成为首个用于为矩阵乘法等数学问题发现新颖、高效且可证明正确的算法的 AI 系统。论文《Discovering faster matrix multiplication algorithms with reinforcement learning》也登上了 Nature 封面。然而,AlphaTensor 的记录仅保持了一周,便被人类

研究表明强化学习模型容易受到成员推理攻击研究表明强化学习模型容易受到成员推理攻击Apr 09, 2023 pm 08:01 PM

​译者 | 李睿 审校 | 孙淑娟​随着机器学习成为人们每天都在使用的很多应用程序的一部分,人们越来越关注如何识别和解决机器学习模型的安全和隐私方面的威胁。 然而,不同机器学习范式面临的安全威胁各不相同,机器学习安全的某些领域仍未得到充分研究。尤其是强化学习算法的安全性近年来并未受到太多关注。 加拿大的麦吉尔大学、机器学习实验室(MILA)和滑铁卢大学的研究人员开展了一项新研究,主要侧重于深度强化学习算法的隐私威胁。研究人员提出了一个框架,用于测试强化学习模型对成员推理攻击的脆弱性。 研究

See all articles

Hot AI Tools

Undresser.AI Undress

Undresser.AI Undress

AI-powered app for creating realistic nude photos

AI Clothes Remover

AI Clothes Remover

Online AI tool for removing clothes from photos.

Undress AI Tool

Undress AI Tool

Undress images for free

Clothoff.io

Clothoff.io

AI clothes remover

AI Hentai Generator

AI Hentai Generator

Generate AI Hentai for free.

Hot Article

Hot Tools

MantisBT

MantisBT

Mantis is an easy-to-deploy web-based defect tracking tool designed to aid in product defect tracking. It requires PHP, MySQL and a web server. Check out our demo and hosting services.

Atom editor mac version download

Atom editor mac version download

The most popular open source editor

Dreamweaver Mac version

Dreamweaver Mac version

Visual web development tools

Notepad++7.3.1

Notepad++7.3.1

Easy-to-use and free code editor

SublimeText3 English version

SublimeText3 English version

Recommended: Win version, supports code prompts!