선생님 조합수를 사용해도 시간복잡도는 O(n!)인거 같은데 제가 잘못 생각한걸까요?
조합수를 사용하지 않아도 메모이제이션을 사용하면 O(n!)인거 같아서 질문 드립니다.
혹시 맞으면 시간복잡도를 O(n^k)정도로 바꿀 수 있는 방법이 있을까요?
조합수를 사용하지 않은 풀이입니다. 비효율적인 부분이나 잘못된점도 알고 싶습니다.
function solution(n, f){
const arrayMaker = (len, generator) =>
Array.from({ length: len}, (_, i) => generator(i));
const base = arrayMaker(n, idx => idx + 1);
const checker = arrayMaker(n, () => 0);
const temp = arrayMaker(n, () => 0);
const change = i => array => array[i] === 0 ? array[i] = 1 : array[i] = 0;
function *permutation (position){
if(position === n){
yield temp;
}
else{
for(let i = 0; i < checker.length; i++){
if(checker[i] === 0){
temp[position] = base[i];
change(i)(checker);
yield *permutation(position + 1);
change(i)(checker);
}
}
}
}
function combination (n, r, seq){
if(bin[n - 1][r - 1] !== 0) return bin[n - 1][r - 1];
if(n === 1) return seq[r-1];
return bin[n - 1][r - 1] = combination(n - 1, r, seq) + combination(n - 1, r + 1, seq);
}
let bin;
for(let order of permutation(0)){
bin = arrayMaker(n, () => arrayMaker(n, () => 0));
if( combination(n, 1, order) === f) return order;
}
}
console.log(solution(4, 16));