Оценка сложности алгоритма

Время запроса:

Необходимо найти локусы в которых лежат 4 точки.

Т.к. локусы хранятся в отсортированном списке длиной N² в худшем случае (могут быть вырожденные случаи), т.е. необходимо время O(4*log N²) = O(8*log N) = O(log N)

Память:

Храним 3 списка с N точками и список локусов (N + 1) ². Т.е. O(3N+ (N + 1) ² ) = O(N²)

Время предобработки:

Для каждого элемента списка точек list_x_sorted необходимо создать N локусов, обработав список list_y_sorted. Для полученных локусов надо найти число доминирования за время O(log N). В работе проделано усовершенствование алгоритма. Вводится еще один итератор, который помнит число доминирования для диагональной матрицы. Тогда число доминирование считается итеративно (см. рис. 2.5):

Domin_locus1 = domin_locus2 + domin_locus3 – domin_locus4

Рис 2.5. Подсчет числа доминирования

Приложение а. Листинг программы (реализация алгоритма)

//---------------------------------------------------------------------------

#ifndef Unit1H

#define Unit1H

#include <list>

#include <vector>

#define INFINITY 10000000

#define INFINITY_POINT TPoint(INFINITY, INFINITY)

#define INFINITY_MYPOINT MyPoint(INFINITY_POINT, INFINITY)

#define NULL_POINT TPoint(-111,-111)

#define NULL_MYPOINT MyPoint(NULL_POINT, -1)

#define NULL_MYRECT MyRect(NULL_POINT, NULL_POINT)

#define NULL_LOCUS TLocus(NULL_POINT, NULL_POINT, 0)

using namespace std;

//---------------------------------------------------------------------------

bool operator == (const TPoint& point1, const TPoint& point2) {

return (point1.x == point2.x && point1.y == point2.y);

}

bool operator != (const TPoint& point1, const TPoint& point2) {

return (point1.x != point2.x || point1.y != point2.y);

}

//---------------------------------------------------------------------------

struct MyPoint {

MyPoint(const TPoint& pntPoint = NULL_POINT, int iNumber = -1) : point(pntPoint), number(iNumber) {}

int number;

TPoint point;

bool operator ==(const MyPoint& point1) const {

return (point == point1.point && number == point1.number);

}

bool operator !=(const MyPoint& point1) const {

return (!(*this == point1));

}

};

/*

* Comparing structure for bynary search

* i - template parameter for compare points in stl containers

* 1 - compare x coordinates (x-sorted lists, vector, etc)

* 2 - compare y coordinates (y-sorted)

* 3 - compare numbers of points (number-sorted)

* 4 - compare x,y coordinates (x-and-y-sorted)

* 5 - compare y,y coordinates (y-and-x-sorted)

*

*/

template <int i> struct less_my_point {

int less_type;

less_my_point() : less_type(i) {}

bool operator() (const MyPoint* point1, const MyPoint* point2) const {

int rslt = 0;

switch (less_type) {

case 1:

if (point1->point.x < point2->point.x) rslt = true;

break;

case 2:

if (point1->point.y < point2->point.y) rslt = true;

break;

case 3:

if (point1->number < point2->number) rslt = true;

break;

case 4:

if (point1->point.x < point2->point.x) rslt = true; else

if (point1->point.x == point2->point.x && point1->point.y < point2->point.y) rslt = true;

break;

case 5:

if (point1->point.y < point2->point.y) rslt = true; else

if (point1->point.y == point2->point.y && point1->point.x < point2->point.x) rslt = true;

break;

default:

throw "Parameter is incorrect.";

}

return rslt;

}

};

//---------------------------------------------------------------------------

struct MyRect {

MyRect(const TPoint& point1 = NULL_POINT, const TPoint& point2 = NULL_POINT) {

rect.left = point1.x;

rect.top = point2.y;

rect.right = point2.x;

rect.bottom = point1.y;

}

MyRect(int left, int top, int right, int bottom) {

rect.left = left;

rect.top = top;

rect.right = right;

rect.bottom = bottom;

}

const RECT& getRect() { return rect; }

RECT rect;

bool operator ==(const MyRect& rect1) const {

return (rect.left == rect1.rect.left

&& rect.right == rect1.rect.right

&& rect.top == rect1.rect.top

&& rect.bottom == rect1.rect.bottom);

}

bool operator !=(const MyRect& rect1) const {

return (!(*this == rect1));

}

};

