dimanche 1 mars 2020

Whats the Time Complexity of this SET Cover algorithm ? (C++)

In a book, I found that the set cover problem can be solve O(LogN) time by using greedy approximation algorithm. I implemented greedy algorithm in C++ So here is my Code.

do{

        std::set<int> result;

        for(int i = 0; i < input.size(); i++){
            if(com[i]){
                result.insert(input[i].begin(), input[i].end());
            }
        }

        if(std::includes(result.begin(), result.end(), target.begin(), target.end())){
            for(auto i = 0; i < input.size(); i++){
                if(com[i]){
                    output.push_back(input.at(i));
                }
            }
            return;
        }
        result.clear();

    }while(std::next_permutation(com.begin(), com.end()));
}

So my problem is what's the time complexity of my code. Is it taken LogN or N^2. Please help me guys to calculate this code's time complexity.

Aucun commentaire:

Enregistrer un commentaire