algorithm - 你最喜欢的算法和它教给你的教训

Question

在编程或特定语言特性方面，哪种算法教给你最多？

我们都有过这样的时刻，突然我们知道，只是知道，我们已经为未来吸取了重要的一课，基于最终理解程序员编写的算法，在进化阶梯上走了几步。谁的想法和代码对你有魔力？

score 33 · Accepted Answer

通用算法：

快速排序（它是平均复杂度分析），表明随机化输入可能是一件好事！
平衡树（例如AVL 树），一种平衡搜索/插入成本的巧妙方法；
图上的Dijkstra和Ford-Fulkerson算法（我喜欢第二个有很多应用的事实）；
LZ* 系列压缩算法（例如LZW），数据压缩对我来说听起来有点神奇，直到我发现它（很久以前:)）；
FFT，无处不在（在许多其他算法中重复使用）；
单纯形算法，无处不在。

数值相关：

欧几里德算法计算两个整数的 gcd：最早的算法之一，简单优雅，功能强大，有很多推广；
整数的快速乘法（例如Cooley-Tukey）；
牛顿迭代求逆/求根，一种非常强大的元算法。

数论相关：

AGM相关算法（示例）：导致计算 pi 的非常简单和优雅的算法（以及更多！），虽然理论非常深刻（高斯从它引入了椭圆函数和模形式，所以你可以说它诞生了代数几何...）；
数域筛（用于整数分解）：非常复杂，但理论上的结果非常好（这也适用于AKS算法，它证明了 PRIMES 在 P 中）。

我也很喜欢研究量子计算（例如Shor和Deutsch-Josza算法）：这教你跳出框框思考。

正如你所看到的，我对面向数学的算法有点偏见:)

score 19 · Accepted Answer

“迭代是人类，递归是神圣的”——1989 年在大学引用。

PS 在等待加入邀请时由 Woodgnome 发布

score 12 · Accepted Answer

Floyd-Warshall 全对最短路径算法

procedure FloydWarshall ()
   for k := 1 to n
     for i := 1 to n
        for j := 1 to n
          path[i][j] = min ( path[i][j], path[i][k]+path[k][j] );

这就是它很酷的原因：当你第一次在图论课程中学习最短路径问题时，你可能会从解决单源最短路径的 Dijkstra 算法开始。一开始很复杂，但后来你克服了它，你就完全理解了。

然后老师说“现在我们要解决相同的问题，但要针对所有来源”。你对自己说：“天啊，这将是一个更难的问题！它至少比 Dijkstra 的算法复杂 N 倍！！！ ”。

然后老师给你弗洛伊德-沃歇尔。你的头脑会爆炸。然后你开始为这个算法是多么的简单而哭泣。这只是一个三重嵌套循环。它的数据结构只使用一个简单的数组。

对我来说最令人大开眼界的部分是以下认识：假设您有问题 A 的解决方案。然后您有一个更大的“超级问题”B，其中包含问题 A。问题 B 的解决方案实际上可能比问题 B 的解决方案更简单问题A。

score 10 · Accepted Answer

这可能听起来微不足道，但对当时的我来说是一个启示。我在上我的第一堂编程课（VB6），教授刚刚教我们随机数，他给出了以下说明：“创建一个虚拟彩票机。想象一个装满 100 个乒乓球的玻璃球，标记为 0 到 99。随机挑选它们并显示它们的编号，直到它们都被选中，没有重复。”

其他人都这样编写程序：挑选一个球，将其编号放入“已选择列表”，然后再挑选一个球。检查它是否已经被选中，如果是，则选择另一个球，如果没有将其编号放在“已选中列表”等......

当然，到最后，他们进行了数百次比较，以找到尚未被挑选的少数球。这就像选择它们后将球扔回罐子里一样。我的启示是采摘后将球扔掉。

我知道这听起来很明显，但这是“编程开关”在我脑海中翻转的那一刻。这是编程从试图学习一门陌生的外语到试图找出一个有趣的谜题的那一刻。一旦我在编程和乐趣之间建立了这种心理联系，就真的没有人能阻止我。

score 10 · Accepted Answer

霍夫曼编码将是我的，我最初通过将编码文本的位数从 8 降至更少来制作自己的哑版本，但没有考虑根据频率可变位数。然后我在杂志的一篇文章中发现了霍夫曼编码，它开辟了许多新的可能性。

