Нахождение временной сложности решения по возврату для генерации всех подмножеств - PullRequest
Новая
       91

Нахождение временной сложности решения по возврату для генерации всех подмножеств

0 голосов
/ 30 октября 2018

Учитывая проблему различных целых чисел, генерировать все подмножества. https://www.interviewbit.com/problems/subset/

Я нашел два решения.

первое решение :: 

 void helper_subsets(vector<vector<int>> &res , vector<int> &A , 
    vector<int> &subset ,int current)
{
    if(current == A.size())
        res.push_back(subset) ;
    else
    {
        helper_subsets(res,A,subset,current+1) ;
        subset.push_back(A[current]) ;
        helper_subsets(res,A,subset,current+1) ;
        subset.pop_back() ;
    }
}

vector<vector<int> >subsets(vector<int> &A) {
    vector<vector<int>> res ;

    sort(A.begin(),A.end()) ;

    vector<int> subset ;

    helper_subsets(res , A , subset , 0 ) ;

    sort(res.begin(),res.end()) ;
    return res ;
}

Второе решение :: 

void helper_subsets(vector<vector<int>> &res , vector<int> &A , 
    vector<int> &subset ,int current)
{
    res.push_back(subset) ;
    for(int i = current ; i < A.size() ; i++)
    {
        subset.push_back(A[i]) ;
        helper_subsets(res,A,subset,i+1) ;
        subset.pop_back() ;
    }
}

vector<vector<int> > subsets(vector<int> &A) {
    vector<vector<int>> res ;

    sort(A.begin(),A.end()) ;

    vector<int> subset ;

    helper_subsets(res , A , subset , 0 ) ;

    sort(res.begin(),res.end()) ;
    return res ;
}

Проблема в том, что я могу математически рассчитать временную сложность первого решения, используя дерево рекурсии. t (n) = 2t (n-1) + c (то есть 2 рекурсивных вызова с размером n-1 и некоторым постоянным временем для каждого n) t (n) = O (2 ^ n), решая вышеуказанное рекуррентное соотношение.

Но со вторым решением я не могу определить рекуррентное отношение, чтобы, наконец, использовать обратную подстановку, чтобы получить сложность времени, и не смог получить ее методом дерева рекуррентности. Пожалуйста, помогите мне найти временную сложность второго решения.

1 Ответ

0 голосов
/ 01 ноября 2018

Аналогичное рекуррентное соотношение для задачи 2: 

       n - 1
T(n) =   Σ  T(n - i) + c
       i = 1

- что следует из for -цикла от current до A.size(). Чтобы решить эту проблему, раскройте первый член: 

T(n) = T(n - 1) + T(n - 2) + T(n - 3) + ... + T(1) + c
  ____ --------
 |
 |   =            T(n - 2) + T(n - 3) + ... + T(1) + c +
  -->  T(n - 2) + T(n - 3) + ... + T(1) + c

     = 2 * [T(n - 2) + T(n - 3) + ... + T(1) + c]
     = 2 * T(n - 1)

Т.е. очень похожее рекуррентное соотношение, отличающееся только константой. Он по-прежнему оценивается как O(2^n), принимая базовый случай за T(1) = O(1).

...