LIS 的运行时复杂性和正确性

Question

function LIS(str1){

return LISUtil(str1, 0);

function LISUtil(str1, index){
    if(index == str1.length){
        return 0;
    }
    var min = str1[index],
        len = 1;

    for(let i=index+1; i<str1.length; i++){

        if(min < str1[i]){
            len++;
            min = str1[i];
        }
    }
    return Math.max(len, LISUtil(str1, index+1));
}

}

这是我得出的最长递增子序列（是的，它看起来很奇怪，但请暂时忽略它！）。

我读到 LIS 的运行时间复杂度为 2^n。使用 DP，您可以达到 n^2.

当我思考并尝试我的 LIS 函数时，我确信它在 n^2 中运行s。它经过 n，每个索引检查 O(n) 次 -> n^2.

我有运行一些测试用例，它 return 正确。但是我没有用过 DP...意思是它必须是这两个中的任何一个。

我的函数有问题。它没有获得 LIS。
运行时间是 2^n，我只是没能正确计算运行时间。

谁能帮我理清思路？是不是我的函数有问题，是运行time 2^n，还是不用DP也能得到LIS？

Answer 1

它没有得到LIS。例如，

LIS([1, 6, 2, 3, 7, 4, 5])

returns3.应该是4.

LIS 的运行时复杂性和正确性

Runtime complexity & correctedness of LIS

javascript

algorithm

time-complexity

lis