关于编程或者特定语言功能，哪种算法对影响最大？

在所有这些时刻，我们突然之间都知道，只是知道，我们在最终了解程序员所编写的算法的基础上，已经迈出了重要的一步。谁的想法和代码给我们带来魔力？

解决方案

回答

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

回答

这是一个缓慢的:)

通过了解Duffs设备和XOR交换，我从总体上了解了C和计算机的知识

编辑：

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

回答

1989年在大学里引用"迭代是人的，递归神的"。

P.S.在等待邀请加入时由Woodgnome发表

回答

我不知道这是否可以算是一种算法，或者只是一种经典的破解方法。无论哪种情况，它都有助于我开始思考。

交换2个整数而不使用中间变量(在C ++中)

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

回答

对我来说，凯利与波尔(Kelly＆Pohl)撰写的《关于C的书》中的简单互换演示了按引用调用，当我第一次看到它时，就让我失望了。我看了看，然后指针跳到适当的位置。逐字。 。 。

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

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

回答

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

可替代地，用于斐波那契数列的递归算法和数字的计算能力证明了递归算法的相反情况，该递归算法用于递归而不是提供良好的价值。

回答

通用算法：

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

数值相关：

• Euclid算法用于计算两个整数的gcd：第一个算法简单，优雅，功能强大，具有很多泛化；
• 快速整数乘法(例如，Cooley-Tukey)；
• 牛顿迭代可反转/查找根，这是一个非常强大的元算法。

与数论有关：

• 与AGM相关的算法(示例)：导致计算pi的算法非常简单，优雅(甚至更多！)，尽管该理论非常深刻(高斯从中引入了椭圆函数和模块化形式，所以可以说它诞生了代数几何...);
• 数字场筛(用于整数分解)：非常复杂，但理论效果很好(对于AKS算法也是如此，这证明PRIMES在P中)。

我也很喜欢研究量子计算(例如，Shor和Deutsch-Josza算法)：这教会了我们开箱即用的思维。

如我们所见，我有点偏向于面向数学的算法:)

回答

由于某种原因，Bubble Sort一直对我很突出。不是因为它优雅或者好，而是因为我想它有一个愚蠢的名字。

回答

Fibonacci的迭代算法，因为对我而言，它确定了最优雅的代码(在这种情况下为递归版本)不一定是最高效的事实。

详细说明" fib(10)= fib(9)+ fib(8)"方法意味着将fib(9)评估为fib(8)+ fib(7)。因此，对fib(8)的评估(以及针对fib7，fib6的评估)将全部评估两次。

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

在编程时，我倾向于争取简单，优美的代码，但这是算法，使我认识到，这并不是编写优质软件的最终目的，最终最终用户不会这样做。不在乎代码的外观。

回答

这听上去很琐碎，但对当时的我来说是一个启示。
我当时是在我的第一门编程课(VB6)上，教授刚刚教给我们有关随机数的信息，他给出了以下指示："创建一个虚拟彩票机。想象一下一个装有100个标记为0到99的乒乓球的玻璃球。随机挑选它们并显示它们的编号，直到全部被选中为止，没有重复。"

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

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

我知道这听起来让人有点麻木，但是那是"编程开关"突然出现在我脑海中的那一刻。这是编程从尝试学习一种奇怪的外语到试图找出一个令人愉快的难题的那一刻。一旦我在编程和乐趣之间建立了思维上的联系，实际上并没有阻止我。

回答

快速排序：在我上大学之前，我从未质疑过暴力泡沫排序是最有效的排序方法。从直观上看，它似乎很明显。但是暴露于诸如Quicksort之类的非显而易见的解决方案使我了解了这些显而易见的解决方案，以了解是否有更好的解决方案可用。

回答

The iterative algorithm for Fibonacci, because for me it nailed down the fact that the most elegant code (in this case, the recursive version) is not necessarily the most efficient.
  
  The iterative method, (curr = prev1 + prev2 in a forloop) does not tree out this way, nor does it take as much memory since it's only 3 transient variables, instead of n frames in the recursion stack.

我们知道斐波那契有一个封闭形式的解决方案，它允许以固定的步骤数直接计算结果，对吗？即(phin(1 phi)n)/ sqrt(5)。它应该产生一个整数总是让我感到有些惊讶，但是确实如此。

phi当然是黄金分割率； (1 + sqrt(5))/ 2.

回答

Minimax告诉我国际象棋程序不是很聪明，他们只能认为比我们可以采取的行动更多。

回答

@克里希纳·库玛(Krishna Kumar)

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

回答

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

回答

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

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

其中foo($)表示一个计算密集型表达式，该表达式采用$(依次列出列表中的每个项目)并生成要比较的相应值。

回答

Haskell中的Quicksort：

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

尽管当时我无法编写Haskell，但我确实了解了此代码以及递归和quicksort算法。只是点击一下就到了...

回答

布雷森纳姆(Bresenham)的线条绘制算法使我对实时图形渲染产生了兴趣。这可用于渲染诸如3D模型渲染之类的填充多边形(如三角形)。

回答

递归下降解析我记得让我印象深刻的是，如此简单的代码可以完成看起来如此复杂的事情。

回答

对我来说，它是弱堆排序算法，因为它表明(1)明智地选择数据结构(及其上运行的算法)在多大程度上会影响性能，以及(2)即使在古老的，众所周知的环境中也可以发现令人着迷的事物事物。 (弱堆排序是所有堆排序中最好的变体，八年后证明了这一点。)

回答

一种算法，通过将每个数字与当前素数列表进行比较来生成素数列表，如果找不到则将其添加，最后返回素数列表。思维弯曲有几种方式，其中最重要的一种就是使用部分完成的输出作为主要搜索条件的想法。

回答

在一个单词中为一个双链表存储两个指针使我难受一个教训，那就是我们确实可以在C中做非常糟糕的事情(保守的GC会带来很多麻烦)。

回答

我一直为解决方案感到最骄傲的是编写与DisplayTag软件包非常相似的内容。它教会了我很多有关代码设计，可维护性和重用性的知识。我在DisplayTag之前就写了它，并且它已经与NDA达成协议，因此我无法开源，但是我仍然可以在工作面试中谈论这个。

回答

这不是我的最爱，但是用于测试素数的Miller Rabin算法向我展示了几乎一直都是正确的，几乎总是足够好。 (即，不要仅仅因为概率算法有错误的可能性而对概率算法产生怀疑。)

回答

映射/缩小。两个简单的概念组合在一起，使数据处理任务的负载更易于并行化。

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

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

回答

我没有喜欢的东西-有很多漂亮的东西可供选择-但我一直很感兴趣的一个是BaileyBorweinPlouffe(BBP)公式，它使我们能够在不知道前几位的情况下计算pi的任意数字。

回答

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

回答

RSA向我介绍了模块化算术领域，可以用来解决令人惊讶的许多有趣问题！