Отношение повторения для определенной функции - PullRequest
Новая
       2

Отношение повторения для определенной функции

0 голосов
/ 22 февраля 2019

Задача состояла в том, чтобы найти рекуррентное отношение для этой функции, а затем найти класс сложности для нее.При условии, моя работа и функции.У меня такой вопрос, я чувствую, что пропускаю какой-то шаг в классе повторяемости и сложности.Это правильно?Следующий код на JavaScript. 

function divideAndConquerSum(x){
if(x.length<1){
return 0;
}
if(x.length == 1){
return x[0];
}
var third = Math.floor((x.length-1)/3);
var next = (third *2)+1;
var y = x.slice(0, third+1);
var z = x.slice(third+1, next+1);
var a = x.slice(next+1, x.length);
return divideAndConquerSum(y)+divideAndConquerSum(z)+divideAndConquerSum(a);

}

///

work:

  1. Проверяет, имеет ли массив нулевую длину ...это постоянное время, поэтому: + 1

  2. Проверяет, имеет ли массив длину 1, если да, то возвращает.Также постоянное время: + 1

  3. Разбивает массив на 3. Функция также постоянна независимо от размера n: + 1

  4. Функциязатем добавляет себя три раза, но каждый раз это рекурсивный вызов 1/3 размера n: 3T (1/3)

1 + 1 + 1 + 3T (1 /3)

3T (1/3)

вызывает себя, чтобы мы могли определить отношение как

3T (1/3)

9T (1/ 9)

27T (1/27)

этот шаблон может отображаться как

3log3n

, поэтому мы имеем

1 +1 + 1 + 3log3n

, который является классом сложности

O (log n)

это правильно?

...