СЛОЖНОСТЬ АЛГОРИТМОВ

Сортировка Хоара

/// Сортировка Хоара (быстрый итеративный вариант) void InterLib::HoareSort(void * aStructSort) {

ThStructSort *ptrStructSort = (ThStructSort *) aStructSort; IntegerType Left = ptrStructSort->aFirstElem;

IntegerType Right = ptrStructSort->aLastElem; IntegerType L2, R2;

NumericalType PivotValue; std::stack<NumericalType> Lows; std::stack<NumericalType> Highs; Lows.push(Left); Highs.push(Right);

while (!Lows.empty()) { Left = Lows.top(); Lows.pop();

Right = Highs.top(); Highs.pop();

L2 = Left;

R2 = Right;

PivotValue = ptrStructSort->TContainerX[0][(Left + Right) / 2];

do {while (ptrStructSort->TContainerX[0][L2] < PivotValue) ++L2; /// T(log n)

while (ptrStructSort->TContainerX[0][R2] > PivotValue) --R2; /// T(log n)

if (L2 <= R2) {

if (ptrStructSort->TContainerX[0][L2]

> ptrStructSort->TContainerX[0][R2])

{

NumericalType Temp = ptrStructSort->TContainerX[0][L2]; ptrStructSort->TContainerX[0][L2]

= ptrStructSort->TContainerX[0][R2]; ptrStructSort->TContainerX[0][R2] = Temp; Temp = ptrStructSort->TContainerY[0][L2]; ptrStructSort->TContainerY[0][L2]

= ptrStructSort->TContainerY[0][R2]; ptrStructSort->TContainerY[0][R2] = Temp;

}

++L2;

if (R2 > 0) --R2;

}

} while (L2 <= R2); /// T(n) if (L2 < Right) { /// O(log n)

Lows.push(L2);

Highs.push(Right);

}

if (R2 > Left) { /// O(log n) Lows.push(Left); Highs.push(R2);

}

}

}

		Временная сложность	) = log2
Худший случай:		( ) = max(log2 2,.log2
	( ) = max( , log2 ) =			.
Лучший и средний случаи:

(Случай уже отсортированного массива.)

47

( ) = Пространственная2 log2 сложность

Общий случай: .

Функция интерполяции одной точки методом Лагранжа

/// Интерполяция Лагранжа

InterLib::NumericalType InterLib::LagrangeInterpolation( ContainerType & TContainerX, /// Контейнер X ContainerType & TContainerY, /// Контейнер Y NumericalType ntX, /// Координата X

IntegerType nStart, /// Стартовый индекс интерполяции IntegerType nStop) /// Конечный индекс интерполяции

{

IntegerType i, j;

NumericalType ntProduct, ntResult = 0;

for (i = nStart; i < nStop; i++) { /// T(n)

ntProduct = 1;

for (j = nStart; j < nStop; j++) { /// T(n) if (j != i) {

ntProduct *= (ntX - TContainerX[j])

/ (TContainerX[i] - TContainerX[j]);

}

}

ntResult += ntProduct * TContainerY[i];

}

return ntResult;

}

Общий = −

Временная сложность

2

В случае

( ) = =

Пусть

(степень интерполяции).

случай:

.

интерполяции отрезка сложность

возрастает в

раз,

где

—

количество точек интерполяции.

В алгоритме

( ) = 1

:

Общий случай:

Пространственная сложность

.

интерполяции реализованы следующие формулы8

точек с одинаковой X координатой (

по

=

означает наличие двух

Знаменатель

заведомо не равен нулю, так как

дубликатов по

X

условию), а функция удаления

исключает. Таким образом,

деления

на 0

не

возникнет.

этот случай

≠

8 Источник: https://ru.wikipedia.org/wiki/Интерполяционный_многочлен_Лагранжа

48

Функция удаления дубликатов по X координате

///Функция удаления дубликатов

///Принимает указатель на ThStructRemoveDuplicates void FuncLib::RemoveDuplicates(void * aStructRD) {

ThStructRemoveDuplicates *ptrStructRD = (ThStructRemoveDuplicates *) aStructRD;

IntegerType i, nAmountOfPoints = ptrStructRD->TContainerX->size(); NumericalType PrevElem;

/// Цикл, выполняющий основную работу

for (i = 1; i < nAmountOfPoints; ++i) { /// T(n)

/// Если найдены две одинаковые X координаты, то…

if (ptrStructRD->TContainerX[0][i-1] == ptrStructRD->TContainerX[0][i])

{

/// Если их соответствующие Y координаты не равны друг другу, то… if (ptrStructRD->TContainerY[0][i-1] != ptrStructRD-

>TContainerY[0][i]) {

/// Удаление второй точки

PrevElem = ptrStructRD->TContainerX[0][i - 1];

/// И всех последующих

while (i < nAmountOfPoints && PrevElem == ptrStructRD- >TContainerX[0][i]) { /// T(n-3)

/// erase удаляет элемент контейнера (X) ptrStructRD->TContainerX->erase(ptrStructRD->TContainerX-

>begin() + i);

/// erase удаляет элемент контейнера (Y) ptrStructRD->TContainerY->erase(ptrStructRD->TContainerY-

>begin() + i);

--nAmountOfPoints; /// Число данных уменьшается

}

}

///Удаление первой точки

///(помимо верхнего условия, этот этап выполняется, если Y

координаты равны друг другу) ptrStructRD->TContainerX->erase(ptrStructRD->TContainerX->begin() +

i - 1);

ptrStructRD->TContainerY->erase(ptrStructRD->TContainerY->begin() +

i - 1);

--i; /// Счетчик уменьшается --nAmountOfPoints; /// Число данных уменьшается

}

}

}

Общий случаи:

T(n) =n2 Временная сложность

O(n)=nПространственная сложность Общий случай: .

Этот алгоритм нужно улучшить

Если координаты X равны, то:

1.Если их соответствующие Y координаты не равны, то все такие точки (с этой координатой X) удаляются.

2.Если их соответствующие Y координаты равны, то остается только одна точка (с этой координатой X).

49