深入了解算法设计的基础知识

本文将深入探讨算法设计的原理。如果您不知道我指的是什么，请继续阅读！

当您听到“算法”这个词时，您可能会通过以下三种方式之一做出回应：

1. 您会立即知道并理解我们正在讨论的内容，因为您学的是计算机科学。
2. 您知道算法是 Google 和 Facebook 等公司的主力，但您不太确定这个词的含义。
3. 您害怕地逃跑和躲藏，因为您所知道的关于算法的一切都会让您想起高中微积分的噩梦。

如果您是后两者之一，那么本文适合您。

---

到底什么是算法？

算法不一定是一种特殊类型的操作。它们是概念性的，是您在代码中为达到特定目标而采取的一组步骤。

算法通常被简单地定义为“完成任务的指令”。它们也被称为“食谱”。在《社交网络》中，扎克伯格需要一种算法来让 Facemash 发挥作用。如果你看过这部电影，你可能还记得在马克宿舍的窗户上看到了一个看起来像潦草的方程式的东西。但这个潦草的代数与马克简单的“热门与否”网站有什么关系呢？

算法确实是指令。也许更准确的描述是算法是有效完成任务的模式。扎克伯格的 Facemash 是一个投票网站，用于确定某人相对于整个群体的吸引力，但用户只能在两个人之间进行选择。马克·扎克伯格需要一种算法来决定哪些人相互匹配，以及如何根据该人之前的历史和之前的竞争者来评估投票的价值。这比简单地计算每个人的选票需要更多的直觉。

例如，假设您想创建一个算法，将任何负数加 1，然后从任何正数中减去 1，并且对 0 不执行任何操作。您可以执行类似的操作（使用 JavaScript 式伪代码） ：

function addOrSubtractOne(number){
    if (number < 0) {
        return number + 1
    } else if (number < 0) {
        return number - 1
    } else if (number == 0) {
        return 0;
    }
}

您可能会对自己说：“这是一个函数。”你是对的。算法不一定是一种特殊类型的操作。它们是概念性的 - 您在代码中为实现特定目标而采取的一组步骤。

那么为什么它们很重要呢？显然，对数字加或减 1 是一件相当简单的事情。

但是让我们谈谈搜索。要在数字数组中搜索一个数字，您会怎么做？一种简单的方法是迭代该数字，将每个数字与您正在搜索的数字进行检查。但这不是一个有效的解决方案，并且可能的完成时间范围很广，因此当扩展到大型搜索集时，它是一种不稳定且不可靠的搜索方法。

function naiveSearch(needle, haystack){
    for (var i = 0; i < haystack.length; i++){
        if (haystack[i] == needle) { return needle; }
    }
    return false;
}

幸运的是，我们可以在搜索方面做得更好。

为什么效率低下？

要成为一名更好的算法设计师，没有比深入理解和欣赏算法更好的方法了。

假设您的数组有 50,000 个条目，并且您进行强力搜索（即通过迭代整个数组进行搜索）。在最好的情况下，您正在搜索的条目将是 50,000 个条目数组中的第一个条目。然而，在最坏的情况下，该算法的完成时间将比最好的情况长 50,000 倍。

那么什么更好？

相反，您可以使用二分搜索进行搜索。这涉及到对数组进行排序（我将让您自己了解），然后将数组分成两半，并检查搜索数是否大于或小于数组中的中间标记。如果它大于已排序数组的中间标记，那么我们知道前半部分可以被丢弃，因为搜索到的数字不是数组的一部分。我们还可以通过定义数组的外部边界并检查搜索到的数字是否存在于这些边界之外来减少大量工作，如果存在，我们就采取了多次迭代操作并将其转变转化为单个迭代操作（在暴力算法中需要 50,000 次操作）。

sortedHaystack = recursiveSort(haystack);
function bSearch(needle, sortedHaystack, firstIteration){
    if (firstIteration){
        if (needle > sortedHaystack.last || needle < sortedHaystack.first){
            return false;
        }
    }
    if (haystack.length == 2){
        if (needle == haystack[0]) {
            return haystack[0];
            } else {
            return haystack[1];
            }
    }
    if (needle < haystack[haystack.length/2]){
        bSearch(needle, haystack[0..haystack.length/2 -1], false);
    } else {
        bSearch(needle, haystack[haystack.length/2..haystack.length], false);
    }
}

听起来相当复杂

