为什么两个看似lower_bound()相同的方法具有不同的处理时间 [英] Why two seemingly lower_bound() same method has different processing time

问题描述

虽然我解决了算法问题，但由于时间问题，我的解决方案无法通过.
但是我意识到，通过的人和我的人之间唯一的区别是

While I solve an algorithm question, My solution couldn't get passed because of time issue.
But I realized that the only difference between passed one and mine was

bag.lower_bound(jewerly[i].first) != bag.end() //passed

lower_bound(bag.begin(), bag.end(), jewerly[i].first) != bag.end() //failed

我已经用clock()检查了它，显然它比另一个慢.

I've already checked it with clock() and It was obviously slower than the other one.

这两个代码有什么区别?

what makes the difference between the two codes?

#include <cstdio>
#include <set>
#include <algorithm>
using namespace std;

const int MAXN = 300100;

bool cmp(pair<int, int> a, pair<int, int> b)
{
    if(a.second != b.second)
        return a.second > b.second;
    return a.first < b.first;
}

pair<int, int> jewerly[MAXN];
multiset<int> bag;

int main()
{
    int N, K, M;
    scanf("%d%d", &N, &K);

    int w, p;
    for(int i = 0; i<N; i++)
    {
        scanf("%d%d", &w, &p);
        jewerly[i] = {w, p};
    }

    for(int i = 0; i<K; i++)
    {
        scanf("%d", &M);
        bag.insert(M);
    }

    sort(jewerly, jewerly+N, cmp);

    clock_t begin = clock();

    long long sum = 0;
    for(int i = 0; i<N; i++)    // #1
    {
        if( bag.empty() ) break;
        if( lower_bound(bag.begin(), bag.end(), jewerly[i].first) != bag.end())
        {
            sum += jewerly[i].second;
            bag.erase(bag.lower_bound(jewerly[i].first));
        }
    }

    /*
    for(int i = 0; i<N; i++)   //#2
    {
        if( bag.empty() ) break;
        if( bag.lower_bound(jewerly[i].first) != bag.end())
        {
            sum += jewerly[i].second;
            bag.erase(bag.lower_bound(jewerly[i].first));
        }
    }
    */

    clock_t end = clock();    
    printf("%lf\n", double(end-begin));
}

测试输入 10 8 1 65 5 23 1 30 9 40 3 50 2 90 5 30 5 30 7 80 2 99 10 15 12 5 3 5 2个 2

Test Input 10 8 1 65 5 23 1 30 9 40 3 50 2 90 5 30 5 30 7 80 2 99 10 15 12 5 3 5 2 2

推荐答案

std::lower_bound无法访问std::multiset的内部结构.它不是O(log N)，因为std::multiset的迭代器不是随机访问的(并且您不可能比Theta(N)更快地实现非随机访问的迭代器)

std::lower_bound has no access to internal structure of std::multiset. It is not O(log N) because iterators of std::multiset are not random-access (and you can't possibly implement it for not random-access iterator faster then in Theta(N))

std::multiset::lower_bound确实可以访问树的结构，并且可以轻松实现，复杂度为O(tree height)，即O(log N)

std::multiset::lower_bound does have access to structure of a tree and can be easily implemented with complexity O(tree height) which is O(log N)

这篇关于为什么两个看似lower_bound()相同的方法具有不同的处理时间的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！