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