Недавно я придумал наивное (+ бедное) решение Британской проблемы изменения (т.е. Сколько комбинаций монет может генерировать данное общее количество). Теперь у меня есть лучшее решение, но мы все еще заинтересованы в решении временной и пространственной сложности этих двух решений ниже.
Худшее решение
Это решение рекурсивно пытается комбинировать каждое число с самим собой и с любым другим числом, что приводит к многократной работе. Я считаю это O (n ^ n) временем и не уверен, как измерить сложность пространства (но он огромный, поскольку мы сохраняем каждый результат). Мысли?
var makeChange = function(total){ // in pence
var allSets = new Set();
var coins = [1,2,5,10,20,50,100,200];
var subroutine = (arr, total) => {
if(total < 0){ return; }
if(total === 0){
allSets.add(''+arr);
} else {
// increase each coin amount by one and decrease the recursive total by one
for(var i = 0; i<coins.length; i++){
if((total - coins[i]) >= 0){
subroutine(arr.slice(0,i).concat(arr[i]+1).concat(arr.slice(i+1)), (total - coins[i]))
}
}
}
};
var zeros = new Array(coins.length).fill(0);
subroutine(zeros, total);
return allSets.size;
};
Улучшенное решение
Это решение все еще имеет огромную пространственную сложность, но я считаю, что временная сложность имеет-улучшенную до O (n!), Так как мы каждый раз рекурсируем на меньших подмножествах монет.
var makeChange = function(total){ // in pence
var allSets = new Set();
var coins = [1,2,5,10,20,50,100,200];
var subroutine = (arr, total, start) => {
if(total < 0){ return; }
if(total === 0){
console.log(''+arr);
allSets.add(''+arr);
} else {
// only solve for coins above start, since lower coins already solved
for(var i = start; i<coins.length; i++){
if((total - coins[i]) >= 0){
subroutine(arr.slice(0,i).concat(arr[i]+1).concat(arr.slice(i+1)), (total - coins[i]), i);
}
}
}
};
var zeros = new Array(coins.length).fill(0);
for(let i = 0; i<coins.length; i++){
subroutine(zeros, total, i);
}
return allSets.size;
};
Пожалуйста, помогите мне понять, правильны ли мои оценки сложности времени и пространства и как лучше оценить будущие проблемы, подобные этим. Спасибо!
Сложность первого алгоритма на самом деле не является O (n ^ n). N - это переменная, которая представляет ваш вход. В этом случае я буду ссылаться на переменную "total" в качестве вашего ввода, поэтому N основывается на итоговом. Для того чтобы ваш алгоритм был O (n ^ n), дерево повторения должно было иметь глубину N и коэффициент ветвления N. Здесь ваша глубина вашего повторения основана на наименьшей переменной в вашем массиве монет. Существует одна ветка дерева рекурсии, где вы просто вычитаете это значение каждый раз и рекурсируете до тех пор, пока общее значение не будет равно нулю. Учитывая, что это значение является постоянным, можно с уверенностью сказать, что ваша глубина равна n. Ваш коэффициент ветвления для дерева рекурсии также основан на вашем массиве монет или количестве значений в нем. Для каждого вызова функции вы создаете C другие вызовы функций, где C - размер вашего массива монет. Это означает, что ваша функция на самом деле O (n ^ c) не O (n ^ n). Ваши сложности времени и пространства основаны на размере вашего массива монет, а также на вашем номере ввода.
Сложность пространства для вашей функции O (n ^ c * c). Каждый раз, когда вы вызываете свою функцию, вы также передаете ей массив размера, основанный на вашем вводе. Мы уже показали, что существуют вызовы O (n ^ c), и каждый вызов включает массив размера c.
Помните, когда анализируете сложность функций, чтобы учесть все входы.