C++ 提高时间复杂度

Question

求教如何提高程序的时间复杂度。我无法更改接口（函数头）

比如我在find()之前做sort，会有什么影响吗？或者我的代码是否有任何替代方案。

谢谢大家的建议

在link整个程序中，这里是部分代码 https://onecompiler.com/cpp/3xxpa4w9q

bool Company::operator == (Company cmpx)  const
{ 

    return ( ( (strcasecmp(addr.c_str(), cmpx.addr.c_str()) == 0) 
            && (strcasecmp(name.c_str(), cmpx.name.c_str()) == 0) )
            || (id == cmpx.id)
    );
    
}

void CVATRegister::sortI (vector<unsigned int> &TotalInvoice) const 
{
    sort(TotalInvoice.begin(), TotalInvoice.end(), greater<unsigned int>());
}

bool CVATRegister::cancelCompany  ( const string  &name, const string &addr )
{
    Company cmp(name, addr, "-1");
    auto itr = find(DCompany.begin(), DCompany.end(), cmp);

    if(itr != DCompany.end())
     {   
        DCompany.erase(itr);
        return true;
     }
     
     return false;
}

bool CVATRegister::newCompany ( const string &name, const string &addr, const string &taxID )
{
    Company cmp(name, addr, taxID);
    if ( find(DCompany.begin(), DCompany.end(), cmp) == DCompany.end() )
    {
        DCompany.push_back(cmp);
        return true;
    }
    return false;
}

bool CVATRegister::invoice ( const string &taxID, unsigned int amount )
{
    Company cmp("", "", taxID);

    auto itr = find(DCompany.begin(), DCompany.end(), cmp);

    if(itr != DCompany.end())
     {   
        TotalInvoice.push_back(amount);
        DCompany[distance(DCompany.begin(), itr)].saveInvoice(amount);
        return true;
     }
     
     return false;    
}

bool CVATRegister::audit ( const string &name, const string  &addr, unsigned int &sumIncome ) const
{
    Company cmp(name, addr,"-1");

    auto itr = find(DCompany.begin(), DCompany.end(), cmp);

    if(itr != DCompany.end())
     {   
        sumIncome = DCompany[distance(DCompany.begin(), itr)].getTotalIncome();
        return true;
     }
     return false;
}

void CVATRegister::sortC (vector<Company> &c) const
{
   sort(c.begin(), c.end());
}


bool CVATRegister::firstCompany ( string &name, string &addr ) const
{
    vector<Company> tmp = DCompany;
    sortC(tmp);

    if( tmp.size() > 0 )
    {   
        name = tmp[0].getName();
        addr = tmp[0].getAddr();
        return true;
    }
    return false;
}

Answer 1

您正在将公司存储在向量中。在多种方法中，对向量进行排序和搜索。

如果向量已经排序，请不要再次排序
正如所指出的，使用二进制搜索而不是 std::find
或使用 hash-based 容器，例如std::unordered_set 存储公司。这应该使大多数操作平均为 O(1)。
或使用多个容器，accessing/updating每个容器都需要
或自己编写 :)

C++ 提高时间复杂度

C++ Improve time complexity

c++

time