Javascript 时间复杂度分析

Question

您好，我一直在研究并尝试学习如何检查某些算法的时间复杂度。我看过这个非常有帮助的视频。

话虽如此，我想知道并开始尝试计算出某些算法的最坏情况和平均情况。

1

我相信下面的代码片段是 O(n)，因为要找到 sin 的值，我们必须循环整个数组。

function mySin(x, iterNum) {
    var mxx = -x*x;
    var sin = 1;
    var n = 0;
    var term = 1;
    for (var i = 1; i <= 2*iterNum; i++) {
        n = n + 2;
        term = term * mxx / ( n*(n+1) );
        sin = sin + term
    }
    sin = x*sin;
    console.log(sin + " = my function.");
    console.log(Math.sin(x)  + " math.sin");
}

再次感谢

2

function calculateFibonacciSum (num) {
    if(cachedNumbers[num]) {
        return cachedNumbers[num];
    }
    if(('number' === typeof num) && num <= 0) {
        throw new Error ('Fibonnci series starts with 0. Please, enter any interget greater than or equal to 0');
    }
    else if(('number' === typeof num) && num === 0) {
        return 0;
    }
    else if(('number' === typeof num) && (num === 1 || num === 2)) {
        return 1;
    }
    else {
        var value = calculateFibonacciSum(num-1) + calculateFibonacciSum(num-2);
        cachedNumbers[num] = value;
        return value;
    }
}

虽然对于这个我认为它也是 O(n) 因为在第一个 if/else 语句中 tc 是 O(1) 因为它的参赛者而最后的 else 语句我们必须循环所有数字并且如果数字是不计算然后再次调用该函数(也称为递归)。

TIA

Answer 1

这两个对我来说似乎都是正确的。这里有更多的解释:

1.

这实际上是 O(n)，因为循环有 n 次迭代，其余时间不变； n与iterNum成正比

2.

这也是线性时间，但只是因为您缓存了先前计算的结果。否则它将是 O(2ⁿ)。 它是线性时间，因为它本质上是向下运行到基本情况(0 和 1)的循环。事实上，您可以使用循环而不是递归来重写这个。