建站
咨詢
售后
建站咨詢
新聞中心
算法是數(shù)據(jù)科學不可分割的一部分。雖然很多數(shù)據(jù)科學家在學習的時候沒有選修合適的算法課程，但它確實很重要。
北海街道網(wǎng)站制作公司哪家好，找創(chuàng)新互聯(lián)公司！從網(wǎng)頁設計、網(wǎng)站建設、微信開發(fā)、APP開發(fā)、成都響應式網(wǎng)站建設等網(wǎng)站項目制作，到程序開發(fā)，運營維護。創(chuàng)新互聯(lián)公司自2013年起到現(xiàn)在10年的時間，我們擁有了豐富的建站經驗和運維經驗，來保證我們的工作的順利進行。專注于網(wǎng)站建設就選創(chuàng)新互聯(lián)公司。
比如說，許多公司在面試數(shù)據(jù)科學家時，都會問到數(shù)據(jù)結構和算法。
那么，現(xiàn)在問題是，問數(shù)據(jù)科學家這樣的問題到底有什么用。
對于這個問題，我的答案是，數(shù)據(jù)結構問題可以被當作是對編碼能力的測試。
我們都在人生的不同階段接受過能力測試，但是這些測試并不能完美地評判一個人，幾乎沒有什么測試能做到這一點。
那么，為什么不用一個標準算法測試來評判一個人的編碼能力呢?
因為算法和測試都并非死板，你總能在前者總結的基礎上不斷改進、創(chuàng)新，總能運用不同的算法來回應這些測試。
但這也并不意味著你可以不掌握基礎就可以肆意動搖算法的地基。
牢固掌握基礎算法的概念和運用，永遠是一個優(yōu)秀數(shù)據(jù)科學家必備的素質。
本文將以一種容易理解的方式幫助數(shù)據(jù)科學家快速回顧相關研究并介紹一些基本算法概念。
1. 遞歸/記憶化
遞歸是將定義的函數(shù)應用到自己的定義中。簡而言之，遞歸是函數(shù)的自身調用。當你用谷歌搜索遞歸時，會遇到點小插曲。
剛開始學習數(shù)據(jù)科學的人可能會覺得遞歸有點難，但其實它很容易理解。一旦理解了，就會發(fā)現(xiàn)這是一個很棒的概念。
解釋遞歸的最好例子就是計算一個數(shù)的階乘。
- def factorial(n):
- if n==0:
- return 1
- return n*factorial(n-1)
可以很容易地看出階乘是一個遞歸函數(shù)。
- Factorial(n) = n*Factorial(n-1)
那么如何將它轉化為編程呢?
遞歸調用的函數(shù)通常由兩部分組成：
- 基線條件——終止遞歸的條件。
- 遞歸公式——向基線條件發(fā)展的公式。
許多問題解決到最后，就是遞歸問題。這也適用于數(shù)據(jù)科學。
例如，一棵決策樹是二叉樹，樹算法通常是遞歸的?；蛘撸晕覀兘洺Ｊ褂玫呐判驗槔?。排序的算法稱為歸并排序(mergesort)，它本身就是一種遞歸算法。另一種是對分查找 (binary search)，包括在數(shù)組中查找元素。
現(xiàn)在我們了解了遞歸的基本知識，接下來試著找到第n個斐波那契數(shù)。斐波那契數(shù)列是一系列數(shù)字，其中每個數(shù)字(斐波那契數(shù))都是前面兩個數(shù)字之和。最簡單的數(shù)列是1、1、2、3、5、8等。要找到第n個斐波那契數(shù)，可以用如下代碼:
- def fib(n):
- if n<=1:
- return 1
- return fib(n-1) + fib(n-2)
但是，發(fā)現(xiàn)問題了嗎?
如果試圖計算fib(n=7)要運行兩次fib(5) ，運行三次 fib(4) ，運行5次 fib(3)。隨著n越來越大，對同一數(shù)字進行了多次調用，遞歸函數(shù)對其進行了一次又一次的計算。
稍微改變我們的執(zhí)行，添加一個詞典來為這個方法添加一些存儲?，F(xiàn)在，每次計算出一個數(shù)字，這個備忘錄詞典就會更新。如果再出現(xiàn)同樣的數(shù)字，就不需要再對它進行計算，而是可以直接從備忘錄字典中得出結果。這種增加存儲的方式被稱為記憶化。
- memo = {}def fib_memo(n): if n in memo: return memo[n] if n<=1: memo[n]=1 return 1 memo[n] = fib_memo(n-1) +fib_memo(n-2) return memo[n]
通常，我會先寫遞歸代碼，如果它重復調用相同的參數(shù)，我會再添加一個詞典來進行記憶化。
這幫助大嗎?
圖中是不同n值的運行時間的比較。可以看到：沒有記憶化的斐波那契函數(shù)運行時間呈指數(shù)性增長，而記憶化函數(shù)的運行時間則是線性的。
2. 動態(tài)規(guī)劃
遞歸本質就是一種自上而下的方法。比如在計算斐波那契數(shù)n時，就是從n開始，然后對n-2和n-1進行遞歸調用，依此類推。
在動態(tài)規(guī)劃中，我們采取自下而上的方法。這本質上是一種迭代編寫遞歸的方法。首先計算fib(0)和fib(1)，然后使用前面的結果生成新的結果。
- def fib_dp(n):
- dp_sols = {0:1,1:1}
- for i in range(2,n+1):
- dp_sols[i] = dp_sols[i-1] +dp_sols[i-2]
- return dp_sols[n]
上圖是“動態(tài)規(guī)劃”和“記憶化”運行時間的比較?？梢钥闯鏊鼈兌际蔷€性的，但動態(tài)規(guī)劃更快一點。
為什么呢?因為在這種情況下，動態(tài)規(guī)劃只對每個子問題進行一次調用。
關于開發(fā)動態(tài)規(guī)劃的貝爾曼是如何選定“動態(tài)規(guī)劃”這個名字的，有一個很有趣的故事：
“動態(tài)規(guī)劃”這個名字是從哪里來的呢?20世紀50年代的數(shù)學研究情況并不是很好。當時，華盛頓有一位非常有趣的紳士，名叫威爾遜，他是國防部長。實際上，他對研究這個詞懷有病態(tài)的恐懼和仇恨。那我能起個什么名字呢?首先，我考慮了“計劃”、“決策”、“思考”。但是出于各種原因，“計劃”并不是一個好詞。于是，我決定使用“規(guī)劃”一詞。我想傳遞的概念是，這是動態(tài)的，多級的，并且是時變的。因此，我認為動態(tài)規(guī)劃是個好名字，這可以一舉兩得。這是連國會議員都不會反對的。所以我決定采用這個名字。
3. 二進制搜索
假設有一個排序了的數(shù)字組合，要從這個數(shù)組中找出一個數(shù)字。我們可以采用線性搜索，挨個地檢查每一個數(shù)字，直到找到特定數(shù)字。問題是，如果數(shù)組包含數(shù)百萬個元素，這種方法就需要花費很長時間。這種情況下，可以采用二進制搜索方法。
來源：發(fā)現(xiàn)37-海洋中有3.7萬億條魚，他們正在尋找其中的1條
- # Returns index of target innums array if present, else -1
- def binary_search(nums, left, right, target):
- # Base case
- if right >= left:
- mid = int((left + right)/2)
- # If target is present at themid, return
- if nums[mid] == target:
- return mid
- # Target is smaller than midsearch the elements in left
- elif nums[mid] > target:
- return binary_search(nums,left, mid-1, target)
- # Target is larger than mid,search the elements in right
- else:
- return binary_search(nums,mid+1, right, target)
- else:
- # Target is not in nums
- return -1nums =[1,2,3,4,5,6,7,8,9]
- print(binary_search(nums, 0, len(nums)-1,7))
這是一個基于遞歸算法的高級例子。利用數(shù)組被排序的事實，遞歸地查看中間元素，看看是想在中間元素的左邊還是右邊搜索。這使得每一步的搜索空間減少2倍。
因此，二進制搜索算法的運行時間是O(logn)，而不是線性搜索的O(n)。
這有什么作用呢?下面是運行時間的比較。我們可以看到二進制搜索與線性搜索相比是相當快。
當n=10000時, 二進制搜索需要大約13步，線性搜索需要10000步。
結論
本文談到了一些構成編程基礎的算法，雖然是基礎，但也同樣令人興奮。
數(shù)據(jù)科學家在面試時會經常被問到這些算法，深入理解它們可能會幫助你找到理想的工作哦。
盡管你不學習這些算法也可以在數(shù)據(jù)科學中取得進步，但你可以把學習它們當作一種樂趣，培養(yǎng)興趣的同時還可以順便提高編程技能。
一舉兩得，何樂而不為呢?
文章題目：不能忘記！數(shù)據(jù)科學家面試時應該掌握的3個編程概念
文章位置：http://www.5511xx.com/article/ccscego.html
