配列の積和演算のアルゴリズム

「特別な配列」が与えられるので積和演算を行って値を返す。「特別な配列」は数値あるいは「特別な配列」をもつ。「特別な配列」内の数値をすべて加算するが、ネストレベルに応じてその和を乗算する。例えば、

[x, y] → x + y
[x, [y, z]] → x + 2(y + z)
[1, [2, [3, 4]]] → 1 + 2 * (2 + 3 * (3 + 4)) → 47

アルゴリズム実装(1) $O(n)$

再帰関数を別途作るのが楽。見たまんまで、配列ならdepthに1を加えて再帰関数を実行し、数値なら加算する。

function productSum(array) {
    return productSumHelper(array, 1)
}

function productSumHelper(array, depth) {
    let result = 0
    for (const ele of array) {
        if (Array.isArray(ele)) {
            result += productSumHelper(ele, depth + 1)
        } else {
            result += ele
        }
    }
    return result * depth
}

要素数n回実行されるので、計算量は$O(n)$