我正在撰寫一個函式，它接受一個陣列和一個整數并回傳一個子陣列陣列。子陣列的數量正是傳遞給函式的整數。并且子陣列必須是連續的，這意味著必須保留陣列中專案的原始順序。也沒有子陣列可以為空。他們必須至少有一個專案。例如：

const array = [2,3,5,4]
const numOfSubarray = 3

const subarrays = getSubarrays(arraym numOfSubarray)

在這種情況下subarrays是這樣的：

[
  [[2, 3], [5], [4]],
  [[2], [3, 5], [4]],
  [[2], [3], [5, 4]],
]

這是我的嘗試：

function getSubarrays(array, numOfSubarray) {
  const results = []

  const recurse = (index, subArrays) => {
    if (index === array.length && subArrays.length === numOfSubarray) {
      results.push([...subArrays])
      return
    }
    if (index === array.length) return

    // 1. push current item to the current subarray
    // when the remaining items are more than the remaining sub arrays needed

    if (array.length - index - 1 >= numOfSubarray - subArrays.length) {
      recurse(
        index   1,
        subArrays.slice(0, -1).concat([subArrays.at(-1).concat(array[index])])
      )
    }
    // 2. start a new subarray when the current subarray is not empty

    if (subArrays.at(-1).length !== 0)
      recurse(index   1, subArrays.concat([[array[index]]]))
  }

  recurse(0, [[]], 0)
  return results
}

現在它似乎正在作業。但我想知道這個演算法的時間/空間復雜度是多少。我認為它肯定比O(2^n). 有什么辦法可以改善嗎？或者我們可以用來改進演算法的任何其他解決方案？

uj5u.com熱心網友回復：

tl;博士

解決方案的數量與（如@gimix 提到的）二項式系數有關，所以如果我理解正確，它是悲觀的指數 https://en.wikipedia.org/wiki/Binomial_coefficient#Bounds_and_asymptotic_formulas。

如果我沒記錯的話，這會使您的演算法成為指數 * n （對于每個解決方案的每個元素）* n （因為幾乎在每個步驟中，您都復制了長度可能取決于的陣列n）。

• 修復第二個 if - 僅在 subArrays.length < numOfSubarrays 時呼叫遞回
• 您正在大量復制陣列 - 切片、連接、擴展運算子 - 所有這些都會創建新陣列。如果對于每個解決方案（其長度可能取決于n）在每個步驟中復制此解決方案（我認為在這里發生），您將復雜性乘以n.
• 空間復雜度也是指數 * n- 你存盤指數數量的解決方案，可能長度取決于n。使用生成器并在當時回傳一個解決方案可以大大改善這一點。正如@gimix 提到的那樣，組合可能是最簡單的方法。python中的組合生成器：https ://docs.python.org/3/library/itertools.html#itertools.combinations

考慮復雜性：

我認為你對慢于指數復雜性的看法是正確的，但是 - 對我來說 - 你對斐波那契數列了解多少？;)

讓我們考慮輸入：

array = [1, 2, ..., n]
numOfSubarrays = 1

我們可以將遞回呼叫視為一棵二叉樹，其中if1. 保護左孩子（第一次recurse呼叫）和if2. 保護右孩子（第二次recurse呼叫）。

對于每個遞回呼叫if1. 將被滿足 - 專案比需要的子陣列多。

僅當當前子陣列具有某些元素時，第二個if才會成立。這是一個棘手的條件 - 當且僅當它成功高一幀時它才會失敗 - 一開始就添加了一個空陣列（根呼叫除外 - 它沒有父級）。就樹而言，這意味著我們在正確的孩子中 - 父母必須剛剛添加了一個空子陣列作為當前。另一方面，對于左孩子，父母剛剛將（又一個？）元素推送到當前子陣列，我們確信 if 2. 會成功。

好的，但它說明了復雜性是什么？

好吧，我們可以計算樹中節點的數量，乘以它們執行的操作的數量——其中大多數是一個常數——我們就得到了復雜度。那么有多少呢？

我將在每個級別上分別跟蹤左右節點。很快就會有用的。為方便起見，我將忽略根呼叫（我可以將其視為右節點 - 它具有空子陣列 - 但它會破壞最終效果）并從級別 1 開始 - 根呼叫的左子節點。

r ₁ = 0
l ₁ = 1

作為左節點（子陣列不為空），它有兩個子節點：

r ₂ = 1
l ₂ = 1

現在，左節點總是有兩個子節點（1. 總是滿足；2. 為真，因為父節點將元素推送到當前子陣列），右節點只有左子節點：

r ₃ = r ₂ l ₂ = 1 1 = 2
l ₃ = r ₂ = 1

我們可以繼續。結果是：

嗯……奇怪的熟悉，不是嗎？

好吧，很明顯，復雜度是 O(Σ(F _i F _i-1 )，其中 1 <= i <= n)。

好吧，但它的真正含義是什么？有一個非常酷的證明S(n) - 從 0 到 n 的斐波那契數之和等于 F(n 2) - 1。它將復雜性簡化為：

O(S(n)   S(n-1)) = O(F(n 2) - 1   F(n 1) - 1) = O(F(n 3) - 2) = O(F(n 3))

我們可以忘記 3，因為 F(n 3) < 2 * F(n 2) < 4 * F(n 1) < 8 * F(n)。

最后一個問題，斐波那契數列是指數的嗎？是的，顯然不是。不是可以滿足 x ⁿ = F(n) 的數字 - 該值在 2 和 √2 之間波動，因為對于 F(n 1) < 2 * F(n) < F(n 2)。

但事實證明，lim(n->∞) F(n 1) / F(n) = φ - 黃金比例。這意味著 O(F(n)) = O(φ ⁿ )。（實際上，你復制陣列很多，所以它更像是 O(φ ⁿ *n)）

如何解決？您可以在遞回 if 2 之前檢查是否沒有太多陣列。

除此之外，正如@Markus 提到的，根據輸入，解決方案的數量可能是指數的，因此獲得它們的演算法也必須是指數的。但這并不是每個輸入都是如此，所以讓我們將這些情況保持在最低限度：D

uj5u.com熱心網友回復：

如果要將n元素串列完全拆分為k分離的連續子串列，這就像將k-1拆分點放置n-1在元素之間的間隙中：

2 | 3 | 5   4
2 | 3   5 | 4
2   3 | 5 | 4

在組合學中，這是k-1取自n-1. 所以我認為輸出的結果大小將是n-1 take k-1 = (n-1)! / ((k-1)! * (n-k)!). 因此，復雜性是多項式，例如O(n^(k-1))constant k。如果您不修復k而是提高它，復雜性將呈指數級增長n。k = n/2

我不認為你可以改進這一點，因為輸出的大小正在增加這種復雜性。

uj5u.com熱心網友回復：

該問題可以通過不同的方法解決：

• 計算numOfSubarray從 1 到長度的所有數字組合array
• 每個組合都是 的有效切片array。例如，您希望在示例中的位置 (1, 2)、(1, 3)、(2, 3) 處對陣列進行切片，從而產生子陣列[[2],[3],[5,4]]、[[2],[3,5],[4]]和[[2,3],[5],[4]]

我相信時間復雜度是 O(r(nCr))，其中 n 是（陣列的長度 - 1），r 是（子陣列的數量 - 1）。

要可視化它的作業方式和原因，請查看星條技術

標籤：javascript 数组 算法 递归 大哥

上一篇：遞回Java方法未完全執行

下一篇：網格搜索問題的最大遞回深度誤差