Какова временная сложность этого алгоритма SET Cover? (C ++) - PullRequest
Новая
       5

Какова временная сложность этого алгоритма SET Cover? (C ++)

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

В книге я обнаружил, что проблему покрытия множеств можно решить за время O (LogN), используя алгоритм жадного приближения. Я реализовал жадный алгоритм в C ++. Вот мой код. 

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()));
}

Так что моя проблема в том, какова временная сложность моего кода. Это взято LogN или N ^ 2. Пожалуйста, помогите мне, ребята, рассчитать сложность времени этого кода.

...