常見的數(shù)據(jù)結構與算法

最基本的數(shù)據(jù)結構和算法包括：

• 排序算法
• 遞歸
• 鏈表
• 數(shù)組
• 隊列
• 棧
• 優(yōu)先隊列
• 哈希(散列)
• 二叉樹，B樹，B+樹，紅黑樹
• bitmap
• 跳表
• 二分法
• 動態(tài)規(guī)劃
• 貪心算法
• ……

工作無需數(shù)據(jù)結構與算法?

您是否知道您的所有SQL和Linux命令都是算法和數(shù)據(jù)結構?您可能沒有意識到這一點，但這就是軟件的工作方式。

數(shù)據(jù)結構和算法在實現(xiàn)軟件和雇用過程中也起著重要作用。許多學生和專業(yè)人士都提出了這樣一個問題：為什么這些公司的訪談只關注DSA，而不是針對語言/框架/工具的特定問題?

當您要求某人做出某項決定時，好的人會告訴您“我選擇做X，因為在這些方面，它比A，B更好。我本可以選擇C的，但是由于這個原因，我認為這是一個更好的選擇。在我們的日常生活中，我們總是和那個可以在短時間內高效完成任務并使用更少資源的人一起工作。這些公司也發(fā)生同樣的事情。這些公司面臨的問題更加艱巨，解決這些公司的問題時，軟件開發(fā)人員必須做出正確的決定。

對數(shù)據(jù)結構(例如哈希表，樹，圖表，圖形和各種算法)的了解對于有效解決這些問題大有幫助，面試官對查看候選人如何使用這些工具解決問題的興趣更大。就像汽車修理工需要正確的工具來修理汽車并使其正常運行一樣，程序員也需要正確的工具(算法和數(shù)據(jù)結構)來使軟件正確運行。因此，面試官想找到一個候選人，可以應用正確的工具來解決給定的問題。

在像Google，Microsoft，F(xiàn)acebook，Amazon這樣的公司工作的工程師與其他公司不同，在這些公司中，編碼只是實現(xiàn)，大約需要20-30%的時間分配給項目。大多數(shù)時間都在使用最佳算法來設計事物，以節(jié)省公司的資源(服務器，計算能力等)。這就是為什么這些公司中的采訪集在算法上的主要原因，因為他們希望開箱即用的人設計可以為公司節(jié)省數(shù)千美元的算法。

示例：假設您在Facebook公司工作。您提出了時間復雜度為O(nLogn)而不是O(n ^ 2)的問題的最佳解決方案，并假定公司的問題的n實際為生活場景為1億(考慮到在Facebook上注冊的用戶數(shù)超過10億)。nLogn為8億，而n ^ 2為10 ^ 70億。在成本方面，您可以看到效率提高了10 ^ 7倍以上，這在服務器成本和時間方面可以節(jié)省很多。

從用人者角度

毋庸置疑，面試是用來篩選候選人的，在這個僧多粥少的時候，就需要提高篩選條件，例如最常見的學歷，不是說學歷一般的人不好，而是總體來說，學歷好的人里面挑選到合適的概率比較大而已，這就是現(xiàn)實。而面試題中，算法相比于其他記憶型的題目，就能很好的體現(xiàn)一個人的邏輯和思路，因而也是一個很好的篩選條件。當然像操作系統(tǒng)，網(wǎng)絡，Linux等都是很多公司喜歡考察的點。

所以為了面試還是需要準備學習算法的。

從個人角度

進去的第一家公司基本用不上什么算法(血的教訓，在學校的時候一定要好好準備)，甚至用不上網(wǎng)絡編程，基本就是簡單純C開發(fā)，因為那些東西早就封裝好了(由另外一個組負責開發(fā)維護)，只需要調用即可。包括后來去面試，主要面試了兩類公司，一類是傳統(tǒng)通信技術類，一類是互聯(lián)網(wǎng)公司，前者關注項目本身，以及基本的技術技能更多一些，而后者考察的方面通常比較多，包括操作系統(tǒng)，數(shù)據(jù)庫，算法，網(wǎng)絡等知識。

那么面完之后是不是真的就完全沒用了呢?確實，大多數(shù)時候根本用不上。你寫的可能多是業(yè)務代碼，是業(yè)務流程的設計，代碼實現(xiàn)可能只是很小的一環(huán)。而且現(xiàn)有算法實現(xiàn)一搜一大把，基本不太可能要你自己去實現(xiàn)什么快排，跳表，快排，紅黑樹之類的算法，但是學習算法有好處。

例如，你可能要根據(jù)你的業(yè)務排序需求來選擇是用穩(wěn)定排序還是非穩(wěn)定排序;你可能會根據(jù)插入和刪除數(shù)據(jù)的頻率來選擇使用array list還是link list;你可能為了處理top K問題采用堆相關算法;可能為了某種情況下的快速查找而使用哈希;你可能在設計你的業(yè)務數(shù)據(jù)結構時引用了基本數(shù)據(jù)結構的思想。

算法解決一些現(xiàn)實世界中的復雜問題

當您在混亂的房間里找不到書或衣服時，有沒有被父母罵過?肯定有過吧，您的父母的建議是對的，以確保一切都在正確的位置，以便下次您可以輕松獲得所需的東西。在這里，您需要以一種結構來安排和保留所有內容(數(shù)據(jù))，以便每當您需要搜索某些內容時，都可以輕松而迅速地獲得它。這個例子清楚地表明，在現(xiàn)實生活中安排或構造數(shù)據(jù)有多么重要。

現(xiàn)在以圖書館為例。如果您需要從圖書館中找到一本關于集合論的書，那么您將首先進入數(shù)學部分，然后進入集合論部分。如果這些書不是以這種方式組織的，而是隨機分配的，那么尋找特定的書將很令人沮喪。因此，數(shù)據(jù)結構是指我們在計算機上組織信息的方式。計算機科學家進行處理并尋找可以組織數(shù)據(jù)的最佳方式，因此可以根據(jù)所提供的輸入更好地對其進行處理。

許多新手程序員都提出了這樣一個問題：我們在日常生活中將數(shù)據(jù)結構和算法的所有內容都用在哪里，以及它在解決現(xiàn)實世界中的復雜問題上如何有用。我們需要提及的是，無論您是否有興趣進入頂尖的科技巨頭公司，DSA仍然對您的日常生活有很大幫助。

總結

通常我們不需要自己實現(xiàn)這些算法，不過我覺得從中了解以下幾點非常重要

• 時間和空間復雜度的概念
• 各類數(shù)據(jù)結構或算法的效率
• 各類數(shù)據(jù)結構或算法的復雜度
• 各類數(shù)據(jù)結構或者算法的適用場景
• 常見的如vector，map，set等容器背后的數(shù)據(jù)結構是什么，它們的查找或者插入效率如何
• 從現(xiàn)有數(shù)據(jù)結構和算法中獲得思路
• 根據(jù)現(xiàn)有問題選擇合適的數(shù)據(jù)結構和算法

不像Java，C++，Python之流，C庫中可能沒有上面提到的數(shù)據(jù)結構或者算法的實現(xiàn)，因而C語言也是加深對它們理解的不二選擇。

一切為了更好地解決實際問題。