分治法
在计算机科学中，分治法（）是建基於多項分支遞歸的一种很重要的算法範式。字面上的解释是“分而治之”，就是把一个复杂的问题分成两个或更多的相同或相似的子问题，直到最后子问题可以简单的直接求解，原问题的解即子问题的解的合并。 这个技巧是很多高效算法的基础，如排序算法（归并排序、快速排序）、大數乘法（Karatsuba算法）、、語法解析（如）、，以及离散傅里叶变换（FFT）。 另一方面，理解及設計分治法算法的能力需要一定時間去掌握。正如以歸納法…
标签：#算法
共 60 篇文章
埃拉托色尼筛法
埃拉托色尼筛法（，），或作埃拉托斯特尼筛法，簡稱-{zh-cn:埃氏筛; zh-tw:埃氏篩; zh-hk:愛氏篩}-，是一种用來質數的筛法，得名於古希臘數學家埃拉托色尼。其基本步骤是從最小的質數2開始，將该質數的所有倍數標記成合數，而下一个尚未被标记的最小自然数3即是下一个質數。如此重复这一过程，将各个质数的倍数标记为合数并找出下一个质数，最终便可找出一定範圍內所有質數。 埃拉托色尼筛法可能在埃拉托色尼的时代之前就已经为人所知，并记载…
最小平方頻譜分析法
最小平方頻譜分析法（）是一種利用最小平方法尋找適配於資料點之最佳正弦曲線，以估算頻譜的方法。其數學原理與科學界中最常用的傅立葉分析相似。 最小平方頻譜分析法也稱為凡尼切克法（Vaníček method）、隆布法（Lomb method）或隆布—史卡構法（Lomb–Scargle method），分別取名自對其有所貢獻的、尼可拉斯·隆布（Nicholas R. Lomb）。然而，大多數以上述理論為基礎開發的方法僅適用於取樣間距相等的訊號…
裝置指紋
裝置指紋（或设备指纹、机器指纹）是以识别目的而收集的设备软硬件信息。 形式 不同场景对其称呼不同，可有數位指紋、瀏覽器指紋等，是遠端網站在裝置（電腦、手機、平板，甚至智慧家電）連接時收集並累積的資訊。 即使在浏览器中无法读取或存储持久Cookie、隐藏用户端IP地址或切换到同一设备的另一種浏览器时，设备指纹也可用于完全或部分识别单部设备。 信息通常用哈希算法同化为简短的标识符。 来源 众多来源均可称为设备指纹的源头，如： IP地址 MA…
算法
-{zh-hans:]];zh-hant:]]}- 算法（），在数学（算学）和计算机科学中指一个被定义好的、计算机可施行其指示的有限步骤或次序，常用于计算、数据处理和自动推理。算法可以使用条件语句通过各种途径转移代码执行（称为自动决策），并推导出有效的推论（称为自动推理），最终实现自动化。 相反，启发式是一种解决问题的方法，可能没有完全指定，也可能不能保证正确或最优的结果，尤其是在没有明确定义的正确或最优结果的问题领域。例如，社交媒体推…
星期的計算
星期的計算是能够計算出某一指定日期是在一周中的哪一天的一类算法。多種數學算法均可計算出過去或未來某一指定日期，是屬於一周中的星期幾，包括判决日法则（Doomsday Rule），Babwani公式等，但其實這些算法皆基于类似的机制相互变化而来，只是透過不同規則取得相同結果。 算法的典型應用，是計算某人的出生日期或某重大事件的發生日期，是在一周中的哪一天。 簡介 差不多所有星期算法的基礎皆可歸納如下： #从一個已知的日子作为起始日，一般采…
PSRS算法
问题的初步处理 PSRS算法（Parallel Sorting by Regular Sampling）：首先设待处理里序列长n，并行机上有p个处理器。为了使问题简单，我们假设n是p的整倍数。于是将这n个元素划分为p段，每段中有n/p个元素，将这p段分给p个处理器。注意，执行PSRS算法的并行机必须是多指令流多数据流（MIMD）的。 算法描述 让各个处理器并行的调用串行排序算法进行局部排序； 从每个有序段中选p个样本元素，共p^2个样本…
SimHash
SimHash是一种局部敏感的散列算法，由Moses Charikar提出。例如，当两个字符串只有细微差别时，它们的Simhash散列值同样会非常接近，这种特征就称为局部敏感。因此，Simhash可用于检查两项内容的相似程度，如文档去重、检测垃圾邮件和近似重复内容、被Google爬虫用于查找近似重复页面等。在2021年，谷歌宣布决定在新发布的FLoC系统中使用该算法。 参考文献
随机化算法
隨機化演算法（）是在邏輯或執行過程中使用隨機性的演算法。這類演算法通常使用均勻隨機位元作為輔助輸入，以引導演算法的行為，並期望在所有可能的隨機選擇之平均情況下取得良好效能。因此，隨機化演算法的執行時間、輸出結果，或兩者都可能是隨機變數。 隨機化演算法可依其對正確性與執行時間的保證分為不同類型。一類演算法會使用隨機輸入，並總是以正確答案終止，其執行時間可能根據隨機選擇而改變，這類演算法稱為拉斯維加斯演算法。另一類演算法通常具有固定或有界的…
秦九韶算法
秦九韶算法是中国南宋时期的数学家秦九韶表述求解一元高次多项式的值的算法——正负开方术。它也可以配合牛顿法用来求解一元高次多项式的根。 历史 《中国科学札记》论秦九韶玲珑开方]] 19世纪初，英国数学家重新发现并证明，後世称作霍纳算法（、）。但是，19世纪英国传教士偉烈亞力 Alexander Wylie. (1815–1887) 最早对霍纳的发明权提出质疑。他在1852年著的《中国科学札记》（Jottings on the Scienc…
黄金分割搜索
黄金分割搜索是一种通过不断缩小单峰函数的最值的已知范围，从而找到最值的方法。它的名称源于这个算法保持了间距具有黄金分割特性的三个点。这个算法与斐波那契搜索和二分查找关系紧密。黄金分割搜索是由Kiefer提出的，而斐波那契搜索是由Avriel和Wilde所提出。 内容 基本概念 上图表示了算法中找最小值的一个步骤。f(x)的函数值位于垂直坐标轴上，参数x位于水平坐标轴。已经有三个位于函数f(x)上的点的值被计算出来。: x_1，x_2，和…
大步小步算法
在群论中，大步小步算法（）是发明的一种中途相遇算法，用于计算离散对数或者有限阿贝尔群的阶。其中离散对数问题在公钥加密领域有着非常重要的地位。 许多常用的加密系统都基于离散对数极难计算这一假设——计算越困难，这些系统提供的数据传输就越安全。增加离散对数计算难度的一种方法，是把密码系统建立在更大的群上。 理论 这是一种空间换时间的算法，实质上是求解离散对数的朴素算法（枚举并试乘）的一个相当简单的改进。 给出一个 n 阶循环群 G 、该群的一…
最长公共子序列
最长公共子序列（LCS）是一个在一个序列集合中（通常为两个序列）用来查找所有序列中最长子序列的問題。这与查找最長公共子串的问题不同的地方是：子序列不需要在原序列中占用连续的位置 。最长公共子序列问题是一个经典的计算机科学问题，也是程序，比如Diff工具，和生物信息学应用的基础。它也被广泛地应用在版本控制，比如Git用来调和文件之间的改变。 定義 一个数列S，如果分别是两个或多个已知数列的子序列，且是所有符合此条件序列中最长的，则S称为已…
对立度算法
对立度算法是一种根据对立度进行计算的智能算法。其中，对立度是指两种数据对象之间的对立程度；若对象之间对立程度越高，说明其距离越远；若对象之间对立度程度越低，说明其距离越近。12345 应用 对立度算法已经应用在了多个安全工程领域，例如 对立度算法在金属磨损中的预测应用，通过对比BP神经网络算法，证明了算法的精度（SCI WOS: 000348343800010; EI Accession Number: 20150200417176）。…
托马苏洛算法
托马苏洛算法（）是IBM罗伯特·托马苏洛1967年所研发用来改善处理器乱序执行指令级并行性的硬件算法。 概述 在处理器中，先后执行的指令之间经常具有相关性（例如后一条指令用到前一条指令向寄存器写入的结果），因此早期简单的处理器使后续指令停顿，直到其所需的资源已经由前序指令准备就绪。托马苏洛算法则通过动态调度的方式，在不影响结果正确性的前提下，重新排列指令实际执行的顺序（乱序执行），提高时间利用效率。IBM System/360 Mode…
萤火虫算法
萤火虫算法（Firefly Algorithm）是一种启发式算法，灵感来自于螢火蟲闪烁的行为。萤火虫的闪光，其主要目的是作为一个信号系统，以吸引其他的萤火虫。时为剑桥大学研究员的杨新社提出了萤火虫算法，其假设为： 萤火虫不分性别，这样一个萤火虫将会吸引到所有其他的萤火虫; 吸引力与它们的亮度成正比，对于任何两个萤火虫，不那么明亮的萤火虫被吸引，因此移动到更亮的一个，然而，亮度又随着其距离的增加而减少; 如果没有比一个给定的萤火虫更亮的萤…
施特拉森演算法
施特拉森演算法（）是一個計算矩陣乘法的演算法，時間複雜度為O(n^{\log_2 7}) = O(n^{2.807})。 簡介 施特拉森演算法在1969年由沃爾克·施特拉森所提出，是第一個時間複雜度低於O(n^3)的矩陣乘法演算法。由於演算法簡單理解，且為第一個被提出來的特性，常被演算法教材拿來當作主定理（）計算時間複雜度的例子。 另外，因為施特拉森演算法證明了矩陣乘法存在時間複雜度低於O(n^3)的演算法，使得更多學者投入研究，尋找更…
長除法
長除法也稱為直式除法（），是算术中除法的演算法，可以處理多位數的除法，而且很簡單，可以用紙筆計算。長除法將除法分為許多由減法及乘法組合的步驟。長除法中，被除數會除以除數，得到一個數字，稱為商數。長除法將除法分為許多簡單的步驟，因此可以處理任意長度數字的除法。長除法可以處理整數除法、小數除法、多项式除法，也可以處理有餘數的歐幾里德除法。 長除法的簡化版稱為短除法，若除數只有一位數時，會用短除法代替長除法。也是一種處理長除法的作法，比較沒有…
先进不出
先进不出（，缩写：），有时也称先进仍在（，缩写：），是计算机科学中戏仿照先进先出（FIFO）算法和先进后出（FILO）算法而提出的一种幽默的调度算法。 原理 先进不出算法的工作原理是将所有的被调度任务永久保留。不管有多少需要等待调度的任务，实际上永远没有任何任务将被调度。这使得先进不出算法极其容易实现出来，但是这在现实中是毫无用途的。一个有状态的先进不出队列可以导致内存泄漏。这个算法是在Signetics 25120只写存储器的数据手册…
遗传算法
遗传算法（）是计算数学中用于解决最佳化的搜索算法，是进化算法的一种。进化算法最初是借鉴了进化生物学中的一些现象而发展起来的，这些现象包括遗传、突变、自然选择以及杂交等等。 遗传算法通常实现方式为一种计算机模拟。对于一个最优化问题，一定数量的候选解（称为个体）可抽象表示为染色體，使种群向更好的解进化。传统上，解用二进制表示（即0和1的串），但也可以用其他表示方法。进化从完全随机个体的种群开始，之后一代一代发生。在每一代中评价整个种群的适应…