贈書 | 看不懂《演算法導論》？先讀完豆瓣評分 9.4 的演算法入門巨著

  • 2021 年 8 月 8 日
  • AI

說到演算法巨著，你可能想到的是《演算法導論》這本經典。但在入門演算法時，還有一本與之比肩的巨著，不得不提，它就是《演算法（第4版）》。

這本豆瓣評分 9.4 的演算法巨著，可謂是演算法經典好書，給了無數人幫助。它是由普林斯頓的 Robert Sedgewick 和 Kevin Wayne 所寫，其中 Sedgewick 作為 Knuth 的學生，繼承了他們這一派的演算法分析思路。

《演算法（第4版）》全面介紹了關於演算法和數據結構的必備知識，並特別針對排序、搜索、圖處理和字元串處理進行了論述。在第 4 版中，還具體給出了每位程式設計師應知應會的 50 個演算法，不僅提供了實際程式碼，而且這些 Java 程式碼實現採用了模組化的編程風格，讀者可以方便地加以改造。
這本書初學者看完不會有挫敗感，不會給你一種「啃」書的感覺，而是跟著作者的思路一點點地帶入。因為其內容對初學者友好，《演算法（第4版）》也收穫了眾多粉絲。看看讀者都是怎麼評價的：

「這本書很適合剛剛入門或者離開校園已久需要複習一下演算法基礎的人。說起實用性，這本書比很多同類的書好太多了。省去了很多數學推導，非常適合需要準備面試，需要快速回顧一下基本的演算法及其實現的人。」

「最好的演算法入門書，當之無愧。內容全面實用，覆蓋常用的排序、查找、圖、字元串操作，講解生動，能用簡單精鍊的語句將複雜問題講清楚，可見作者的演算法和語言功力都很出色。」

「不愧是大師的作品，讀起來酣暢淋漓。這本書架構清晰明了，演算法思想通俗易懂，學完很難忘記。其中的思想給我帶來了一個新的世界，在這個世界我見識了很多新奇又好玩的事物。讀此書猶如小孩把玩自己的玩具，久久不能放下。」

這樣一本神作，影響了一代又一代的程式設計師。如果你想全面了解演算法，希望你能走近這本書。

整本書基於 Java，第一章就很簡潔地講解了 Java 的主要內容，沒學過 Java 的人，也可以輕鬆上手。而且本書程式碼實現非常詳細，內容比較簡單，一步步用圖告訴你程式碼是如何運行的，所有演算法都很基礎，不僅適合大學生閱讀，還適合初入職場需要提升的職場小白們，以及中高級工程師回顧補充演算法知識之用。
下面是這本書的目錄（滑動查看）：
目錄
這裡給大家一點小建議，第一章的 1.2 數據抽象和 1.4 演算法分析一定要仔細讀, 因為這兩節是全書的基礎。
第二章到第五章也要仔細看, 涉及到的演算法一定要跟著敲一遍。
第四章圖論是相對獨立的一章，只有在第五章正則表達式的 NFA 的構造中會用到有向圖中的知識, 裡面涉及到的演算法也比較容易理解。
書中部分小節後面有習題、答疑等，小夥伴們一定要跟著練習才能鞏固提高。下面選取 1.4 的答疑部分，給各位同學展示一下。
1
在近似函數的定義中，「隨著N 的增大」確切的意思是什麼？

滑動滾動條查看答案

f(N)~g(N) 的正式定義為limN→∞f(N)/g(N)=1。

2
我還見到過其他表示增長的數量級的符號，它們都表示什麼意思？

滑動滾動條查看答案

使用最廣泛的記法是「大O」：對於f(N) 和g(N)，如果存在常數c 和N0 使得對於所有N>N0 都有｜ f(N) ｜ < cg(N)，則我們稱f(N) 為O(g(N))。這種記法在描述演算法性能的漸進上限時十分有用，這在演算法理論領域是十分重要的，但它在預測演算法性能或是比較演算法時並沒有什麼作用。

