专栏首页小詹同学统治世界的 10 大算法,你知道几个?

统治世界的 10 大算法,你知道几个?

原文 | The real 10 algorithms that dominate our world

作者 | George Dvorsky 编辑 | 深度学习这件小事

一篇有趣的文章《统治世界的十大算法》中,作者George Dvorsky试图解释算法之于当今世界的重要性,以及哪些算法对人类文明最为重要。

1 排序算法

所谓排序,就是使一串记录,按照其中的某个或某些关键字的大小,递增或递减的排列起来的操作。排序算法,就是如何使得记录按照要求排列的方法。排序算法在很多领域得到相当地重视,尤其是在大量数据的处理方面。一个优秀的算法可以节省大量的资源。

稳定的

  • 冒泡排序(bubble sort) — O(n^2)
  • 鸡尾酒排序(Cocktail sort,双向的冒泡排序) — O(n^2)
  • 插入排序(insertion sort)— O(n^2)
  • 桶排序(bucket sort)— O(n); 需要 O(k) 额外空间
  • 计数排序(counting sort) — O(n+k); 需要 O(n+k) 额外空间
  • 合并排序(merge sort)— O(nlog n);需要 O(n) 额外空间
  • 原地合并排序— O(n^2)
  • 二叉排序树排序 (Binary tree sort) — O(nlog n)期望时间;O(n^2)最坏时间;需要 O(n) 额外空间
  • 鸽巢排序(Pigeonhole sort)— O(n+k); 需要 O(k) 额外空间
  • 基数排序(radix sort)— O(n·k); 需要 O(n) 额外空间
  • Gnome 排序— O(n^2)
  • 图书馆排序— O(nlog n) withhigh probability,需要(1+ε)n额外空间

不稳定的

  • 选择排序(selection sort)— O(n^2)
  • 希尔排序(shell sort)— O(nlog n) 如果使用最佳的现在版本
  • 组合排序— O(nlog n)
  • 堆排序(heapsort)— O(nlog n)
  • 平滑排序— O(nlog n)
  • 快速排序(quicksort)— O(nlog n) 期望时间,O(n^2) 最坏情况;对于大的、乱数列表一般相信是最快的已知排序
  • Introsort—O(nlog n)
  • Patience sorting— O(nlog n+k) 最坏情况时间,需要额外的 O(n+ k) 空间,也需要找到最长的递增子串行(longest increasing subsequence)

不实用的

  • Bogo排序— O(n× n!) 期望时间,无穷的最坏情况。
  • Stupid sort— O(n^3); 递归版本需要 O(n^2)额外存储器
  • 珠排序(Bead sort) — O(n) or O(√n),但需要特别的硬件
  • Pancake sorting— O(n),但需要特别的硬件
  • stooge sort——O(n^2.7)很漂亮但是很耗时

2 傅立叶变换与快速傅立叶变换

傅立叶是一位法国数学家和物理学家,原名是JeanBaptiste Joseph Fourier(1768-1830), Fourier于1807年在法国科学学会上发表了一篇论文,论文里描述运用正弦曲线来描述温度分布,论文里有个在当时具有争议性的决断:任何连续周期信号都可以由一组适当的正弦曲线组合而成。

当时审查这个论文拉格朗日坚决反对此论文的发表,而后在近50年的时间里,拉格朗日坚持认为傅立叶的方法无法表示带有棱角的信号,如在方波中出现非连续变化斜率。直到拉格朗日死后15年这个论文才被发表出来。

谁是对的呢?拉格朗日是对的:正弦曲线无法组合成一个带有棱角的信号。但是,我们可以用正弦曲线来非常逼近地表示它,逼近到两种表示方法不存在能量差别,基于此,傅立叶是对的。

为什么我们要用正弦曲线来代替原来的曲线呢?如我们也还可以用方波或三角波来代替呀,分解信号的方法是无穷多的,但分解信号的目的是为了更加简单地处理原来的信号。

用正余弦来表示原信号会更加简单,因为正余弦拥有原信号所不具有的性质:正弦曲线保真度。一个正余弦曲线信号输入后,输出的仍是正余弦曲线,只有幅度和相位可能发生变化,但是频率和波的形状仍是一样的。且只有正余弦曲线才拥有这样的性质,正因如此我们才不用方波或三角波来表示。

3 Dijkstra 算法

Dijkstra算法是典型的算法。Dijkstra算法是很有代表性的算法。Dijkstra一般的表述通常有两种方式,一种用永久和临时标号方式,一种是用OPEN, CLOSE表的方式,这里均采用永久和临时标号的方式。注意该算法要求图中不存在负权边。

4 RSA算法变换

RSA是目前最有影响力的公钥加密算法,它能够抵抗到目前为止已知的绝大多数密码攻击,已被ISO推荐为公钥数据加密标准。

