Временная эффективность JavaScript

Question

Подскажите пожалуйста, правильно ли, что эффективность первой функции O(n), а второй O(n^2) и их совместная O(n^2)?

function permute(arr) {
  let ch;
  for (let i = 0; i < arr.length; i++) {
    ch = arr.splice(i, 1)[0];
    used.push(ch);
    if (arr.length == 0) {
      perm.push(used.slice());
    }
    permute(arr);
    arr.splice(i, 0, ch);
    used.pop();
  }
  return perm
};



function combination(arr, k){
    let res = [];
    for(let i=0; i<n - k+1; i++){
        for(let j=i+1; j<n; j++)
            res.push([arr[i], arr[j]])
    }
    return res;
}

Answer 1

Функция permute порождает все перестановки массива arr. Код с комментариям по сложности:

/* T(N)    */ function permute(arr) {
/*         */   let ch;
/* N       */   for (let i = 0; i < arr.length; i++) {
/* N^2     */     ch = arr.splice(i, 1)[0];
/* N       */     used.push(ch);
/* N       */     if (arr.length == 0) {
/* N       */       perm.push(used.slice());
/*         */     }
/* NT(N-1) */     permute(arr);
/* N^2     */     arr.splice(i, 0, ch);
/* N       */     used.pop();
/*         */   }
/* 1       */   return perm
/*         */ };

Через T(N) обозначено время работы функции permute. N - длина массива arr. Цикл for работает за время N - это из руководства по JavaScript.

Один вызов splice требует времени N - когда удаляется или вставляется элемент, хвост массива надо сместить на одну позицию, что требует времени. Кроме того каждая строка со splice исполняется N раз. Перемножаем - N^2.

used.push, used.pop выполняются за константу (за одну единицу времени). Вызываются N раз в цикле. Тоже верно для if.

perm.push - константа. used.slice - N: копирование массива длины N. Умножать на N - число итераций их не нужно. Благодаря if они выполняются только один раз.

permute вызывается для массива длины N-1: T(N-1). Вызывается он N раз.

Общая формула для сложности T(N) = N + N^2 + N + N + N + NT(N-1) + N^2 + N + 1. Так как мы работаем в терминах "О-большого", то формула своебразно упрощается: T(N-1) = N^2 + TN(N-1). Все коэффициенты заменяются на единицы. Все функции которые растут медленнее самой быстрой (N^2) убираются.

Отдельно надо оценить T(1). Он будет равен N - длине массива used в этот момент.

Раскроем рекуррентную формулу:

T(N) = N^2 + NT(N-1) =
= N^2 + N((N-1)^2 + (N-1)T(N-2)) = 
= N^2 + N(N-1)^2 + N(N-1)T(N-2) = 
= N^2 + N(N-1)^2 + N(N-1)((N-2)^2 + (N-2)T(N-3)) =
= N^2 + N(N-1)^2 + N(N-1)(N-2)^2 + N(N-1)(N-2)T(N-3) =
...
= [N^2 + N(N-1)^2 + N(N-1)(N-2)^2 + ... + N(N-1)(N-2)...3*2*1^2] + N!T(1) <= 
<= [N! + ... + N!] + N * N! = 
= N * N! + N * N! = 
= N * N!

Там где неравенство - это оценка сверху. Особенности "О-большого" позволяют написать что в итоге T(N) = N * N!.

Ту же самую оценку можно получить более грубо таким рассуждением: время работы алгоритма не может быть меньше чем объём его результата. Это интуитивно очевидно: один элемент результата требует для вычисления и записи не меньше одной единицы времени. Объём результата N * N!: первый сомножитель длина одной перестановки, второй - число перестановок. Следовательно любая процедура порождающая перестановки работает за N * N! или дольше. Предыдущее рассуждение получает эту формулу уже не как оценку, а как точный результат.

БЛОГ НА HUSL

Временная эффективность JavaScript

Ответы (1 шт):