entities.entities_for_tag

26 total results found

关键路径的实现算法和复杂度分析

数据结构与算法

在上篇文章中学院君简单介绍了关键路径的定义,这篇文章我们来探讨关键路径的实现算法。 在 AOE 网中,某些活动可以并行地进行,因此完成工程的最短时间是从源点到汇点的最大路径长度(事件之间耗时最...

由 学院君 发布于9 months ago    浏览数: 93    点赞数: 0

拓扑排序的算法实现及复杂度分析

数据结构与算法

上篇文章学院君介绍了什么是拓扑排序以及拓扑排序的应用场景,还是老规矩,介绍完基本概念,我们接着通过数据结构和算法来实现它,拓扑排序的基本实现思路如下: 在 AOV 网中,找到一个入度为 0 的...

由 学院君 发布于9 months ago    浏览数: 76    点赞数: 0

最短路径的实现算法(二):弗洛伊德算法(Floyd)

数据结构与算法

昨天我们介绍了网图的最短路径定义,以及如何通过迪杰斯特拉算法实现,今天我们介绍最短路径的另一种常见实现算法 —— 弗洛伊德(Floyd)算法。 实现原理 弗洛伊德算法的基本思想如下: 从任...

由 学院君 发布于9 months ago    浏览数: 123    点赞数: 0

最短路径及实现算法(一):迪杰斯特拉算法(Dijkstra)

数据结构与算法

最短路径 在日常生活中,我们经常面临路径选择的问题,比如从杭州到北京,可以选择汽车、火车、飞机,甚至还可以坐公交车(这不是笑话,最近网上就流传一个从杭州回临沂,转了 35 班公交车,行程 66...

由 学院君 发布于9 months ago    浏览数: 119    点赞数: 0

最小生成树的实现算法之克鲁斯卡尔算法(Kruskal)

数据结构与算法

上篇文章我们分享了通过普里姆算法实现最小生成树,该算法主要以顶点为维度,时间复杂度也只与顶点相关,今天我们要给大家介绍最小生成树的另一种实现算法 —— 克鲁斯卡尔(Kruskal)算法。 实现...

由 学院君 发布于9 months ago    浏览数: 97    点赞数: 0

最小生成树的实现算法之普里姆算法(Prim)

数据结构与算法

上篇文章学院君简单给大家介绍了最小生成树的定义,接下来我们分别介绍最小生成树的两种常见的实现算法,首先介绍的是普里姆(Prim)算法。 算法定义 简单来说,普里姆算法从图中某个顶点开始,将其...

由 学院君 发布于9 months ago    浏览数: 133    点赞数: 0

图的遍历(下)—— 广度优先搜索

数据结构与算法

上篇文章我们分享了通过深度优先搜索对图进行遍历,这篇我们来探讨如何通过广度优先搜索对图进行遍历。 广度优先搜索定义 广度优先搜索(Breadth First Search),简称 BFS,我...

由 学院君 发布于9 months ago    浏览数: 128    点赞数: 0

图的遍历(上)—— 深度优先搜索

数据结构与算法

前面我们已经介绍了图的定义和存储,今天这篇我们来探讨图的遍历,图的遍历和树的遍历类似,最直接的理解就是,在图中某个顶点出发,访遍图中其余顶点,并且其中每个顶点仅被访问一次,这个过程就是图的遍历。...

由 学院君 发布于9 months ago    浏览数: 242    点赞数: 0

图的存储:邻接矩阵和邻接表

数据结构与算法

由于图这种数据结构比较复杂,单纯的数组和链表已经无法表示了,需要通过更复杂的结构来存储。 今天,学院君简单为大家介绍两种存储图的方式,一种是基于数组,一种是基于链表,但是不是简单的数组和链表,...

由 学院君 发布于9 months ago    浏览数: 162    点赞数: 0

解决 TopK 问题的利器(下):堆排序及其应用

数据结构与算法 二叉树

堆排序 上篇分享我们介绍了堆的定义及其构建,这篇教程我们来分享堆排序及其应用,堆排序的过程其实就是不断删除堆顶元素的过程。如果构建的是大顶堆,逐一删除后堆顶元素构成的序列是从大到小排序;如果构...

由 学院君 发布于9 months ago    浏览数: 209    点赞数: 0

红黑树的特性和算法复杂度

数据结构与算法 二叉树

前面几篇分享中我们陆续介绍了平衡二叉树的定义、实现原理、构建过程演示以及对应的实现代码,我们提到平衡二叉树是最理想的二叉排序树,性能最好,也最稳定,但是缺点是维护成本高,需要在插入和删除节点时维...

由 学院君 发布于9 months ago    浏览数: 252    点赞数: 0

平衡二叉树(AVL)的实现代码和算法复杂度

数据结构与算法 二叉树

下面我们将上一篇分享中演示的平衡二叉树构建示例转化为 PHP 代码。 节点类 我们还是使用二叉链表来实现二叉树的存储,对应的节点类如下: class AVLNode { pub...

由 学院君 发布于9 months ago    浏览数: 254    点赞数: 1

平衡二叉树(AVL)的定义和实现原理

数据结构与算法 二叉树

引子 上一篇我们介绍了二叉排序树,并且提到理想情况下,二叉排序树的插入、删除、查找时间复杂度都是 O(logn),非常高效,而且它是一种动态的数据结构,插入删除性能合查找一样好,不像之前提到的...

由 学院君 发布于9 months ago    浏览数: 320    点赞数: 2

二叉排序(查找)树的定义及实现

数据结构与算法 二叉树

为什么要引入二叉排序树 我们前面已经介绍了很多数据结构,比如数组、链表、散列表等,数组查找性能高,但是插入、删除性能差,链表插入、删除性能高,但查找性能差,在不考虑散列冲突的话,散列表的插入、...

由 学院君 发布于9 months ago    浏览数: 386    点赞数: 0

PHP 字符串匹配函数 strstr 底层实现原理剖析

数据结构与算法 字符串匹配

PHP 提供的字符串匹配函数多是单模式匹配,因此大多通过 KMP 算法实现,我们以 strstr 函数为例,简单对底层实现源码进行剖析。 strstr 是 PHP 标准库提供的函数,所以可以在...

由 学院君 发布于9 months ago    浏览数: 204    点赞数: 0