數學基礎對學習資料結構的影響

2020-07-16 10:05:28
很多初學者自認數學基礎不好,懷疑這將是學習資料結構不可逾越的大山,對學習資料結構沒有足夠的信心。總的來說,數學基礎不是學習資料結構的必備條件,但好的資料基礎對學習資料結構大有助益。

這個問題,其實和“英語不好,可以學習程式設計嗎?”同屬一類。不可否認,英語基礎好對於學習程式設計確實是很有幫助的,但它並不是學習程式設計不可跨越的鴻溝。事實上,只有從優秀程式設計師躍升為頂尖程式設計師時,英文基礎(需要閱讀一些英文資料)的桎梏才會凸顯出來,但也並非無法克服。數學和資料結構之間的關係也是如此。

注意,英語基礎薄弱並不等價於英語 0 基礎,如果是這樣,那在學習程式設計的過程中,確實需要適當地惡補一些英語;學習資料結構也是如此,如果數學基礎很差(例如僅有小學功底),就需要在學習資料結構的過程中,有意識地惡補一下數學。這裡所謂的惡補,不建議讀者無目的地單純學數學知識,而是在學習資料結構的過程中,遇到搞不懂的數學運算,再去刻意地翻閱相關資料。

舉個簡單的例子,前面已經詳細的講解了如何用“大 O 記法”來評判一個演算法的時間複雜度,那麼下面 C 語言程式碼的時間複雜度是多少呢?
i = 1;
while( i < n ){
    i = i * 2;
}
對於此段程式碼來說,我們只需要求出 while 迴圈中程式碼(也就是第 3 行程式碼)執行的次數,即可輕鬆得到這段程式碼的時間複雜度。可以看到,迴圈條件為 i<n,而變數 i 的值每經歷一次迴圈都會翻倍,因此假設有一個臨界值 m,能恰好使 2m = n,此時迴圈將會終止,程式執行結束。

因此,求這段程式碼的時間複雜度,只需要求出 m 的值即可。這就需要我們具備對數運算的能力,由 2m = n 得 m = log2n,簡化 m 的值並最終得出此段程式的時間複雜度為 O(logn)。此時,如果讀者無法理解 m 值的由來,就需要惡補一下關於數學中對數運算的相關知識。

當然,對於絕大多數的數學運算,也可以借助計算器或者網路工具來計算得出。事實上,很多和編寫程式碼無關的工作,我們完全不必親力親為,要善於運用網路來解決遇到的難題。


其次,一些讀者學習資料結構的初衷,僅僅是想將資料結構應用到自己的專案中。這種情況下,資料基礎則更顯得無關緊要,因為在實際開發中,很多程式語言都提供有整合資料結構中各種儲存結構的庫或者模組,例如 C++ 中可以使用 STL 標準庫,Python 中可以使用 collections 模組等等。這意味著,如果我們所用的程式語言提供有已封裝好的資料結構,則只需簡單了解資料結構中各個儲存結構的特性,然後呼叫相關的庫或者模組,即可實現最初的目的。

通過前面的學習我們知道,資料結構和演算法完全是 2 個獨立的學科,只是它們相輔相成(可閱讀《資料結構和演算法的關係和區別》一節)。讀者可能會問,學習資料結構肯定是要學習相關演算法的,學習演算法不需要有一定的數學基礎嗎?我認為,學習演算法更多的是要求我們具備一定的問題分析能力和空間想象力(可以用畫圖彌補),很少有演算法需要較高的數學功底。

總的來說,無論是學習資料結構還是學習演算法,只要讀者具備一定的程式設計能力,都可以學會。而至於數學基礎的好壞,有更好,沒有也無需沮喪,依然可以學習資料結構和演算法。