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

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

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

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

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

1 

function sqrt(num) {
guess = num / 3;

  do {
    lastGuess = guess; 


    guess = (num / guess + guess) / 2;

   while(Math.abs(lastGuess - guess));

  return guess;  /

Правильно ли я сказать, что это O (n), мои рассуждения таковы, что мы повторяем цикл до тех пор, пока не будет найдено приблизительное значение.

2 

function max(numArray) 
{
    // copy the given array 
    nums = numArray.slice();

    // base case: if we're at the last number, return it
    if (nums.length == 1) { return nums[0]; }

    // check the first two numbers in the array and remove the lesser
    if (nums[0] < nums[1]) { nums.splice(0,1); }
    else { nums.splice(1,1); }

    // with one less number in the array, call the same function
    return max(nums);
}

От пользователя спасибо за ссылку, он вычисляет самое большое число в массиве. Можно ли с уверенностью сказать, что сложность времени в этом O(n), поскольку наибольшее число может быть самым последним, и, следовательно, почему O(n)?

# 3 Хотя я верю в следующий фрагмент, это 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");
}

Еще раз спасибо

1 Ответ

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

Для второго вы правы: это O(n), так как вам нужно пройти n элементов, чтобы найти максимум. В первом случае, однако, у ypu нет ничего, что изменило бы ваш ввод. Всегда будет несколько шагов, пока вы не дойдете до догадки, которая каким-то образом не зависит от размера числа, которое вы передаете. Поэтому это скорее O(1). Например, все эти числа имеют только одну цифру, но алгоритм принимает разное количество итераций для каждой: 

 sqrt(9) // 1 iteration
 sqrt(3) // a few iterations

Можно также сказать, что мы не можем предсказать временную сложность первого.

...