問題：在MxN網格中找到一些從左上角到右下角的可能方式，而你只能向下或向右移動。
下面是我寫的兩個演算法。結果看起來還不錯，但我無法計算出時間和空間的復雜度，我對復雜度有一些猜測，但我無法以 "適當 "的方式證明它們。
天真的演算法：
function gridTravel（m, n） {
if(m<1 || n<1) return 0;
if (m ==1 || n ==1) return 1;
return gridTravel(m-1, n) gridTravel(m, n-1) 。
};
console.log(gridTravel(10,10) ）。)
我的猜測：
- 空間復雜性 - O(n m)? 最長的呼叫堆疊似乎是 "線性 "擴展的，所以假設某種近似值，它將是O(n m)，但我無法真正證明或反駁它。
- 時間復雜性是指數級的，因為每個位置可以創建2個新的位置--O(2^n)或O(2^n m)，不確定哪個更合適。
m: n
m-1:n m:n-1: n
m-2:n m-1:n-1 m-1: n-1 m:n-2.
但是，我再次對這個解釋感到不自信，因為它不是模擬樹，它只是在開始時看起來像。
Naive algo memoization：
seenGrids = {};
const gridTravel = (m, n) => {
if(m<1 || n<1) return 0;
if (m ==1 || n ==1) return 1;
if (`${m}: ${n}` in seenGrids || `${n}: ${m}` in seenGrids) {
return seenGrids[`${m}:${n}`] || seenGrids[`${n}:${m}`] 。
}
seenGrids[`${m}: ${n}`] = gridTravel（m-1, n） gridTravel（m, n-1）。
return seenGrids[`${m}:${n}`] 。
};
我的猜測：
- 空間 - O(n*m)? 呼叫堆疊似乎仍然是線性的，但現在我們有這個不斷增長的物件
seenGrids，根據我的直覺，它應該以一種二次方的方式擴展？我不知道如何證明或反駁它，當我運行console.log(Object.keys(seedGrids).length)為200x200網格時，我得到19900，這不是m*n或m n，所以它是線性或二次的？ - 時間 - O(n*m)? - 這對我來說是最難理解的。它不應該是指數級的，因為由于保存了答案，很多子樹被跳過了，但我不知道如何以 "適當 "的方式推匯出時間復雜性。
uj5u.com熱心網友回復：
第一個演算法：
對于時間復雜度，最簡單的證明就是你的方法! 我是指遞回函式的計算樹。正如你所看到的，有一棵二進制樹用于展開，而樹的最大長度是min(n,m)。因此，時間復雜度為O(2^(min(m,n)))。
對于空間復雜度，正如你所指出的，堆疊的計算將以深度優先的方式進行。因此，由于每個節點的最大分支是2，并且樹的最大長度是min(m,n)（如前一段所討論的），空間復雜度將是2 min(m,n)。
第二種演算法：
由于輸入的最大不同組合是m * n（[1, 2, ..., m]和[1, 2, ..., n]分別為函式的第一個和第二個輸入），而堆疊呼叫的最壞情況是在O(min(m, n))，空間復雜性是在O(m * n)，這就是記憶體陣列的大小。
對于時間復雜度，我們可以確保陣列的每個元素將被計算一次（因為它被記憶了）。因此，與遞回回呼的復雜性無關，并且由于遞回的深度優先計算（自下而上），第二種演算法的時間復雜性在O(m * n)。
轉載請註明出處，本文鏈接：https://www.uj5u.com/ruanti/326072.html
標籤：
上一篇：svg的背景顏色