今天只有短的RSA钥匙才可能被强力方式解破。到2008年为止,世界上还没有任何可靠的攻击RSA算法的方式。只要其钥匙的长度足够长,用RSA加密的信息实际上是不能被解破的。但在分布式计算和量子计算机理论日趋成熟的今天,RSA加密安全性受到了挑战。

5 安全哈希算法

一种对输入信息(例如消息)进行摘要的算法。摘要过程能够完成下列特点:不同的输入信息绝对不会具有相同的指纹:相近输入信息经过摘要之后的输出信息具有较大的差异,同时计算上很难生产一个与给定输入具有相同指纹的输入。(即不可逆)。

6 整数因式分解

这是在计算机领域被大量使用的数学算法,没有这个算法,信息加密会更不安全。该算法定义了一系列步骤,得到将一合数分解为更小因子的质数分解式。这被认为是一种FNP问题,它是NP分类问题的延伸,极其难以解决。

许多加密协议(如RSA算法)都基于这样一个原理:对大的合数作因式分解是非常困难的。如果一个算法能够快速地对任意整数进行因式分解,RSA的公钥加密体系就会失去其安全性。

量子计算的诞生使我们能够更容易地解决这类问题,同时它也打开了一个全新的领域,使得我们能够利用量子世界中的特性来保证系统安全。

7 链接分析

链接分析,源于对Web结构中超链接的多维分析。当前其应用主要体现在网络信息检索、网络计量学、数据挖掘、Web结构建模等方山。作为Google的核心技术之一,链接分析算法应用已经显现出j惊人的商业价值。

8 比例积分微分算法

你是否曾经用过飞机、汽车、卫星服务或手机网络?你是否曾经在工厂工作或是看见过机器人?如果回答是肯定的,那么你应该已经见识过这个算法了。

大体上,这个算法使用一种控制回路反馈机制,将期望输出信号和实际输出信号之间的错误最小化。无论何处,只要你需要进行信号处理,或者你需要一套电子系统,用来自动化控制机械、液压或热力系统,这个算法都会有用武之地。

可以这样说,如果没有这个算法,现代文明将不复存在。

9 数据压缩算法

在现今的电子信息技术领域,正发生着一场有长远影响的数字化革命。由于数字化的多媒体信息尤其是数字视频、音频信号的数据量特别庞大,如果不对其进行有效的压缩就难以得到实际的应用。因此,数据压缩技术已成为当今数字通信、广播、存储和多媒体娱乐中的一项关键的共性技术。

10 随机数生成

在统计学的不同技术中需要使用随机数,比如在从统计总体中抽取有代表性的样本的时候,或者在将实验动物分配到不同的试验组的过程中,或者在进行蒙特卡罗模拟法计算的时候等等。

本文分享自微信公众号 - 小詹学Python(xiaoxiaozhantongxue)

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2019-11-04

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 「时间」与「空间」复杂度

    算法(Algorithm)是指用来操作数据、解决程序问题的一组方法。对于同一个问题,使用不同的算法,也许最终得到的结果是一样的,比如排序就有前面的十大经典排序和...

    小小詹同学
  • 支持中文的算法可视化网站,你想要的算法这都有

    上次文摘菌给大家推荐了一个能让算法动起来的开源项目之后,有热心的读者给文摘菌推荐了另一个算法可视化的网站。文摘菌打开之后,立即被起画风所折服,所以决定探索一番。

    小小詹同学
  • 关于程序员的那些事~

    小小詹同学
  • 搞算法的我们,不知道这些算法怎么行

    分享 动一动手指,分享给向我们一样需要的人 这是一篇有趣的文章,George Dvorsky试图解释算法之于当今世界的重要性,以及哪些算法对人类文明最为重要,如...

    昱良
  • 加权有向图----无环情况下的最短路径算法

    SuperHeroes
  • [AWR报告]In-memory Sort %

    从这期开始讲解awr报告的部分,上期说的是awr整体的部分,今天开始对里面的细节说起

    bsbforever
  • 【机器学习】CS229课程笔记notes1翻译-Part II分类和logistic回归

          我们现在谈论分类问题。分类问题与回归问题类似,区别是在分类问题中,我们现在想要预测的y值只取少量的离散值。现在,我们聚焦于二值分类问题,y只取两个值...

    魏晓蕾
  • Python中对list进行排序

    很多时候,我们需要对List进行排序,Python提供了两个方法 对给定的List L进行排序, 方法1.用List的成员函数sort进行排序 方法2.用bu...

    py3study
  • RSA数学运算的魅力

    Rivest哥、Shamir哥和Adleman哥发明了RSA。Rivest哥也发明了家喻户晓 RC4对称算法。RSA,一种公钥算法,通信双方使用不对称密钥,解决...

    mariolu
  • python pandas 基础之二

    pandas可以将两个数据的索引对齐;在算术的时候,如果一个索引,两个数据结构都有,就把它们元素运算,否则结果显示为NaN。

    小末快跑

扫码关注云+社区

领取腾讯云代金券