Estom的博客

算法概述 参考文献 八种算法思想 1 基本概念定义 算法是一系列解决问题的清晰指令，对于符合一定规范的输入，算法能够在有限时间内获得所要求的输出。算法是解决问题的一种方法或过程，它是由若干条指令组成的有穷序列。 算法本质上不是数学，而是逻辑。 特征 输入：有零或多个外部量作为算法的输入。 输出：算法产生至少一个量作为输出。 确定性：组成算法的每条指令清晰、无歧义。 有效性：算法中执行的任何计算步骤都是可以被分解为基本的可执行的操作步。 有限性：算法中每条指令的执行次数有限，执行每条指令的时间也有限。 算法的描述 算法的描述方式：自然语言、流程图、伪代码 算法的正确性证明方式：归纳法 算法分析：正确性分析、效率分析、复杂度分析 算法的终极目标 次序order：先做什么、后做什么。前边对后边有影响。 选择if-else：要做什么、不做什么。合并相同的类别，减少分类讨论的情况。 重复while-for:一直做什么。提取相同子结构、相同子操作，进行重复利用。可以通过递归实现重复。 整理说明 以算法结尾，代表的是某一系列或者某一类通用的算法。不依赖于具体的问题。通常可以解决很...

算法效率 目录 算法效率的度量 函数的渐进的界 算法的基本复杂性类型 算法复杂性分析的基本方法 非递归算法的复杂性分析 递归算法的复杂性分析 递归算法与非递归算法比较 经验分析方法 算法可视化 1 算法效率的度量分类 时间复杂度 空间复杂度 算法效率的表示N-要解决问题的规模I-算法的输入A-算法本身C-算法复杂性S-空间复杂性T-时间复杂性$$C = F(N, I, A)\T = T(N, I)\S = S(N, I)\$$ 算法效率的界包含最大时间效率、最小时间效率、平均时间效率。 2 函数的渐进的界函数的界定义设f 和g 是定义域为自然数集N上的函数 $f(n)=O(g(n))$渐进上界若存在正数$c$和$n0$使得对一切$n≥n0有0≤f(n)≤cg(n)$ $f(n)= Ω(g(n))$渐进下届若存在正数$c$和$n0$使得对一切$n≥n0有0≤cg(n)≤ f(n)$ $f(n)=o(g(n))$不可达上届对任意正数$c$存在$n0$使得对一切$n≥n0$有$0≤f(n)<cg(n)$ $...

蛮力法0 蛮力法概述 蛮力法是一种简单直接地解决问题的方法，常常直接 基于问题的描述和所涉及的概念定义。 1 查找算法2 搜索算法——广度优先搜索3 搜索算法——深度优先搜索4 排序算法——简单排序5 排序算法——线性排序6 线性时间选择算法7 字符串算法——匹配算法8 字符串算法——其他算法9 位运算算法

查找算法 阅读目录 顺序查找 二分查找 插值查找 斐波那契查找 树表查找 分块查找 哈希查找 0 概述 查找是在大量的信息中寻找一个特定的信息元素，在计算机应用中，查找是常用的基本运算，例如编译程序中符号表的查找。 本文简单概括性的介绍了常见的七种查找算法，说是七种，其实二分查找、插值查找以及斐波那契查找都可以归为一类——插值查找。 插值查找和斐波那契查找是在二分查找的基础上的优化查找算法。树表查找和哈希查找会在后续的博文中进行详细介绍。 查找算法，一般适用于线性结构。 搜索算法，一般适用于树和图。 查找定义 根据给定的某个值，在查找表中确定一个其关键字等于给定值的数据元素（或记录）。 查找算法分类： 静态查找和动态查找； 静态或者动态都是针对查找表而言的。动态表指查找表中有删除和插入操作的表。 无序查找和有序查找。 无序查找：被查找数列有序无序均可； 有序查找：被查找数列必须为有序数列。 平均查找长度（Average Search Length，ASL） 需和指定key进行比较的关键字的个数的期望值，称为查找算法在查找成功时的平均查找长度。 对于...

广度优先搜索1 概述特点 广度优先搜索（BFS：Breadth-First Search）是一种树和图搜索策略，其将搜索限制到 2 种操作： 访问图中的一个节点； 访问该节点的邻居节点； 过程 广度优先搜索（BFS）由 Edward F. Moore 在 1950 年发表，起初被用于在迷宫中寻找最短路径。在 Prim 最小生成树算法和 Dijkstra 单源最短路径算法中，都采用了与广度优先搜索类似的思想。 对图的广度优先搜索与对树（Tree）的广度优先遍历（Breadth First Traversal）是类似的，区别在于图中可能存在环，所以可能会遍历到已经遍历的节点。BFD 算法首先会发现和源顶点 s 距离边数为 k 的所有顶点，然后才会发现和 s 距离边数为 k+1 的其他顶点。 例子 例如，下面的图中，从顶点 2 开始遍历，当遍历到顶点 0 时，邻接的顶点为 1 和 2，而顶点 2 已经遍历过，如果不做标记，遍历过程将陷入死循环。所以，在 BFS 的算法实现中需要对顶点是否访问过做标记。 上图的 BFS 遍历结果为 [ 2, 0, 3, 1 ]。 实...