score 9 · Accepted Answer

9

快速排序。它向我展示了递归是强大而有用的。

于 2008-08-25T16:04:48.327 回答

score 7 · Accepted Answer

Bresenham 的线条绘制算法让我对实时图形渲染产生了兴趣。这可用于渲染填充的多边形，如三角形，用于 3D 模型渲染等。

score 6 · Accepted Answer

Recursive Descent Parsing——我记得如此简单的代码如何能做如此看似复杂的事情给我留下了深刻的印象。

score 4 · Accepted Answer

Haskell 中的快速排序：

qsort []     = []
qsort (x:xs) = qsort (filter (< x) xs) ++ [x] ++ qsort (filter (>= x) xs)

虽然当时我不会编写 Haskell，但我确实理解了这段代码以及递归和快速排序算法。它只是点击了一下，它就在那里......

score 3 · Accepted Answer

斐波那契的迭代算法，因为对我来说它确定了一个事实，即最优雅的代码（在这种情况下是递归版本）不一定是最有效的。

详细说明-“fib(10) = fib(9) + fib(8)”方法意味着 fib(9) 将被评估为 fib(8) + fib(7)。因此对 fib(8)（以及 fib7、fib6）的评估都将被评估两次。

迭代方法 (curr = prev1 + prev2 in a forloop) 不会以这种方式生成树，也不会占用太多内存，因为它只有 3 个瞬态变量，而不是递归堆栈中的 n 帧。

我在编程时倾向于追求简单、优雅的代码，但正是这种算法帮助我意识到，这并不是编写好软件的终极目标，最终用户也不会这样做。不在乎你的代码看起来如何。

score 3 · Accepted Answer

3

Minimax告诉我国际象棋程序并不聪明，它们只会比你想出更多的动作。

于 2008-08-26T14:04:17.420 回答

score 3 · Accepted Answer

出于某种原因，我喜欢Schwartzian 变换

@sorted = map  { $_->[0] }
          sort { $a->[1] cmp $b->[1] }
          map  { [$_, foo($_)] }
                @unsorted;

其中 foo($ ) 表示一个计算密集型表达式，它采用 $（依次为列表的每个项目）并生成相应的值，以便对其进行比较。

score 2 · Accepted Answer

我不知道这是否符合算法，或者只是一个经典的黑客。无论哪种情况，它都有助于让我开始跳出框框思考。

在不使用中间变量的情况下交换 2 个整数（在 C++ 中）

void InPlaceSwap (int& a, int &b) {
     a ^= b;
     b ^= a;
     a ^= b;
}

score 2 · Accepted Answer

快速排序：在我上大学之前，我从未质疑过暴力冒泡排序是否是最有效的排序方式。它看起来很直观。但是接触到像 Quicksort 这样的非显而易见的解决方案教会了我去审视那些显而易见的解决方案，看看是否有更好的解决方案可用。

score 2 · Accepted Answer

对我来说，它是弱堆排序算法，因为它展示了 (1) 明智选择的数据结构（以及处理它的算法）可以在多大程度上影响性能，以及 (2) 即使在旧的、知名的事物。（弱堆排序是所有堆排序中最好的变体，八年后证明了这一点。）

score 1 · Accepted Answer

这是一个缓慢的:)

通过了解Duffs 设备和XOR 交换，我总体上学到了很多关于 C 和计算机的知识

编辑：

@Jason Z，那是我的 XOR 交换 :) 很酷，不是吗。

score 1 · Accepted Answer

出于某种原因，冒泡排序对我来说一直很突出。不是因为它优雅或好，只是因为我想它有/有一个愚蠢的名字。

score 1 · Accepted Answer

斐波那契的迭代算法，因为对我来说它确定了一个事实，即最优雅的代码（在这种情况下是递归版本）不一定是最有效的。

迭代方法 (curr = prev1 + prev2 in a forloop) 不会以这种方式生成树，也不会占用太多内存，因为它只有 3 个瞬态变量，而不是递归堆栈中的 n 帧。

你知道斐波那契有一个封闭形式的解决方案，它允许以固定数量的步骤直接计算结果，对吧？即，(phi ⁿ - (1 - phi) ⁿ ) / sqrt(5)。我总是觉得这应该产生一个整数有些显着，但确实如此。

