深入了解演算法設計的基礎知識

本文將深入探討演算法設計的原理。如果您不知道我指的是什麼，請繼續閱讀！

#當您聽到「演算法」這個詞時，您可能會透過以下三種方式之一做出回應：

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中文網其他相關文章！