//---------------------------------------------------------------------------

typedef list<MyPoint*>::const_iterator TPointListConstIterator;

class TPointList {

public:

TPointList() : _elemCount(0) {}

MyPoint addPoint(const TPoint&);

void deletePoint(const MyPoint&);

void deletePoint(int);

void deletePoints();

MyPoint movePoint(const MyPoint&, TPoint);

MyPoint getPoint(int);

int getPointCount() const;

MyPoint getPointInArea(const TPoint&, int);

TPointListConstIterator begin();

TPointListConstIterator end();

void clear();

protected:

typedef list<MyPoint*> TObjectList;

typedef list<MyPoint*>::iterator TObjectListIterator;

TObjectList _array_points;

TObjectList _array_x_sorted;

TObjectList _array_y_sorted;

private:

MyPoint addPoint(const TPoint&, int);

int _elemCount;

};

//---------------------------------------------------------------------------

struct TLocus : public MyRect {

TLocus( const TPoint& point1=NULL_POINT, const TPoint& point2=NULL_POINT, int dom=0) :

MyRect(point1,point2), domination(dom) {}

TLocus( int left, int top, int right, int bottom, int dom=0) :

MyRect(left, top, right, bottom), domination(dom) {}

int domination;

};

/*

* Comparing structure for bynary search

* locuses was sorted by x,y

*

*/

struct less_locus {

bool operator() (const TLocus& locus, const TPoint& point) const {

int rslt = 0;

if (locus.rect.right < point.x) rslt = 1; else

if (locus.rect.left < point.x && locus.rect.bottom < point.y) rslt = 1;

return rslt;

}

};

//---------------------------------------------------------------------------

//---------------------------------------------------------------------------

typedef void (__closure *TTraceFunc) (const TLocus&);

class TRegionalSearch : public TPointList {

typedef vector<TLocus> TObjectList;

typedef vector<TLocus>::iterator TObjectListIterator;

public:

TRegionalSearch() : TPointList(), pointInfinity(INFINITY_MYPOINT) {}

TTraceFunc tracerFunc;

MyPoint addPoint(const TPoint&);

void deletePoint(const MyPoint&);

MyPoint movePoint(const MyPoint&, TPoint);

void clear();

int getPointCountInRect(const MyRect&, TLocus&, TLocus&, TLocus&, TLocus&);

public:

TLocus preprocessing();

TLocus preprocessingStep(int);

private:

TPointList::TObjectListIterator ix, iy;

struct preprocessingSearchStruct {

TPoint pred_x, pred_y;

TLocus locus_x, locus_y;

TObjectListIterator ilocusy;

int ixpoints, iypoints;

void init() {

pred_x = TPoint(0, 0);

pred_y = TPoint(0, 0);

locus_x= NULL_LOCUS;

locus_y= NULL_LOCUS;

}

} pps;

MyPoint pointInfinity;

TObjectList _locus_list;

int isModified;

};

//---------------------------------------------------------------------------

int getZoomCoord(int coord, float zoom) {

float rslt = float(coord) * zoom;

return rslt;

}

int getRealCoord(int coord, float zoom) {

float rslt = float(coord) / zoom;

return rslt;

}

#endif

//---------------------------------------------------------------------------

#include <vcl.h>

#include <stdlib.h>

#pragma hdrstop

#include "Unit1.h"

/*

* TPointList

*/

MyPoint TPointList::addPoint(const TPoint& point, int number)

{

MyPoint *myPoint = new MyPoint(point, number);

TObjectListIterator result, upper_result, lower_result;

result = upper_bound(_array_points.begin(), _array_points.end(), myPoint, less_my_point<3>());

_array_points.insert(result, myPoint);

result = upper_bound(_array_x_sorted.begin(), _array_x_sorted.end(), myPoint, less_my_point<4>());

_array_x_sorted.insert(result, myPoint);

result = upper_bound(_array_y_sorted.begin(), _array_y_sorted.end(), myPoint, less_my_point<5>());

_array_y_sorted.insert(result, myPoint);

return *myPoint;

}

//---------------------------------------------------------------------------

MyPoint TPointList::addPoint(const TPoint& point)

{

return addPoint(point, ++_elemCount);

}