深度优先搜索1 概述定义 深度优先搜索（DFS：Depth-First Search）是一种图搜索策略，其将搜索限制到 2 种操作： 访问图中的一个节点； 访问该节点的子节点； 过程 在深度优先搜索中，对于最新发现的顶点，如果它还有以此为起点而未探测到的边，就沿此边继续探测下去。当顶点 v 的所有边都已被探寻过后，搜索将回溯到发现顶点 v 有起始点的那些边。这一过程一直进行到已发现从源顶点可达的所有顶点为止。实际上深度优先搜索最初的探究也是为了解决迷宫问题。 对图的深度优先搜索与对树（Tree）的深度优先遍历（Depth First Traversal）是类似的，区别在于图中可能存在环，所以可能会遍历到已经遍历的节点。 例子 例如，下面的图中，从顶点 2 开始遍历，当遍历到顶点 0 时，子顶点为 1 和 2，而顶点 2 已经遍历过，如果不做标记，遍历过程将陷入死循环。所以，在 DFS 的算法实现中需要对顶点是否访问过做标记。 上图的 DFS 遍历结果为 2, 0, 1, 3。 实现 DFS 算法可以通过不同方式来实现： 递归方式 非递归方式：栈（Stack）数据结构...

排序算法0 比较排序算法分类比较排序（Comparison Sort）通过对数组中的元素进行比较来实现排序。 比较排序算法（Comparison Sorts） Category Name Best Average Worst Memory Stability  插入排序  （Insertion Sorts）    插入排序 （Insertion Sort） n n2 n2 1 Stable  希尔排序 （Shell Sort） n n log2 n n log2 n 1 Not Stable  交换排序 （Exchange Sorts ）        快速排序 （Quick Sort）  n log n n log n n2 log n Not Stable  冒泡排序 （Bubble Sort） n ...

线性时间排序算法0 线性时间排序算法列表 线性时间排序 Name Average Worst Memory Stable Description  计数排序 （Counting Sort） n + k n + k n + k Stable  Indexes using key values.  基数排序 （Radix Sort） n * k  n * k n + k Stable  Examines individual bits of keys.  桶排序 （Bucket Sort） n + k n2 n * k Stable  Examine bits of keys. 特点给定含 n 个元素的输入序列，任何比较排序在最坏情况下都需要 Ω(n log n) 次比较来进行排序。合并排序和堆排序在最坏情况下达到上界 O(n log n)，它们都是渐进最优的排序算法，快速排序在平均情况下达到上界 O(n log n)。...

线性时间选择算法1 问题概述 在一个由 n 个元素组成的集合中，第 i 个顺序统计量（order statistic）是该集合中第 i 小的元素。也就是说，最小值是第 1 个顺序统计量（i = 1），最大值是第 n 个顺序统计量（i = n）。 中位数（median）是它所在集合的中点元素。当 n 为奇数时，中位数是唯一的，出现在 i = (n + 1)/2 处。当 n 为偶数时，存在两个中位数，下中位数 i = n/2 和上中位数 i = n/2 + 1 处。因此，不考虑 n 的奇偶性，中位数总是出现在 i = (n+1)/2 的中位数处。本文中所用的中位数总是指下中位数。 选择最大值和最小值 选择中位数或任意位置值 1 选择最大值和最小值算法原理对于确定最大值和最小值的问题，n-1 次比较是最优的。 对于同时获取最大值和最小值，至多需要 3(n/2) 次比较就足以同时找到。如果 n 是奇数，那么总共需要 3(n/2) 次比较。如果 n 是偶数，则可先做一次...

字符串匹配算法问题分析字符串匹配问题的形式定义 文本（Text）是一个长度为 n 的数组 T[1..n]； 模式（Pattern）是一个长度为 m 且 m≤n 的数组 P[1..m]； T 和 P 中的元素都属于有限的字母表 Σ 表； 如果 0≤s≤n-m，并且 T[s+1..s+m] = P[1..m]，即对 1≤j≤m，有 T[s+j] = P[j]，则说模式 P 在文本 T 中出现且位移为 s，且称 s 是一个有效位移（Valid Shift）。 比如上图中，目标是找出所有在文本 T = abcabaabcabac 中模式 P = abaa 的所有出现。该模式在此文本中仅出现一次，即在位移 s = 3 处，位移 s = 3 是有效位移。 解决字符串匹配的算法包括 朴素算法（Naive Algorithm） Rabin-Karp 算法 有限自动机算法（Finite Automation） Knuth-Morris-Pratt 算法（即 KMP Algorithm） Boyer-Moore 算法、Simon 算...