섹션 8의 13번 수열의 추측 시간복잡도 질문 있습니다.

Question

선생님 조합수를 사용해도 시간복잡도는 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 ));

김태원 · Answer

안녕하세요^^ 순열을 돌아야 해서 n! 은 해야 하지 않나 생각됩니다. 더 줄일 수 있는 방법은 모르겠네요.