//---------------------------------------------------------------------------

void TPointList::deletePoint(const MyPoint& point)

{

MyPoint *listPoint;

int number;

TObjectListIterator result;

result = lower_bound(_array_x_sorted.begin(), _array_x_sorted.end(), &point, less_my_point<4>());

_array_x_sorted.erase(result);

result = lower_bound(_array_y_sorted.begin(), _array_y_sorted.end(), &point, less_my_point<5>());

_array_y_sorted.erase(result);

result = lower_bound(_array_points.begin(), _array_points.end(), &point, less_my_point<3>());

listPoint = *result;

_array_points.erase(result);

delete listPoint;

}

//---------------------------------------------------------------------------

void TPointList::deletePoint(int number)

{

// TODO

}

//---------------------------------------------------------------------------

void TPointList::deletePoints()

{

_array_x_sorted.clear();

_array_y_sorted.clear();

for (TObjectListIterator ii = _array_points.begin(); ii != _array_points.end(); ++ii) {

delete (*ii);

}

_array_points.clear();

}

//---------------------------------------------------------------------------

MyPoint TPointList::movePoint(const MyPoint& point, TPoint position)

{

TObjectListIterator result;

result = lower_bound(_array_x_sorted.begin(), _array_x_sorted.end(), &MyPoint(position), less_my_point<4>());

if (result != _array_x_sorted.end() && (*result)->point == position) {

return point;

}

deletePoint(point);

return addPoint(position, point.number);

}

//---------------------------------------------------------------------------

int TPointList::getPointCount() const

{

return _array_points.size();

}

//---------------------------------------------------------------------------

MyPoint TPointList::getPointInArea(const TPoint& point, int radius)

{

MyPoint rsltPoint = NULL_MYPOINT;

MyPoint myPoint(TPoint(point.x - radius + 1, point.y));

TObjectListIterator result;

result = upper_bound(_array_x_sorted.begin(), _array_x_sorted.end(), &myPoint, less_my_point<1>());

while (result != _array_x_sorted.end() && (*result)->point.x <= point.x + radius - 1) {

int r = sqrt( pow((*result)->point.x - point.x, 2) + pow((*result)->point.y - point.y, 2));

if (r <= radius) {

rsltPoint = *(*result);

break;

}

++result;

}

return rsltPoint;

}

//---------------------------------------------------------------------------

MyPoint TPointList::getPoint(int number)

{

MyPoint rsltPoint = NULL_MYPOINT;

MyPoint myPoint(NULL_POINT, number);

TObjectListIterator result;

result = lower_bound(_array_points.begin(), _array_points.end(), &myPoint, less_my_point<3>());

if (result != _array_points.end()) rsltPoint = *(*result);

return rsltPoint;

}

//---------------------------------------------------------------------------

TPointListConstIterator TPointList::begin()

{

return _array_points.begin();

}

//---------------------------------------------------------------------------

TPointListConstIterator TPointList::end()

{

return _array_points.end();

}

//---------------------------------------------------------------------------

void TPointList::clear()

{

for (TObjectListIterator ii = _array_points.begin(); ii != _array_points.end(); ++ii)

delete *ii;

_array_points.clear();

_array_x_sorted.clear();

_array_y_sorted.clear();

_elemCount = 0;

}

//---------------------------------------------------------------------------

//---------------------------------------------------------------------------

//---------------------------------------------------------------------------

TLocus TRegionalSearch::preprocessing()

{

TLocus locus = preprocessingStep(1);

while (locus != NULL_LOCUS)

locus = preprocessingStep(0);

return locus;

}

//---------------------------------------------------------------------------

TLocus TRegionalSearch::preprocessingStep(int isStart)

