皇冠上的珍珠 统治世界的十大算法

皇冠上的珍珠 统治世界的十大算法

软件正在统治世界。而软件的核心则是算法。算法千千万万，又有哪些算法属于“皇冠上的珍珠”呢arcos Otero 给出了他的看法。
什么是算法br>  通俗而言，算法是一个定义明确的计算过程，可以一些值或一组值作为输入并产生一些值或一组值作为输出。因此算法就是将输入转为输出的一系列计算步骤。
—Thomas H. Cormen，Chales E. Leiserson，算法入门第三版
简而言之，算法就是可完成特定任务的一系列步骤，它应该具备三大特征：
 1、有限
 2、指令明确
 3、有效
以下是 Marcos Otero 推荐的十大算法：
1、归并排序、快速排序及堆积排序

最好的排序算法跟需求密切相关，很难评判。但是从使用上说，这三种的使用频率更高。
归并排序由冯依曼于 1945 年发明。这是一种基于比较的排序算法，采用分而治之的办法解决问题，其阶是 O(n^2)。
快速排序可采用原地分割方法，也可采用分而治之算法。这不是一种稳定的排序算法，但对于基于 RAM（内存）的数组排序来说非常有效。
堆排序采用优先级队列来减少数据中的搜索时间。该算法也是原地算法，并非稳定排序。
这些排序算法相对于以前的冒泡排序算法等有了巨大改进，实际上我们今天的数据挖掘、人工智能、链接分析及包括 web 在内的大多数计算工具都要感谢它们。
2、傅里叶变换与快速傅里叶变换

我们的整个数字世界都使用这两个简单但非常强大的算法，其作用是将信 从时域转为频域或者反之。实际上，你看得到这篇文章得感谢这些算法。
互联 、你的 WiFi、智能手机、电话、计算机、路由器、卫星，几乎所有内置有计算机的东西都会以各种方式使用这两算法。如果不研究这些算法，你就拿不到电子、计算或通信方面的学位。
3、迪杰斯特拉（Dijkstra）算法

Dijkstra是一种图谱搜索算法。许多问题都可以建模为图谱，然后利用 Dijkstra 寻找两个节点之间的最短路径。如果没有 Dijkstra 算法，互联 的运营效率必将大大降低。虽然今天我们已经有了更好的寻找最短路径的解决方案，但出于稳定性的要求，Dijkstra 算法仍然被很多系统使用。
4、RSA算法
如果没有密码术和 络安全，互联 就不会像今天一样重要，因为电子商务和电子交易需要这些技术来 确保交易安全。而RSA算法是最重要的密码学算法之一。该算法由同名公司的创始人（Ron Rivest、Adi Shamir 和 Leonard Adleman）开发，它让密码学普及到了千家万户并奠定了密码术的应用基础。RSA 要解决的问题既简单又复杂：如何在独立平台与最终用户之间共享公钥。其解决方案是加密。RSA 加密的基础是一个十分简单的数论事实：将两个大素数相乘十分容易，但是想要对其乘积进行因式分解却极其困难，因此可以将乘积公开作为加密密钥。但在分布式 计算和量子计算机理论日趋成熟的今天，RSA 加密安全性受到了挑战。
5、安全哈希算法（SHA）
这个实际上并不算是算法，而是由美国国家标准技术研究所开发的一系列密码杂凑函数。但是这系列函数是全世界运作的基石。应用商店，电子邮件、反病毒、浏览器等在使用SHA系列函数，SHA 函数可用来确定下载的东西是否自己想要的东西，还是说遭遇了中间人攻击或钓鱼攻击。
6、整数因子分解
这是一个在计算领域使用频繁的数学算法。如果没有这一算法，密码术就会变得不安全得多。整数因子分解是用来将一个合数分解成一系列素因子的一系列步骤。整数因子分解可被视为是 FNP 问题（FNP 是难以解决的典型 NP 问题的扩展）。
许多密码协议均基于难以分解的大型合数或相关问题。比方说前面提到的 RSA 问题。如果有算法能够有效分解任意数字，那么就会使得基于 RSA 的公钥密码系统陷入不安全的境地。
而量子计算的诞生则令此问题的解决变得容易，从而也打开了一个全新的领域，可利用量子世界的属性来令系统更加安全。
7、链接分析