您最喜欢的算法和它教给您的课程

Question

什么算法教你最多的编程或特定的语言功能？

我们所有人都知道,我们已经知道,我们已经学会了一个重要的未来课程,这是基于最终理解程序员编写的算法,在演化阶梯上的几个步骤.谁的想法和代码对你有神奇的触动？

Answer 1

一般算法:

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

数值相关:

• Euclid算法计算两个整数的gcd:第一个算法之一,简单而优雅,功能强大,有很多概括;
• 整数的快速乘法(例如Cooley-Tukey);
• 牛顿迭代反转/找到一个根,一个非常强大的元算法.

数论相关:

• 与AGM相关的算法(例子):导致非常简单和优雅的算法来计算pi(以及更多!),虽然理论非常深刻(高斯从中引入椭圆函数和模块化形式,所以你可以说它生了代数几何...);
• 在数字域筛(整数分解):很复杂,但相当不错的理论成果(这也无二AKS算法,证明了素数是P).

我也很喜欢研究量子计算(例如Shor和Deutsch-Josza算法):这教你开箱即用.

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

Answer 2

1989年大学时期引用的"迭代是人类,是对神圣的回归".

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

Answer 3

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倍! ".

然后老师给你Floyd-Warshall.而你的思想爆炸了.然后你开始讨论算法的简单程度.它只是一个三重嵌套的循环.它只为其数据结构使用一个简单的数组.

对我来说最令人瞩目的部分是以下实现:说你有问题A的解决方案.然后你有一个更大的"超级问题"B,它包含问题A.问题B的解决方案实际上可能比解决方案更简单.问题A.

Answer 4

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

Answer 5

Quicksort.它向我展示了递归可以是强大而有用的.

Answer 6

这可能听起来微不足道,但这对我来说是一个启示.我参加了我的第一个编程课程(VB6),教授刚给我们讲了随机数,他给出了以下说明:"创建一个虚拟彩票机.想象一下,玻璃球上有100个标有0到99的乒乓球.随机挑选它们并显示它们的编号,直到它们全部被选中,没有重复."

其他人都这样编写了他们的程序:选择一个球,将其编号放入"已选择的列表"中,然后选择另一个球.检查它是否已被选中,如果是这样选择另一个球,如果没有将它的号码放在"已选择的列表"等....

当然,到最后他们正在进行数百次比较,以找到尚未被挑选的几个球.这就像选择它们后将球扔回罐子里一样.我的启示是在采摘后丢球.

我知道这听起来令人头晕目眩,但这就是"编程开关"在我脑海中翻转的那一刻.这是编程从尝试学习一门奇怪的外语到试图找出一个令人愉快的谜题的时刻.一旦我在编程和乐趣之间建立了心理联系,那真的没有阻止我.

Answer 7

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

Answer 8

递归下降解析 - 我记得如此简单的代码可以做一些看似复杂的事情给我留下了非常深刻的印象.