# 為什么要學習數據結構和算法？ > 原文： [https://www.programiz.com/dsa/why-algorithms](https://www.programiz.com/dsa/why-algorithms) #### 在本文中，我們將學習為什么每個程序員都應借助示例來學習數據結構和算法。 本文適用于剛開始學習算法并想知道對提高其職業/編程技能有多大影響的人員。 對于那些想知道為什么 Google，Facebook 和 Amazon 這樣的大公司為何聘請非常擅長優化算法的程序員的人也是如此。 * * * ## 什么是算法？ 非正式地講，算法只不過是解決問題的步驟。 它們本質上是一個解決方案。 例如，解決階乘問題的算法可能如下所示： **問題**：找到`n`的階乘 ``` Initialize fact = 1 For every value v in range 1 to n: Multiply the fact by v fact contains the factorial of n ``` 在這里，算法是用英語編寫的。 如果以編程語言編寫，則將其稱為**代碼**。 這是用于在 C++ 中查找數字階乘的代碼。 ``` int factorial(int n) { int fact = 1; for (int v = 1; v <= n; v++) { fact = fact * v; } return fact; } ``` * * * 編程全部關于數據結構和算法。 數據結構用于保存數據，而算法用于解決使用該數據的問題。 數據結構和算法（DSA）詳細討論了標準問題的解決方案，使您深入了解了使用每個問題的效率。 它還教您評估算法效率的科學。 這使您能夠選擇各種最佳選擇。 * * * ## 使用數據結構和算法使代碼可擴展 **時間很寶貴。** 假設 Alice 和 Bob 正在嘗試解決一個簡單的問題，即找到前`10^11`個自然數之和。 當鮑勃（Bob）編寫算法時，愛麗絲（Alice）實現了該算法，證明它就像批評唐納德·特朗普（Donald Trump）一樣簡單。 **算法（由 Bob 提出）** ``` Initialize sum = 0 for every natural number n in range 1 to 1011 (inclusive): add n to sum sum is your answer ``` **代碼（由 Alice 提供）** ``` int findSum() { int sum = 0; for (int v = 1; v <= 100000000000; v++) { sum += v; } return sum; } ``` 愛麗絲（Alice）和鮑勃（Bob）感到欣喜若狂，他們幾乎可以在短時間內建立自己的東西。 讓我們潛入他們的工作區，聽聽他們的談話。 > 愛麗絲：讓我們運行這段代碼，找出總和。 鮑勃：我在幾分鐘前運行了這段代碼，但仍未顯示輸出。 它出什么問題了？ 哎呀！出事了！ 計算機是最確定的機器。 返回并嘗試再次運行它將無濟于事。 因此，讓我們分析一下此簡單代碼的問題所在。 計算機程序最有價值的兩個資源是**時間**和**存儲器**。 計算機運行代碼所需的時間為： ``` Time to run code = number of instructions * time to execute each instruction ``` 指令的數量取決于您使用的代碼，執行每個代碼所需的時間取決于您的計算機和編譯器。 在這種情況下，執行的指令總數（假設為`x`）為`x = 1 + (10^11 + 1) + (10^11) + 1`，即`x = 2 * 10^11 + 3` 讓我們假設一臺計算機可以在一秒鐘內執行`y = 10^8`指令（它可能會因機器配置而異）。 運行以上代碼所需的時間為 ``` Time taken to run code = x/y (greater than 16 minutes) ``` 是否可以優化算法，使 Alice 和 Bob 不必每次運行此代碼都等待 16 分鐘？ 我相信您已經猜到了正確的方法。 第一個`N`個自然數的總和由下式給出： ``` Sum = N * (N + 1) / 2 ``` 將其轉換為代碼將如下所示： ``` int sum(int N) { return N * (N + 1) / 2; } ``` 該代碼僅用一條指令執行，無論值是多少，都可以完成任務。 讓它大于宇宙中原子的總數。 它將很快找到結果。 在這種情況下，解決問題所需的時間為`1/y`（10 納秒）。 順便說一句，氫彈的融合反應需要 40-50 ns，這意味著即使有人在運行代碼的同時向計算機上扔了氫彈，程序也將成功完成。 :) **注意**：計算機采用一些指令（而非 1）來計算乘法和除法。 我只是為了簡單起見說 1。 * * * ### 有關可擴展性的更多信息 可擴展性是規模加能力，這意味著處理較大問題的算法/系統的質量。 考慮建立一個有 50 個學生的教室的問題。 最簡單的解決方案之一是預訂房間，拿起黑板，幾支粉筆，問題就解決了。 **但是，如果問題的規模增加了怎么辦？ 如果學生人數增加到 200，該怎么辦？** 該解決方案仍然有效，但需要更多資源。 在這種情況下，您可能需要更大的房間（可能是劇院），投影儀屏幕和數字筆。 **如果學生人數增加到 1000，該怎么辦？** 當問題的規模增大時，該解決方案將失敗或使用大量資源。 這意味著您的解決方案不可擴展。 **那么什么是可擴展的解決方案？** 考慮一個像 [Khanacademy](https://www.khanacademy.org/) 這樣的網站，數百萬學生可以同時觀看視頻，閱讀答案，并且不需要更多資源。 因此，該解決方案可以解決資源緊縮下規模較大的問題。 如果您看到我們找到第一個`N`個自然數之和的第一個解決方案，則該解決方案不可擴展。 這是因為它要求時間隨時間線性增長，而問題的大小則線性增長。 這種算法也稱為線性可擴展算法。 我們的第二個解決方案具有很高的可擴展性，不需要花費更多的時間來解決更大的問題。 這些被稱為恒定時間算法。 * * * ### 內存昂貴 內存并不總是足夠可用。 在處理需要您存儲或產生大量數據的代碼/系統時，對于算法而言，盡可能地節省內存使用至關重要。 例如：在存儲有關`Person`的數據時，您可以通過僅存儲其`age`而不是出生日期來節省內存。 您始終可以使用其年齡和當前日期即時對其進行計算。 * * * ## 算法效率的示例 以下是一些學習算法和數據結構使您可以執行的示例： ### 示例 1：年齡組問題 只需對[二分搜索算法](https://www.programiz.com/dsa/binary-search)進行少許修改，即可輕松解決諸如找到某個年齡段的人的問題（假設數據已排序）。 樸素的算法可以遍歷所有人，然后檢查它是否屬于給定的年齡組，因此可以線性擴展。 而二分搜索聲稱自己是對數可縮放的算法。 這意味著，如果問題的大小是平方的，那么解決問題的時間只會增加一倍。 假設要花 1000 秒才能找到某個年齡段的所有人口，則需要 1 秒。然后，對于 100 萬人口， * 二分搜索算法僅需 2 秒鐘即可解決問題 * 樸素的算法可能需要一百萬秒，大約需要 12 天 相同的二分搜索算法用于查找數字的平方根。 * * * ### 示例 2：魔方問題 想象一下，您正在編寫一個程序來找到魔方的解決方案。 這個看起來很可愛的難題令人討厭地有 43,252,003,274,489,856,000 個職位，而這些只是職位！ 想象一下，到達錯誤位置可以采取的路徑數量。 幸運的是，解決此問題的方法可以由[圖形數據結構](https://www.programiz.com/dsa/graph)表示。 有一種稱為 [Dijkstra](https://www.programiz.com/dsa/dijkstra-algorithm) 的圖算法可讓您在線性時間內解決此問題。 是的，您沒聽錯。 這意味著您可以在最少數量的狀態下到達求解位置。 * * * ### 示例 3：DNA 問題 DNA 是攜帶遺傳信息的分子。 它們由較小的單位組成，用羅馬字母 A，C，T 和 G 表示。 想象一下自己在生物信息學領域的工作。 分配工作是找出 DNA 鏈中特定模式的發生。 這是計算機科學界的一個著名問題。 而且，最簡單的算法所花費的時間與 ``` (number of character in DNA strand) * (number of characters in pattern) ``` 典型的 DNA 鏈具有數百萬個此類單元。 不用擔心 [**KMP 算法**](https://www.ics.uci.edu/~eppstein/161/960227.html)可以及時完成此操作，該時間與 ``` (number of character in DNA strand) + (number of characters in pattern) ``` 由`+`代替的`*`運算符進行了大量更改。 考慮到模式為 100 個字符，您的算法現在快了 100 倍。 如果您的模式包含 1000 個字符，那么 KMP 算法的速度將提高近 1000 倍。 也就是說，如果您能夠在 1 秒內找到模式的出現，那么現在只需要 1 毫秒。 我們也可以用另一種方式。 您可以同時匹配 1000 條相似長度的鏈，而不是匹配 1 條鏈。 而且有無數這樣的故事... * * * ## 最后的話 通常，軟件開發涉及每天學習新技術。 您可以在其中一個項目中使用它們時學習大多數這些技術。 但是，算法并非如此。 如果您不太了解算法，則將無法確定是否可以優化當前正在編寫的代碼。 您應該事先了解它們，并在可能和重要的情況下應用它們。 我們專門討論了算法的可擴展性。 一個軟件系統由許多這樣的算法組成。 優化其中任何一個都會帶來更好的系統。 但是，必須注意，這并不是使系統可擴展的唯一方法。 例如，一種稱為[分布式計算](https://en.wikipedia.org/wiki/Distributed_computing)的技術允許程序的獨立部分同時運行到多臺計算機，從而使其更具可擴展性。