隨機與遞歸算法
隨機算法通過在算法執行過程中進行隨機選擇,在其邏輯中包含了隨機性。由於這種隨機性,即使對於固定輸入,算法的行為也會發生變化。對於許多問題,隨機算法提供了最簡單有效的解決方案。遞歸算法基於這樣一種思想,即問題的解可以通過找到同一問題的較小子問題的解來找到。遞歸在計算機科學中被廣泛用於尋找問題的解決方案,許多高級編程語言都支持遞歸。
什麼是隨機算法?
隨機算法通過隨機選擇來指導算法的執行,從而融入了隨機性的感覺。這通常是通過將偽隨機數生成器生成的一組隨機數作為附加輸入來完成的。因此,即使是固定輸入,算法的行為也可能會發生變化。Quicksort是一種廣泛採用隨機性概念的算法,它具有O(n LOGN)的運行時間,而不考慮輸入屬性。在計算幾何中,將隨機增量構造方法應用於凸包等結構的施工。該方法將輸入點隨機排列,然後逐個**結構中。實現隨機算法相對簡單,而不是對同一問題實現確定性算法。設計隨機算法的最大挑戰在於對時間和空間複雜度進行漸近分析。
什麼是遞歸算法?
遞歸算法基於這樣一種思想,即問題的解可以通過找到同一問題的較小子問題的解來找到。在遞歸算法中,函數是根據其早期版本定義的。需要注意的是,這種自引用應該有一個終止條件,以避免永遠引用它自己。終止條件在引用自身之前被檢查。遞歸算法的初始步驟與問題遞歸定義的基子句有關。第一步之後的步驟與問題的歸納從句有關。遞歸算法在許多情況下提供了一個更簡單的解決方案,它比迭代算法更接近於自然思維方式。但一般來說,遞歸算法需要更多的內存,而且計算成本很高。
隨機算法和遞歸算法有什麼區別?