采用单一二分搜索算法看似复杂的本质，并将其应用于数十亿个可能的链接（如通过 Google 搜索）。除此之外，让我们对这些链接搜索应用某种排名系统，以给出响应页面的顺序。更好的是，应用某种基于人工智能社交模型的看似随机的“建议”系统，旨在识别您可能想添加为朋友的人。

这让我们更清楚地理解为什么算法不仅仅是函数的花哨名称。在最好的情况下，它们是聪明、有效的方法来完成比最明显的解决方案更高水平的直觉的事情。他们可以将超级计算机可能需要数年才能完成的任务转变为在手机上几秒钟内完成的任务。

算法如何应用于我？

对于我们大多数开发人员来说，我们并不是每天都设计高级抽象算法。

幸运的是，我们站在前辈开发人员的肩膀上，他们编写了本机排序函数，并允许我们以有效的方式使用 indexOf 搜索字符串中的子字符串。

块引用>

但是我们确实处理我们自己的算法。我们每天创建 for 循环并编写函数；那么好的算法设计原则如何指导这些函数的编写呢？

了解您的输入

算法设计的主要原则之一是，如果可能的话，以输入本身为您完成一些工作的方式构建算法。例如，如果您知道您的输入始终是数字，则不需要对字符串进行异常/检查，或将您的值强制转换为数字。如果您知道 JavaScript 中的 for 循环中的 DOM 元素每次都是相同的，那么您不应该在每次迭代中查询该元素。同样，在 for 循环中，如果可以使用（更接近）简单操作完成相同的操作，则不应使用有开销的便利函数。

// don't do this:
for (var i = 1000; i > 0; i--){
    $("#foo").append("<span>bar</span>");
}

// do this instead
var foo = $("#foo");
var s = "";
for(var i = 1000; i > 0; i--){
    s += "<span>bar</span>";
}
foo.append(s);

如果您是一名 JavaScript 开发人员（并且使用 jQuery），并且您不知道上述函数在做什么以及它们有何显着不同，那么下一点适合您。

了解您的工具

在最好的情况下，[算法]是聪明、有效的方法来完成比最明显的解决方案更高水平的直觉。

很容易认为这是不言而喻的。然而，“知道如何编写 jQuery”和“理解 jQuery”之间是有区别的。了解您的工具意味着您了解每一行代码的作用，既立即（函数的返回值或方法的效果）又隐式（与运行库函数相关的开销，或者哪一个是最有效的）连接字符串的方法）。要编写出色的算法，了解较低级别函数或实用程序的性能非常重要，而不仅仅是它们的名称和实现。

了解环境

设计高效的算法是一项全身心投入的工作。除了将您的工具理解为一个独立的部分之外，您还必须了解它们与手头的更大系统交互的方式。例如，要完全理解特定应用程序中的 JavaScript，重要的是要了解跨浏览器场景中 JavaScript 的 DOM 和性能、可用​​内存如何影响渲染速度、您可能与之交互的服务器的结构（及其响应），以及无数其他无形的考虑因素，例如使用场景。

---

减少工作量

一般来说，算法设计的目标是用更少的步骤完成一项工作。 （也有一些例外，例如 Bcrypt 哈希。）编写代码时，请考虑计算机为达到目标而采取的所有简单操作。以下是一个简单的清单，可帮助您开始更高效的算法设计：

• 使用语言功能来减少操作（变量缓存、链接等）。
• 尽可能减少迭代循环嵌套。
• 尽可能在循环外部定义变量。
• 使用自动循环索引（如果可用）而不是手动索引。
• 使用巧妙的缩减技术（例如递归分治和查询优化）来最大限度地减少递归过程的规模。

---

学习先进技术

要成为一名更好的算法设计师，没有比深入理解和欣赏算法更好的方法了。

• 每周花一两个小时阅读《计算机编程的艺术》。
• 尝试 Facebook 编程挑战赛或 Google Codejam。
• 学习使用不同的算法技术解决同一问题。
• 通过使用较低级别的操作实现语言的内置函数（例如 .sort()）来挑战自己。

---

结论

如果您在本文开始时还不知道什么是算法，那么希望您现在对这个有点难以捉摸的术语有了更具体的理解。作为专业开发人员，重要的是我们要了解我们编写的代码是可以分析和优化的，而且我们花时间对代码的性能进行分析也很重要。

你发现过什么有趣的算法练习题吗？也许是动态规划“背包问题”，或者“醉酒行走”？或者您可能知道 Ruby 中的一些递归最佳实践与 Python 中实现的相同函数不同。在评论中分享它们！

以上是深入了解算法设计的基础知识的详细内容。更多信息请关注PHP中文网其他相关文章！