3
當一個演算法的運行時間的增長數量級為NlogN 時，根據雙倍測試會得到它的運行時間為~ aN 的猜想（其中a 為常數）。這有問題嗎？

滑動滾動條查看答案

需要注意的是，我們不能根據實驗數據推測它們所符合的某個特定的數學模型。但如果我們只是在預測性能，這並不是什麼問題。例如，當N 在16 000 到32 000 之間時，14N 和NlgN 的影像非常接近。這些數據同時與兩條曲線吻合。隨著N 的增大，兩條曲線更為接近。想要用實驗來檢驗一個演算法的運行時間是線性對數級別而非線性級別是要費一番工夫的。

4
int[] a = new int[N] 表示N 次數組訪問嗎（所有數組元素均會被初始化為0）？

滑動滾動條查看答案

大多數情況下是的，我們在本書中也是這樣假設的，不過複雜編譯器的實現會在遇到大型稀疏數組時儘力避免這種開銷。
另外，配套網站 algs4.cs.princeton.edu 還提供了本書內容摘要以及相關程式碼、測試數據、編程練習、教學課件等資源，有需要的同學們可以自行查找。
圖書簡介
本書作為演算法領域經典的參考書，全面介紹了關於演算法和數據結構的必備知識，並特別針對排序、搜索、圖處理和字元串處理進行了論述。第 4 版具體給出了每位程式設計師應知應會的 50 個演算法，提供了實際程式碼，而且這些 Java 程式碼實現採用了模組化的編程風格，讀者可以方便地加以改造。本書配套網站提供了書中內容的摘要及更多的程式碼實現、測試數據、練習、教學課件等資源。本書適合用作大學教材或從業者的參考書。
本書特色

  • Sedgewick 之巨著，與高德納 TAOCP 一脈相承

  • 幾十年多次修訂，經久不衰的暢銷書

  • 涵蓋所有程式設計師必須掌握的 50 種演算法                   

作者介紹
Robert Sedgewick

斯坦福大學博士，導師為 Donald E. Knuth，從 1985 年開始一直擔任普林斯頓大學電腦科學系教授，曾任該系主任，也是 Adobe Systems 公司董事會成員，曾在 Xerox PARC、國防分析研究所（Institute for Defense Analyses）和法國國家資訊與自動化研究所（INRIA）從事研究工作。他的研究方向包括解析組合學、數據結構和演算法的分析與設計、程式可視化等。

Kevin Wayne

康奈爾大學博士，普林斯頓大學電腦科學系高級講師，研究方向包括演算法的設計、分析和實現，特別是圖和離散優化。

贈書福利 

AI科技評論以及AI研習社本次聯合【圖靈教育】為大家帶來3本《演算法（第四版）》正版新書。

AI研習社將一共選出 3名讀者，每人送出《演算法（第四版）》一本。

在本文（僅限AI研習社社區網站端）留言區留言，歡迎大家暢所欲言，談一談你對本書的看法和期待。在綜合留言品質（留言是敷衍還是走心）和留言點贊最高（註：點贊最高的前3不意味著一定會中獎）的讀者中選出3位讀者獲得贈書。獲得贈書的讀者請聯繫 AI 研習社客服（AIyanxishe3）。

  • 留言內容會有篩選，例如「選我上去」、「這書寫的很棒（僅僅幾個字）」等內容將不會被篩選，亦不會中獎。

  • 留言送書活動時間為2021年8月8日 – 2021年8月12日（23:00），活動推送時間內僅允許贈書福利中獎一次。


另外，讀者也可以到AI科技評論微信公眾號月8號同名文章留言區留言，AI科技評論將會在留言區選出 10名讀者，每人送出《演算法（第四版）》一本。

掃描下方二維碼，關注AI科技評論微信公眾號（ID：aitechtalk）：

1.png

    VirMach 便宜 VPS

    QNews

    QNews