时间戳

首页 > 解决方案 > 以下代码的复杂度是多少？和重载函数

c++ - 以下代码的复杂度是多少？和重载函数

问题描述

我正在解决一个问题，从给定的日期列表中，我们必须打印第三个最晚的日期。

Input: [24-01-2001, 9-2-2068, 4-04-2019, 31-10-1943, 2-10-2013, 17-12-1990]

output:2-10-2013

我为此编写了以下代码

using namespace std;

struct Date
{
    int Day;
    int Year;
    int Month;
};


 
// comparator function used during insertion in set
bool operator<(const Date& date1, const Date & date2)
{
        if(date1.Year<date2.Year)
                return true;
        if(date1.Year == date2.Year and date1.Month<date2.Month)
                return true;
        if(date1.Year == date2.Year and date1.Month==date2.Month and date1.Day<date2.Day)
                return true;
        return false;
}

Date ThirdLatest(std::vector<Date> & dates) {
       
        //using set data structure to eliminate duplicate dates
        set<struct Date>UniqueDates;
        
        
        //using operator function the dates are inserted into the 
        //set in a sorted manner
        for(auto i:dates)
        {
                UniqueDates.insert(i);
        }
        
        //clear original dates vector
        dates.clear();
        
        //push dates from the set back into dates vector
        for(auto i: UniqueDates)
        {
               dates.push_back(i);
        }
  
        int DatesSize=dates.size();
        return dates[DatesSize-3];
}

我只是想知道这段代码的复杂性，因为它只使用一个有序集，并且使用重载函数将元素插入其中operator<以对日期进行排序，而不是使用该sort()函数。插入有序集合是O(log n)这个代码的复杂性log n还是我计算错了？

另外，我还有一个关于重载函数的问题。我从这里研究了重载函数，当提到符号时，它的函数可以被超越。<但是在这段代码中，它是如何工作的，因为在代码中的任何地方都没有提到插入到集合中的符号。该代码有效，那么<在这里如何使用？

标签： c++

解决方案

当您将元素插入到排序集中时，您已经重载了 operator<。因此，排序集被实现为红黑树。红黑树是一种自平衡二叉搜索树。因为它本质上是一个二进制文件，所以每个元素的插入顺序为 O(log(n))。插入 n 个元素的顺序为 O(n*log(n))。重载的 operator< 用于在二叉树中搜索。如果元素是<那么当前元素然后搜索去左子树，否则它去右子树。继续搜索直到找到元素。详细解释可以在这里找到：https ://www.geeksforgeeks.org/red-black-tree-set-1-introduction-2/ 。

此外，您可以使用 std::sort() 方法对现有向量本身进行排序，而不是将元素插入集合然后将它们重新插入向量中。这可以使用：std::sort(dates.begin(), dates.end()) 来完成。您不需要第三个参数，因为您已经重载了 operator<。有关详细信息，请参阅：https ://www.cplusplus.com/reference/algorithm/sort/ 。

另外，幸运的是 date 中的字段都支持 operator< 和 operator==。但是，通常不能保证通过在其成员上调用 operator<() 来编写任何 operator<() 方法更好，例如：

// comparator function used during insertion in set or by sort method
bool operator<(const Date& date1, const Date & date2)
{
    if(date1.Year < date2.Year)
    {
        return true;
    }
    if(date2.Year < date1.Year)
    {
        return false;
    }
    // Equality case for year
    if(date1.Month < date2.Month)
    {
        return true;
    }
    if(date2.Month < date1.Month)
    {
        return false;
    }
    // Equality case for year and month
    if(date1.Day < date2.Day)
    {
        return true;
    }
    if(date2.Day < date1.Day)
    {
        return false;
    }
    return false;
}

清除向量并推回所有元素也有一个缺点，即如果向量相当大，则在清除时它将变得尽可能小，并且一旦穿过分配的内存就会被重新分配和重新复制。即使您正在执行此类操作，也建议在插入之前调用：vector.reserve()，或者只是重新分配所有值而不清除/推回。

如果您的代码需要经常处理日期并且需要按日期排序条目，我建议使用：map/set 而不是 vector 来存储日期。

由于问题是找到第三大日期，而不是通过对整个向量进行排序或将所有元素插入一个集合来对所有元素进行排序，您需要将元素插入到大小为 3 的 priority_queue 中。通常，要找到第 K 个最大的元素，需要维护一个大小为K的priority_queue。优先队列以堆的形式实现，是完全平衡的二叉树。它不像有序集合和映射中使用的 AVL 或红黑树那样有序，但针对插入进行了优化，在这种情况下甚至比有序集合更快。

通常，优先级队列总是首先拥有最大的元素。因此，您需要定义一个比较器，以便将最小元素放置在您的情况所需的顶部。

template<class T>

class TestAscending
{
public:
    bool operator() (const Date& l, const Date&r) const
    {
        return r < l;
    }
};

// Somewhere in code you would define priority queue as
priority_queue<Date, vector<Date>, TestAscending<Date> > p;

因此，您将 vector 的元素一一插入到 priority_queue 中。直到，集合的大小为 < k，您可以在优先级队列中添加元素而无需任何条件检查。当priority_queue (p.size()) 的大小变为k 时，只有当它大于优先级队列的最顶部元素(p.top()) （最小）时才添加元素。您可以通过调用 p.pop() 删除现有的最小并使用 p.push() 添加新的最小来做到这一点。

在程序结束时，最顶层元素 p.top() 将是第 k 个最大元素。

由于优先级的大小为 K，因此在最坏的情况下，程序的复杂性从 O(n log(n)) 降低到 O(n log(k))。由于优先级队列甚至比插入中的设置更快，因此复杂性和执行时间将比使用大小为 k 的集合更快。

推荐阅读