{

TLocus locus;

int flag = 0;

if (isStart) {

_locus_list.clear();

pps.init();

if (*_array_x_sorted.back() != INFINITY_MYPOINT) _array_x_sorted.push_back(&pointInfinity);

if (*_array_y_sorted.back() != INFINITY_MYPOINT) _array_y_sorted.push_back(&pointInfinity);

isModified = 1;

ix = _array_x_sorted.begin();

iy = _array_y_sorted.begin();

}

if (iy == _array_y_sorted.end()) {

if (!pps.pred_x.x) {

pps.ilocusy = _locus_list.begin();

pps.locus_y = *pps.ilocusy;

}

pps.pred_x = (*ix)->point;

++ix;

if (ix == _array_x_sorted.end())

{

_array_x_sorted.pop_back();

_array_y_sorted.pop_back();

isModified = 0;

return NULL_LOCUS;

}

pps.locus_x = NULL_LOCUS;

if (pps.pred_x.x == (*ix)->point.x)

return preprocessingStep(0);

else

pps.ixpoints++;

iy = _array_y_sorted.begin();

pps.pred_y = TPoint(0,0);

}

if (pps.pred_y.y == (*iy)->point.y) {

while (1) {

if (pps.pred_y.x == pps.pred_x.x) {

flag = 1;

}

pps.pred_y = (*iy)->point;

++iy;

if (iy == _array_y_sorted.end()) return preprocessingStep(0);

if (pps.pred_y.y < (*iy)->point.y) break;

}

}

locus.rect.left = pps.pred_x.x;

locus.rect.top = pps.pred_y.y;

locus.rect.right = (*ix)->point.x;

locus.rect.bottom= (*iy)->point.y;

int xdom = pps.locus_x.domination;

int ydom = (pps.locus_y != NULL_LOCUS) ? pps.ilocusy->domination : 0;

int xydom = 0;

if (!flag) flag = (pps.pred_y.x == pps.pred_x.x && (pps.pred_x != TPoint(0,0) && pps.pred_y != TPoint(0, 0)));

if (pps.locus_y != NULL_LOCUS) {

TObjectListIterator ii = pps.ilocusy;

if (ii != _locus_list.begin() && pps.ilocusy->rect.top)

xydom = (--ii)->domination;

}

locus.domination = xdom + ydom - xydom + flag;

_locus_list.push_back(locus);

pps.locus_x = locus;

pps.pred_y = (*iy)->point;

pps.iypoints++;

if (pps.locus_y != NULL_LOCUS) ++pps.ilocusy;

++iy;

return locus;

}

//---------------------------------------------------------------------------

int TRegionalSearch::getPointCountInRect(const MyRect& rect, TLocus& locus1, TLocus& locus2, TLocus& locus3, TLocus& locus4)

{

int rslt = -1;

if (isModified) preprocessing();

TPoint point1(rect.rect.right, rect.rect.bottom);

TPoint point2(rect.rect.left, rect.rect.bottom);

TPoint point3(rect.rect.left, rect.rect.top);

TPoint point4(rect.rect.right, rect.rect.top);

TObjectListIterator result1 = lower_bound(_locus_list.begin(), _locus_list.end(), point1, less_locus());

TObjectListIterator result2 = lower_bound(_locus_list.begin(), _locus_list.end(), point2, less_locus());

TObjectListIterator result3 = lower_bound(_locus_list.begin(), _locus_list.end(), point3, less_locus());

TObjectListIterator result4 = lower_bound(_locus_list.begin(), _locus_list.end(), point4, less_locus());

if (result1 != _locus_list.end() && result2 != _locus_list.end() && result3 != _locus_list.end() && result4 != _locus_list.end()) {

locus1 = *result1;

locus2 = *result2;

locus3 = *result3;

locus4 = *result4;

rslt = locus1.domination - locus2.domination - locus4.domination + locus3.domination;

}

else {

locus1 = NULL_LOCUS;

locus2 = NULL_LOCUS;

locus3 = NULL_LOCUS;

locus4 = NULL_LOCUS;

}

return rslt;

}

//---------------------------------------------------------------------------

void TRegionalSearch::clear()

{

TPointList::clear();

_locus_list.clear();

}

//---------------------------------------------------------------------------

MyPoint TRegionalSearch::addPoint(const TPoint& point)

{

isModified = 1;

return TPointList::addPoint(point);

}

//---------------------------------------------------------------------------

void TRegionalSearch::deletePoint(const MyPoint& point)

{

isModified = 1;

TPointList::deletePoint(point);

}

//---------------------------------------------------------------------------

MyPoint TRegionalSearch::movePoint(const MyPoint& point, TPoint newpoint)

{

isModified = 1;

return TPointList::movePoint(point, newpoint);

}

//---------------------------------------------------------------------------

//---------------------------------------------------------------------------

//---------------------------------------------------------------------------

//---------------------------------------------------------------------------