資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝設計
法學貪婪演算法與動態規劃的區別
在這篇文章中，我們將瞭解貪婪演算法和動態規劃方法的區別。
貪婪演算法
這是一種演算法正規化，它逐步構建解決方案。選擇下一步時，要選擇能帶來最明顯和直接好處的方案。
- 涉及選擇區域性最優值的問題將有助於選擇問題的全域性最優值/解決方案。這些是與貪婪演算法相關的問題。
- 不能保證貪婪演算法一定會找到最優解。
- 在問題的每個階段都會做出最優選擇，即區域性最優解。
- 它在記憶體使用方面效率很高，因為無需回溯或更改之前的解決方案/值。
- 總的來說，與動態規劃技術相比，它速度更快。
- 示例：Dijkstra最短路徑演算法，時間複雜度為O(ELogV + VLogV)。
- 貪婪演算法中的解是用前向方法計算的，從不訪問或更改之前的數值/解。
動態規劃
這是一種最佳化技術，用於儲存子問題的解，以便將來需要時無需重新計算。它們可以直接從預先計算的集合中提取。它將時間複雜度從指數複雜度降低到多項式複雜度。
- 例如：可以透過計算將遞迴解轉換為動態規劃問題。
- 在此方法中，每一步的決策都是透過考慮當前問題和先前已解決的子問題的解來做出的。這將用於計算最優值/解。
- 動態規劃問題的解一定是最優解。
- 這裡選擇的最佳解是全域性最優解。它使用某些公式來儲存先前計算的狀態值。
- 需要動態規劃表進行記憶化。這增加了記憶體複雜度。
- 它相對較慢。
- 示例：Bellman-Ford演算法，時間複雜度為O(VE)。
- 動態規劃透過從小問題（已找到最優解）開始逐步構建，從而確定解決方案。
更新於：2021年3月2日
529 次瀏覽
廣告