Объяснение и сложность видимых точек в кодовом бою

Я столкнулся с этим вопросом о кодовом бою / кодовом сигнале. Учитывая массив точек на плоскости, найдите максимальное количество точек, видимых из начала координат с углом обзора 45 градусов.

int visiblePoints(std::vector<std::vector<int>> points) {


const double pi=M_PI,pi_45=M_PI_4,pi_360=M_PI*2.0;
const double epsilon=1e-10;
int n=points.size(),result=0;
vector<double> angles(n);
for(int i=0;i<n;i++){
    double angle=atan2(points[i][1],points[i][0]);
    angles[i]=angle;
    if(angle<pi_45-pi){
        angles.push_back(angle+pi_360);
    }
}
sort(angles.begin(),angles.end());
//std::sort(angles.begin(), angles.end());
for(auto it=angles.begin();it!=angles.begin()+n;++it){
    auto bound=upper_bound(it,angles.end(),*it+(pi_45+epsilon));
    int curr=distance(it,bound);
    if(curr>result){
        result=curr;
    }
}
return result;
/*
for (auto it = angles.begin(), e = angles.begin() + n; it != e; ++it) {
    auto bound = std::upper_bound(it, angles.end(), *it + (pi_over_4 + epsilon));
    int cur = std::distance(it, bound);
    if (cur > result)
        result = cur;
}
return result;
*/

Итак, код в порядке, я могу понять, что здесь происходит. Я просто хотел проверить временную сложность O (NlogN). Первый цикл for занимает O(N).points — это массив из нескольких точек в 2D. Например, points = [[1,1],[3,1],.....] Затем у нас есть часть сортировки. Я предполагаю, что сортировка занимает O (N * logN). Конечно, быстрая сортировка в худшем случае занимает O(N^2), но пока я проигнорирую этот факт. И тогда последний цикл снова O (N). Кроме того, сложность пространства в этом сценарии будет O (1) или O (N) (из-за сортировки) Спасибо.


time-complexity c++11 space-complexity
person Sparsh Garg    schedule 28.01.2020    source источник
comment
средний линеарифмический случай std::sort равен O(n*log(n)), средний линейный случай одиночного вызова std::upper_bound равен O(log2(angles.end() - it)) и distance является линейным   -  person Swift - Friday Pie    schedule 29.01.2020

Ответы (1)


arrow_upward
0
arrow_downward

Вы можете использовать 2 указателя, поэтому сложность будет всего O(N), не считая sort.

    int l = 0, r = 0, res = 0;
    while (l < N) {
        while (r < N + l && angles[r] - angles[l] < M_PI_4 + eps) ++r;
        res = max(res, r - l);
        ++l;
    }
    return res;
person Denis Glotov    schedule 03.12.2020