C++: функция оптимальной сложности

Это не было четко указано в описании, но я полагаю, вы имели в виду, что пакет не может быть скомпилирован, если некоторые из пакетов, от которых он зависит, еще не были скомпилированы.

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

(Что такое «глубина зависимости»? Думайте о зависимости как о направленном дереве, тогда глубина элемента - это самый длинный путь от элемента до листьев, от которых он зависит. Формально, если у пакета нет зависимостей, то его глубина равна нулю, а для других - Depth [package] = max (Depth [depends_of_the_package]) + 1. Обратите внимание, что пакеты одинаковой глубины обязательно независимы друг от друга)

Я бы использовал следующий код

class PackageOptimizer
{
    public:
    struct PackageDependency
    {  
        size_t Count() const
        {
            return m_end - m_begin;
        }
        size_t m_begin;
        size_t m_end;
    };

    vector<size_t> FindLeaves()
    {
        vector<size_t> leaves;
        for(size_t i = 0; i<m_deps.size(); i++)
        {
            if (m_deps[i].m_begin == m_deps[i].m_end)
                leaves.push_back(i);
        }

        return leaves;
    }

    vector<int> ComputeDepthMap()
    {
        vector<int> Depth(m_deps.size());
        vector<int> Count(m_deps.size(),0);
        vector<size_t> currSet = FindLeaves();
        vector<size_t> nextSet;

        int currDepth = 0;
        while(!currSet.empty())
        {
           for(size_t elem : currSet)
           {
               Depth[elem] = currDepth;

               for( size_t  upPackage = m_depsInv[elem].m_begin;
                            upPackage < m_depsInv[elem].m_end; 
                            upPackage++)
                {
                    Count[upPackage]++;

                    if (Count[upPackage] == m_deps[upPackage].Count())
                    {
                        nextSet.push_back(upPackage);
                    }
                }
           } 
           swap(nextSet, currSet);
           currDepth++;
           nextSet.clear();
        }

        return Depth;
    }

    private:
    // package i is dependent on
    // m_indices[m_deps[i].m_begin], m_indices[m_deps[i].m_begin+1], ... m_indices[m_deps[i].m_end-1]
    vector<PackageDependency>   m_deps; 
    vector<size_t>              m_indices;

    // following packages are dependant on package i
    // m_indicesInv[m_depsInv[i].m_begin], m_indicesInv[m_depsInv[i].m_begin+1], ... m_indicesInv[m_deps[i].m_end-1]
    vector<PackageDependency>   m_depsInv; 
    vector<size_t>              m_indicesInv;
};

Просто не хватает методов для запуска m_deps, m_indices, m_depsInv, m_indicesInv, но это не сложно. С помощью вычислений Depth вы можете легко организовать пакеты в соответствии с порядком выполнения. Кроме того, вам необходимо убедиться, что в пакетах нет циклов зависимости, иначе этот код никогда не завершится.

С точки зрения производительности этот алгоритм занимает около O(n + m), где n - количество пакетов, а m - общее количество зависимостей. Примерно столько же времени займет создание m_deps, m_indices, m_depsInv, m_indicesInv.

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