Почему сложность времени так отличается в следующих двух решениях? - PullRequest
Новая
       6

Почему сложность времени так отличается в следующих двух решениях?

0 голосов
/ 02 марта 2020

Я пытался решить эту проблему Leetcode - https://leetcode.com/problems/partition-equal-subset-sum/. Я придумал запоминающееся решение, которое так и не было принято, потому что, видимо, это заняло слишком много времени. Ниже приведено это решение. 

class Solution{
public:
    bool canPartition(vector<int>& nums){
        int totalSum = 0;
        for(auto value : nums)
            totalSum += value;
        if(totalSum%2 == 1)
            return false;
        return helper(nums, totalSum/2, 0);
    }
private:
    bool helper(vector<int> nums, int totalSum, int index){
        if(totalSum == 0)
            return true;
        if(totalSum < 0)
            return false;
        if(index == nums.size())
            return false;
        // Check in the cache
        pair<int, int> key = make_pair(totalSum, index);
        if(cache.count(key)){
            //cout << "Cache hit!\n";
            return cache[key];
        }
        // Include this
        bool include = helper(nums, totalSum-nums[index], index+1);
        // Exclude this
        bool exclude = helper(nums, totalSum, index+1);
        cache[key] = include || exclude;
        return cache[key];
    }
    map<pair<int, int>, bool> cache;
};

Попробовав некоторое время, я внес небольшое изменение, в котором вместо использования логических выражений "include" и "exclude" я просто выполнил приведенное ниже, и сложность по времени так значительно улучшилась. что он упал с ~ 1000 мс до ~ 0 мс. Я запутался, почему это произошло? Почему использование двух логических значений и сохранение их результатов на карте намного медленнее, чем когда они не используются? 

cache[key] = helper(nums, totalSum-nums[index], index+1) || helper(nums, totalSum, index+1);

Может кто-нибудь просветить меня здесь? Довольно запутался по этому поводу.

1 Ответ

3 голосов
/ 02 марта 2020

Первая версия вызывает helper дважды - один раз для include и один раз для exclude. Вторая версия, так как она использует логический оператор или, не будет вызывать 2nd helper, если первый helper равен true. Другими словами, если include истинно, вызов exclude не будет выполнен, поскольку он не изменит результат выражения.

Другим ударом производительности является параметр nums на helper. Вы не вносите в него никаких изменений в функции, поэтому можете передать его как const vector<int> &nums, чтобы избежать создания ненужной копии всего содержимого массива. canPartition также может принимать свой параметр в качестве константной ссылки, поскольку вы не изменяете его.

...