phi 当然是黄金比例；(1 + sqrt(5)) / 2。

score 1 · Accepted Answer

我没有最喜欢的——有很多漂亮的可供选择——但我一直觉得很有趣的是Bailey-Borwein-Plouffe (BBP) 公式，它使您能够计算任意位数的 pi不知道前面的数字。

score 1 · Accepted Answer

1

RSA向我介绍了模运算的世界，它可以用来解决数量惊人的有趣问题！

于 2010-08-12T17:17:34.630 回答

score 1 · Accepted Answer

1

没有教给我太多东西，但Johnson-Trotter 算法总是让我大吃一惊。

于 2012-12-13T06:44:22.740 回答

score 1 · Accepted Answer

二元决策图虽然形式上不是算法而是数据结构，但可以为各种（布尔）逻辑问题提供优雅且最小的解决方案。它们的发明和开发是为了最大限度地减少芯片设计中的门数，可以被视为硅革命的基础之一。由此产生的算法非常简单。

他们教给我的：

任何问题的简洁表示很重要；小就是美
可以使用一小组递归应用的约束/减少来实现这一点
对于对称性问题，首先要考虑转换为规范形式
不是每一篇文学作品都被阅读。Knuth 在 BDD 的发明/引入几年后发现了他们。（并花了将近一年的时间调查它们）

score 0 · Accepted Answer

对我来说，当我第一次看到它时，Kelly & Pohl 的A Book on C中演示引用调用的简单交换让我大吃一惊。我看了看，指针突然就位。逐字。. .

void swap(int *p, int *q)
{
   int temp;

   temp = *p;
   *p = *q;
   *q = temp;
}

score 0 · Accepted Answer

河内塔算法是最漂亮的算法之一。它展示了如何使用递归以比迭代方法更优雅的方式解决问题。

或者，斐波那契数列的递归算法和一个数字的计算幂证明了递归算法的相反情况是为了递归而不是提供良好的价值。

score 0 · Accepted Answer

0

@克里希纳库马尔

按位解决方案比递归解决方案更有趣。

于 2008-08-26T14:05:57.200 回答

score 0 · Accepted Answer

一种通过将每个数字与当前素数列表进行比较来生成素数列表的算法，如果没有找到则添加它，并在最后返回素数列表。在几个方面令人费解，其中最重要的是使用部分完成的输出作为主要搜索条件的想法。

score 0 · Accepted Answer

在一个单词中为双向链表存储两个指针给我的教训是，你确实可以在 C 中做非常糟糕的事情（保守的 GC 会遇到很多麻烦）。

score 0 · Accepted Answer

我最自豪的解决方案是编写与 DisplayTag 包非常相似的东西。它教会了我很多关于代码设计、可维护性和重用的知识。我在 DisplayTag 之前就已经写好了，它被纳入 NDA 协议，所以我不能开源它，但我仍然可以在工作面试中滔滔不绝地谈论它。

score 0 · Accepted Answer

不是我最喜欢的，但用于测试素数的米勒拉宾算法向我展示了几乎所有时间都是正确的，几乎所有时间都足够好。（即不要仅仅因为概率算法有错误的概率而怀疑它。）

score 0 · Accepted Answer

映射/减少。两个简单的概念结合在一起，使大量数据处理任务更容易并行化。

哦...这只是大规模并行索引的基础：

http://labs.google.com/papers/mapreduce.html

score 0 · Accepted Answer

二分查找一定是最简单优雅的算法。当然需要对数据进行排序，为此合并排序算法也是最简单和优雅的。

score 0 · Accepted Answer

使用矩阵算法在 O(log N) 中计算斐波那契
使用傅里叶变换进行大数乘法

教训是可以在非常意想不到的领域找到解决方案，并且算法和数学的不同领域之间存在非常令人惊讶的联系。

score 0 · Accepted Answer

一些尚未被引用的算法、原理或技巧：

Union-Find算法可快速从数据集中提取组。
Zobrist 哈希码快速、可迭代且对冲突具有弹性。
约束编程是一种编程范式，可以在各种情况下产生令人惊讶的好结果。
蒙特卡洛树搜索是一套混合了树行走、随机化、优化的绝妙技术。

algorithm - 你最喜欢的算法和它教给你的教训

33 回答 33

Related

Reference