算法、数据结构、竞赛——OI Wiki

编程竞赛发展多年,难度越来越高,内容越来越复杂,而网上资料大多零散,初学者往往并不知道如何系统地学习相关知识,需要花费大量时间摸索。 为了方便热爱编程竞赛的小伙伴更好地入门,2018 年 7 月份,OI Wiki 迁移至 GitHub。随着 OI Wiki 的内容不断完善,越来越多的小伙伴参与其中。 OI Wiki 致力于成为一个免费开放且持续更新的知识整合站点,大家可以在这里获取关于 编程竞赛 (competitive programming) 有趣又实用的知识,我们为大家准备了竞赛中的基础知识、常见题型、解题思路以及常用工具等内容,帮助大家更快速深入地学习编程竞赛。 目前,OI Wiki 的内容还有很多不完善的地方,知识点覆盖不够全面,存在一些低质量页面需要修改。OI Wiki 团队以及参与贡献的小伙伴们正在积极完善这些内容。 关于上述待完善内容,请参见 OI Wiki 的 Issues 以及 迭代计划。 与此同时, OI Wiki 源于社区,提倡 知识自由,在未来也绝不会商业化,将始终保持独立自由的性质。

算法基础10——设计技巧之回溯算法

回溯算法实际上一个类似枚举的搜索尝试过程,主要是在搜索尝试过程中寻找问题的解,当发现已不满足求解条件时,就“回溯”返回,尝试别的路径。回溯法是一种选优搜索法,按选优条件向前搜索,以达到目标。但当探索到某一步时,发现原先选择并不优或达不到目标,就退回一步重新选择,这种走不通就退回再走的技术为回溯法,而

算法基础09——随机化算法

随机化算法(randomizedalgorithm),是这样一种算法,在算法中使用了随机函数,且随机函数的返回值直接或者间接的影响了算法的执行流程或执行结果。就是将算法的某一步或某几步置于运气的控制之下,即该算法在运行的过程中的某一步或某几步涉及一个随机决策,或者说其中的一个决策依赖于某种随机事件。

算法基础08——设计技巧之动态规划

动态规划(dynamicprogramming)是运筹学的一个分支,是求解决策过程(decisionprocess)最优化的数学方法。20世纪50年代初美国数学家R.E.Bellman等人在研究多阶段决策过程(multistepdecisionprocess)的优化问题时,提出了著名的最优化原理(p

算法基础07——设计技巧之分治算法

分治算法的基本思想是将一个规模为N的问题分解为K个规模较小的子问题,这些子问题相互独立且与原问题性质相同。求出子问题的解,就可得到原问题的解。即一种分目标完成程序算法,简单问题可用二分法完成。分:递归解决较小的问题(基本情况除外)治:从子问题的解构建原问题的解当我们求解某些问题时,由于这些问题要处理

算法基础06——设计技巧之贪婪算法

求解最优化问题的算法通常需要经过一系列的步骤,在每个步骤都面临多个选择。对于许多最优化问题,使用动态规划算法来求解有些杀鸡用牛刀了。可以使用更简单,更高效的算法——贪心算法。贪婪算法(又叫贪心算法)分阶段的工作。在每一个阶段,可以认为所做的决定是最好的,而不考虑将来后果。通常这意味着某个局部最优。这

算法基础05——字符串匹配

基本定义假设文本是一个长度为n的数组T[1..n],而模式是一个长度为m的数组P[1..m],其中m≤n,进一步假设P和T的元素都是来自一个有限字母集∑的字符。例如∑={0,1}或者∑={a,b,...,z}。字符数组P和T通常称为字符串。在数组T中,若偏移x位,即T[1+x,1+x+m]与模式串p

算法基础04——堆、拓扑及其它基础排序

堆排序堆排序(英语:Heapsort)是指利用堆这种数据结构所设计的一种排序算法。堆是一个近似完全二叉树的结构,并同时满足堆积的性质:即子结点的键值或索引总是小于(或者大于)它的父节点。就是用带排序数据数组构建大顶堆或小顶堆(升序或降速)。堆结构见堆相关。/***堆排序*/publicclassHe

算法基础03——排序之桶、基数、希尔排序

桶排序桶排序(Bucketsort)或所谓的箱排序,是一个排序算法,工作的原理是将数组分到有限数量的桶子里。每个桶子再个别排序(有可能再使用别的排序算法或是以递归方式继续使用桶排序进行排序)。桶排序是鸽巢排序的一种归纳结果。当要被排序的数组内的数值是均匀分配的时候,桶排序使用线性时间(Θ(n))。但

算法基础02——排序之快速&归并排序

定义:选择排序(Selectionsort)是一种简单直观的排序算法。它的工作原理是:第一次从待排序的数据元素中选出最小(或最大)的一个元素,存放在序列的起始位置,然后再从剩余的未排序元素中寻找到最小(大)元素,然后放到已排序的序列的末尾。以此类推,直到全部待排序的数据元素的个数为零。选择排序是不稳
Your browser is out of date!

Update your browser to view this website correctly. Update my browser now

×