您最喜欢的算法及其教给您的课程[关闭]

StackOverflow https://stackoverflow.com/questions/26301

  •  09-06-2019
  •  | 
  •  

题

哪种算法让您对编程或特定语言功能了解得最多？

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

有帮助吗？

解决方案

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

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

其他提示

通用算法：

  • 快速排序（及其平均复杂度分析）表明，随机化您的输入可能是一件好事！；
  • 平衡树（AVL树 例如），一种平衡搜索/插入成本的巧妙方法；
  • 迪克斯特拉 和 福特-富尔克森 图算法（我喜欢第二个算法有很多应用）；
  • LZ* 系列压缩算法（陆ZW 例如），数据压缩对我来说听起来很神奇，直到我发现它（很久以前:)）；
  • 这 快速傅里叶变换, ，无处不在（在许多其他算法中重复使用）；
  • 这 单纯形 算法，也无处不在。

数值相关：

  • 计算两个整数的 gcd 的欧几里得算法：第一个算法，简单而优雅，功能强大，有很多概括；
  • 整数的快速乘法 (库利-图基 例如）;
  • 牛顿迭代求逆/求根，是一种非常强大的元算法。

数论相关：

  • 年度股东大会相关算法（例子）：导致计算 pi 的算法非常简单而优雅（还有更多！），尽管理论相当深刻（高斯从中引入了椭圆函数和模形式，所以你可以说它催生了代数几何......）；
  • 这 数域筛 （对于整数分解）： 非常 复杂，但相当不错的理论结果（这也适用于 AKS 算法，证明了 PRIMES 在 P) 中。

我也喜欢研究量子计算（肖尔 和 德意志乔萨 算法为例）：这教会你跳出框框思考。

正如你所看到的，我有点偏向于数学导向的算法:)

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 的解决方案可能比问题 A 的解决方案更简单。

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

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

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

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

我知道这听起来很明显，但就在那时，“编程开关”在我的脑海中被翻转。这是编程从尝试学习一门陌生的外语转变为尝试解决一个有趣的谜题的时刻。一旦我在编程和乐趣之间建立了联系，就真的没有什么能阻止我了。

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

Bresenham 画线算法 让我对实时图形渲染产生了兴趣。这可用于渲染填充多边形（例如三角形），以进行 3D 模型渲染等操作。

递归下降解析 - 我记得如此简单的代码如何能够完成看似复杂的事情，给我留下了深刻的印象。

Haskell 中的快速排序：

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

虽然我当时不会写 Haskell，但我确实理解了这段代码以及递归和快速排序算法。它只是发出咔嗒声，然后就在那里......

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

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

迭代方法（for 循环中的 curr = prev1 + prev2）不会以这种方式进行树化，也不会占用那么多内存，因为它只有 3 个瞬态变量，而不是递归堆栈中的 n 帧。

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

出于某种原因我喜欢 施瓦兹变换

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

其中 foo($) 表示计算密集型表达式，需要 $ （依次列出列表中的每个项目）并生成要进行比较的相应值。

极小极大 告诉我国际象棋程序并不聪明，它们只是能比你想出更多的棋步。

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

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

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

快速排序：在我上大学之前，我从未质疑过暴力冒泡排序是否是最有效的排序方式。这在直觉上似乎是显而易见的。但接触像快速排序这样的非显而易见的解决方案教会我超越明显的解决方案，看看是否有更好的解决方案。

对我来说，它是弱堆排序算法，因为它显示了（1）明智选择的数据结构（以及处理它的算法）对性能的影响有多大；（2）即使在古老的、众所周知的中也可以发现令人着迷的东西事物。（弱堆排序是所有堆排序的最佳变体，它是 已证实的 八年后。）

这是一个缓慢的过程：）

通过理解，我总体上学到了很多关于 C 语言和计算机的知识 达夫斯装置 和 异或交换

编辑：

@贾森·Z, ，这就是我的 XOR 交换:) 很酷不是吗。

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

我没有 最喜欢的 ——有很多美丽的东西可供选择——但我一直觉得有趣的是 贝利-博温-普洛夫 (BBP) 公式, ，它使您能够计算 pi 的任意数字，而无需了解前面的数字。

RSA 带我进入了模算术的世界，它可以用来 解决 A 奇怪 数字 的 有趣的 问题!

没有教会我太多，但是 约翰逊-特罗特算法 总是让我大吃一惊。

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

他们教给我的：

  • 的紧凑表示 任何 问题很重要；小即是美
  • 可以使用递归应用的一小组约束/减少来实现此目的
  • 对于对称性问题，转换为规范形式应该是考虑的第一步
  • 并不是所有的文学作品都会被阅读。Knuth 在 BDD 发明/推出几年后才发现它们。（并花了近一年的时间调查它们）

对我来说，Kelly & Pohl's 的简单交换 C 语言书籍 当我第一次看到它时，演示按引用调用让我大吃一惊。我看了看，指针卡入到位。逐字。。。

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

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

这 汉诺塔算法 是最美丽的算法之一。它展示了如何使用递归以比迭代方法更优雅的方式解决问题。

或者，斐波那契数列的递归算法和数字的计算幂展示了递归算法的相反情况，即为了递归而不是提供良好的价值而使用递归算法。

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

迭代方法（for 循环中的 curr = prev1 + prev2）不会以这种方式进行树化，也不会占用那么多内存，因为它只有 3 个瞬态变量，而不是递归堆栈中的 n 帧。

您知道斐波那契有一个封闭形式的解决方案，允许以固定的步骤数直接计算结果，对吧？即，(phin - (1 - Φ)n) / 开方(5)。我总是觉得这应该产生一个整数，这有点值得注意，但确实如此。

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

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

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

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

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

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

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

不是我最喜欢的，但是 米勒拉宾算法 测试素性告诉我，几乎所有时候都是正确的，几乎所有时候都足够好了。（IE。不要仅仅因为概率算法有出错的可能性就不信任它。）

@克里希纳库马尔

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

许可以下： CC-BY-SA 和 归因
不隶属于 StackOverflow
scroll top