Анализ сложности времени Javascript - PullRequest
Новая
       27

Анализ сложности времени Javascript

0 голосов
/ 12 мая 2018

Привет, я изучал и пытался научиться проверять временную сложность некоторых алгоритмов.Я видел это видео, которое было очень полезным.

При этом я удивился и начал пытаться отработать случай Уорста и средний случай некоторых алгоритмов.

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

1 Ответ

0 голосов
/ 12 мая 2018

Оба они кажутся мне правильными.Вот еще несколько объяснений:

1.

Это фактически O (n), поскольку существует n итераций цикла, остальная постоянная времени;и n пропорционально iterNum

2.

Это также линейное время, но только потому, что вы кэшируете результаты предыдущих вычислений.В противном случае это будет O (2 n ).Это линейное время, поскольку оно, по сути, запускает цикл до базовых случаев (0 и 1).Фактически, вы могли бы переписать этот, используя цикл вместо рекурсии.

...