Внутренняя сортировка данных методом подсчета. Эффективность данного алгоритма. Привести фрагмент программы, поясняющий данный алгоритм.

Внутренняя сортировка данных методом подсчета. Эффективность данного алгоритма. Привести фрагмент программы, поясняющий данный алгоритм.

Сортировка подсчётом — алгоритм сортировки, в котором используется диапазон чисел сортируемого массива (списка) для подсчёта совпадающих элементов.

Применение сортировки подсчётом целесообразно лишь тогда, когда сортируемые числа имеют (или их можно отобразить в) диапазон возможных значений, который достаточно мал по сравнению с сортируемым множеством, например, миллион натуральных чисел меньших 1000. Эффективность алгоритма падает, если при попадании нескольких различных элементов в одну ячейку, их надо дополнительно сортировать. Необходимость сортировки внутри ячеек лишает алгоритм смысла, так как каждый элемент придётся просматривать более одного раза..

Оценим эффективность сортировки подсчетом по количеству сравнений. Так как мы сравниваем каждый элемент с каждым элементом массива, то имеем N*N сравнений. Эффективность алгоритма C=N*N=Θ(N²), т.е. сортировка подсчетом имеет квадратичную сложность. Множитель N² свидетельствует о том, что алгоритм неэффективен при большом N , т.к. при удвоении числа элементов массива количество сравнений увеличится в 4 раза. Но он очень прост в реализации.

Независимо от отсортированности массива, количество перестановок равно длине массива N. То есть эффективность алгоритма по перестановкам имеет линейную сложность.

Число перестановок: min=0, max= N² , med= N²/2

Число сравнений: N²

Пример

К 503 087 512 061 908 170 897 275 653 426 154 509 612 677 765 703

С 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

С1 6 0 1 0 1 0 1 0 1 0 0 1 1 1 1 1

К1 сравнивается с остальными, если больше Сn, то 1, если меньше – 0, потом количество нулей вписывается в С1.

Считаем, сколько элементов меньше первого элемента массива (503), затем – сколько элементов меньше второго числа(087), и т.д. Число 503 по значению превышает только шесть чисел.и.т.д

С2 6 1 2 0 2 1 2 1 1 1 1 2 2 2 2 2

С3 6 1 6 0 3 1 3 1 2 1 1 2 3 3 3 3

С4 6 1 8 0 4 2 4 …

…

С15 6 1 8 0 15 3 14 4 10 5 2 7 9 11 13 12

Фрагментпрограммы:

For (i=0; i<n-1; i++)

For (i=i+1; j<n; j++)

{ if (k[i]>k[j]) c[i]++;

Elsec[j]++;

}

Внутренняя сортировка данных методом выбора. Эффективность данного алгоритма. Привести фрагмент программы, поясняющий данный алгоритм.

Этот метод – один из простейших, и он работает очень хорошо для небольших

файлов. Кроме того, хотя сортировка выбором является методом «грубой силы», он имееточень важное применение: поскольку каждый элемент передвигается не более чемраз, то он очень хорош для больших записей с маленькими ключами.

Идея сортировки выбором заключается в поиске максимального элемента и вставки его в конец массива. Затем длина массива уменьшается на один элемент («водворенный на свое место» исключается) и процедура повторяется снова. Алгоритм сортировки выполняется до тех пор, пока длина сортируемого массива не станет равна двум элементам.

В целом, это плохой метод, и он должен быть использован только в случаях, когда явно необходимо минимизироать количество присваиваний.

Число сравнений: N²

Число перестановок: N

Пример

Начальное состояние массива	8 23 5 65 44 33 1 6
Шаг 1	1 23 5 65 44 33 8 6
Шаг 2	1 5 23 65 44 33 8 6
Шаг 3	1 5 6 65 44 33 8 23
Шаг 4	1 5 6 8 44 33 65 23
Шаг 5	1 5 6 8 33 44 65 23
Шаг 6	1 5 6 8 23 44 65 33
Шаг 7	1 5 6 8 23 33 65 44
Шаг 8	1 5 6 8 23 33 44 65

Фрагмент программы:

For (i=n; i>1; i--)

{nmax=n

For(j=i-1; i>0; j--)

{if(k[j]>k[nmax])

Nmax=j;

}

{ktemp=k[i];

K[i]=k[nmax]

K[nmax]=ktemp;

}

}

Метод хорд

Метод основан на замене функции f(x) на каждом шаге поиска хордой, пересечение которой с осью Х дает приближение корня.

При этом в процессе поиска семейство хорд может строиться:

а) при фиксированном левом конце хорд, т.е. z=a, тогда начальная точка х₀=b (рис. 4.10а);

б) при фиксированном правом конце хорд, т.е. z=b, тогда начальная точка х₀=a (рис. 4.10б);

Рис. 4.10.

В результате итерационный процесс схождения к корню реализуется рекуррентной формулой:

для случая а)

(4.11)

для случая б)

(4.12)

Процесс поиска продолжается до тех пор, пока не выполнится условие

(4.13)

Метод обеспечивает быструю сходимость, если f(z)f"(z) > 0, т.е. хорды фиксируются в том конце интервала [a,b], где знаки функции f(z) и ее кривизны f"(z) совпадают.

Схема алгоритма уточнения корня методом хорд

Пример программы:

double f(double x)

{

returnsqrt(fabs(cos(x)))- x;// Заменить ф-ей, корни которой мы ищем

}

// a, b - пределы хорды, epsilon - необходимая погрешность

doublefindRoot(double a,double b,double epsilon)

{

while(fabs(b - a)> epsilon)

{

a = b -(b - a)*f(b)/(f(b)- f(a));

b = a -(a - b)*f(a)/(f(a)- f(b));

}

// a - i-1, b - i-тыйчлены

return b;

}

Алгоритм

1. Задается начальное приближение x₀.

2. Пока не выполнено условие остановки, в качестве которого можно взять или (то есть погрешность в нужных пределах), вычисляют новое приближение: [1].

Достоинства метода Ньютона: Метод Ньютона - самый быстрый способ нахождения корней уравнений: обычно заданная точность достигается за 2-3 итерации. Очень быстрая сходимость по сравнению с методом половинного деления и методом простой итерации к заданной точности.

Недостаток: громоздкий алгоритм: на каждой итерации необходимо вычислять значение функции и ее первой производной.

МЕТОД НЬЮТОНА-РАФСОНА

Повышение эффективности метода за счёт использования информации о производной накладывает дополнительные ограничения на функцию. Кроме унимодальности функция должна быть непрерывной и дважды дифференцируемой.

2.5.1. Метод Ньютона-Рафсона.

Пусть - непрерывная и дважды дифференцируемая функция.

Требуется найти корень уравнения .

Зададим – начальную точку поиска. Построим линейную аппроксимацию функции в точке . Для этого разложим в ряд Тейлора в точке и отбросим все члены второго порядка и выше.

Сходимость метода зависит от выбора начальной точки и вида функции.

не сходится

Условие выхода

Условие сходимости

Достаточное условие сходимости, таково:

Это неравенство может быть переписано в виде

откуда получаем, что сходимость гарантируется, когда, во-первых,

так как (тем самым проясняется смысл выбора знака числа ), а во-вторых, когда при всех на всём рассматриваемом отрезке, окружающем корень. Это второе неравенство заведомо выполнено, если

где . Таким образом, угловой коэффициент не должен быть слишком мал по абсолютной величине: при малом угловом коэффициенте уже на первом шаге точка может выскочить из рассматриваемой окрестности корня , и сходимости итераций к корню может не быть.

Метод простых итераций

В ряде случаев весьма удобным приемом уточнения корня уравнения является метод последовательных приближений (метод итераций).

Пусть с точностью необходимо найти корень уравнения f(x)=0, принадлежащий интервалу изоляции [a,b]. Функция f(x) и ее первая производная непрерывны на этом отрезке.

Для применения этого метода исходное уравнение f(x)=0 должно быть приведено к виду

(4.2)

В качестве начального приближения 0 выбираем любую точку интервала [a,b].

Далее итерационный процесс поиска корня строится по схеме:

(4.3)

В результате итерационный процесс поиска реализуется рекуррентной формулой (4.3). Процесс поиска прекращается, как только выполняется условие

(4.4)

или число итераций превысит заданное число N.

Для того, чтобы последовательность х₁, х₂,…, х_n приближалась к искомому корню, необходимо, чтобы выполнялось условие сходимости:

(4.5)

Рис. 4.6. Геометрический смысл метода

Переходим к построению схемы алгоритма (рис. 4.7). Вычисление функции оформим в виде подпрограммы.

Рис. 4.7. Схема алгоритма уточнения корня методом итераций

Метод прямоугольников

Словесный алгоритм метода прямоугольников:

1. Весь участок [a,b] делим на n равных частей с шагом h=(b-a)/n.
2. Определяем значение y_i подынтегральной функции f(x) в каждой части деления, т.е.

1. В каждой части деления подынтегральную функцию f(x) аппроксимируем интерполяционным многочленом степени n = 0, т.е. прямой, параллельной оси OX. В результате вся подынтегральная функция на участке [a,b] аппроксимируется ломаной линией.
2. Для каждой части деления определяем площадь S_i частичного прямоугольника.
3. Суммируем эти площади. Приближенное значение интеграла I равно сумме площадей частичных прямоугольников.

Если высота каждого частичного прямоугольника равна значению подынтегральной функции в левых концах каждого шага, то метод называется методом левых прямоугольников (рис.12.3). Тогда квадратурная формула имеет вид

Рис. 12.3. Метод левых прямоугольников

Если высота каждого частичного прямоугольника равна значению подынтегральной функции в правых концах каждого шага, то метод называется методом правых прямоугольников (рис.12.4). Тогда квадратурная формула имеет вид

Рис. 12.4. Метод правых прямоугольников

Точность каждого метода прямоугольников имеет порядок h.

Алгоритм вычисления интеграла построим в виде итерационного процесса поиска с автоматическим выбором шага. На каждом шаге будем уменьшать шаг в два раза, то есть увеличивать число шагов n в два раза. Выход из процесса поиска организуем по точности вычисления интеграла. Начальное число шагов n=2.Схема алгоритма методов прямоугольников представлена на рис.12.5.

Рис. 12.5. Схема алгоритма метода прямоугольников (с автоматическим выбором шага)

Условные обозначения:

a,b - концы интервала,

- заданная точность,

с=0 - метод левых прямоугольников,

с=1 - метод правых прямоугольников,

S1 - значение интеграла на предыдущем шаге,

S - значение интеграла на текущем шаге.

Пример реализации

Формула средних прямоугольников для аналитически заданной функции, написанная на С

#include <stdio.h>#include <math.h> double f(double x){//Подынтегральная функцияreturnsin(x);//Например, sin(x)} doublerectangle_integrate(double a,double b,int n,double(*f)(double)){double result, h;int i; h =(b-a)/n;//Шагсеткиresult=0.0; for(i=1; i <= n; i++){result+= f(a + h *(i -0.5));//Вычисляем в средней точке и добавляем в сумму}result*= h; return result;} int main(void){double integral;integral=rectangle_integrate(0,2,100,f);printf("The value of the integral is: %lf \n", integral);return0;}

Метод трапеций

Словесный алгоритм метода трапеций:

1. Интервал [a,b] делим на n равных частей с шагом h=(b-a)/n.
2. Вычисляем значение подынтегральной функции в каждой узловой точке

1. На каждом шаге подынтегральную функцию f(x) аппроксимируем прямой, соединяющей две соседние узловые точки. В результате вся подынтегральная функция на участке [a,b] заменяется ломаной линией проходящей через все узловые точки.
2. Вычисляем площадь каждой частичной трапеции.
3. Приближенное значение интеграла равно сумме площадей частичных трапеций, т.е.

Найдем площади S_i частичных трапеций:

Приближенное значение интеграла равно

Точность метода трапеций имеет порядок h².

Схема алгоритма метода трапеций представлена на рис.12.6.

Метод трапеций для оценки определенного интеграла. Величина определенного интеграла численно равна площади фигуры, образованной графиком функции и осью абсцисс (геометрический смысл определенного интеграла). Следовательно, найти – это значит оценить площадь фигуры, ограниченной перпендикулярами, восстановленными к графику подынтегральной функции f(x) из точек a и b, расположенных на оси аргумента x.

Для решения задачи разобьем интервал [a,b] на n одинаковых участков. Длина каждого участка будет равна h=(b-a)/n (см. рис.).

Восстановим перпендикуляры из каждой точки до пересечения с графиком функции f(x). Если заменить полученные криволинейные фрагменты графика функции отрезками прямых, то тогда приближенно площадь фигуры, а следовательно и величина определенного интеграла оценивается как площадь всех полученных трапеций. Обозначим последовательно значения подынтегральных функций на концах отрезков f₀, f₁, f₂,..., f_n и подсчитаем площадь трапеций

В общем случае формула трапеций принимает вид

где f_i – значение подынтегральной функции в точках разбиения интервала (a,b) на равные участки с шагом h; f₀, f_n – значения подынтегральной функции соответственно в точках a и b.

Остаточный член пропорционален длине интервала [a,b] и квадрату шага h

Согласно рис. и формуле остаточного члена, точность вычисления определенного интеграла повышается с уменьшением шага h (увеличением числа отрезков n).

Метод трапеций можно реализовать в виде процедуры или даже функции, поскольку результат вычисления определенного интеграла – скалярная величина. Параметрами программного модуля являются границы интервала (a и b) и число шагов разбиения на малые интервалы n. Для составления универсальной функции целесообразно предусмотреть вычисление подынтегральной функции f(x) во внешней процедуре – функции.

Метод трапеций — метод численного интегрирования функции одной переменной, заключающийся в замене на каждом элементарном отрезке подынтегральной функции на многочлен первой степени, то есть линейную функцию. Площадь под графиком функции аппроксимируется прямоугольными трапециями. Алгебраический порядок точности равен 1.

Если отрезок является элементарным и не подвергается дальнейшему разбиению, значение интеграла можно найти по формуле

Это простое применение формулы для площади трапеции — полусумма оснований, которыми в данном случае являются значения функции в крайних точках отрезка, на высоту (длину отрезка интегрирования). Погрешность аппроксимации можно оценить через максимум второй производной

Составная формула

Применение составной формулы трапеций

Если отрезок разбивается узлами интегрирования и каждом из элементарных отрезков применяется формула трапеций, суммирование даст составную формулу трапеций

Формула Котеса

Применение формулы трапеций для равномерной сетки

В случае равномерной сетки

где — шаг сетки.

Замечательные свойства

Метод трапеций быстро сходится к точному значению интеграла для периодических функций, поскольку погрешность за период аннулируется. Метод может быть получен путём вычисления среднего арифметического между результатами применения формул правых и левых прямоугольников.

Метод Симпсона

В методе Симпсона в каждой части деления подынтегральная функция аппроксимируется квадратичной параболой a₀x²+a₁x+a₂. В результате вся кривая подынтегральной функции на участке [a,b] заменяется кусочно-непрерывной линией, состоящей из отрезков квадратичных парабол. Приближенное значение интеграла I равно сумме площадей под квадратичными параболами.

Т.к. для построения квадратичной параболы необходимо иметь три точки, то каждая часть деления в методе Симпсона включает два шага, т.е.

L_k=2h.

В результате количество частей деления N2=n/2. Тогда n в методе Симпсона всегда четное число.

Определим площадь S₁ на участке [x₀, x₂] (рис.12.2).

Исходя из геометрического смысла определенного интеграла, площадь S₁ равна определенному интегралу от квадратичной параболы на участке [x₀, x₂]:

Неизвестные коэффициенты квадратичной параболы а₀ , а₁, а₂ определяем из условия прохождения параболой через три узловых точки с координатами (x₀y₀), (x₁y₁), (x₂y₂).

На основании этого условия строим систему линейных уравнений:

Решая эту систему, найдем коэффициенты параболы.

В результате имеем: ..

Для участка [x₂, x₄]: ..

:::::::::::::::::::

Для участка [x_i-1, x_i+1]: .,

где .

Суммируя все площади S₁ под квадратичными параболами, получим квадратурную формулу по методу Симпсона:

где

N2 - количество частей деления.

Точность метода Симпсона имеет порядок (h³/h⁴).

Схема алгоритма метода Симпсона представлена на рис.12.7.

Рис. 12.7. Схема алгоритма Симпсона (с автоматическим выбором шага)

Формула Симпсона (также Ньютона-Симпсона^[1]) относится к приёмам численного интегрирования. Получила название в честь британского математика Томаса Симпсона (1710—1761).

Суть приёма заключается в приближении подынтегральной функции на отрезке интерполяционным многочленом второй степени , то есть приближение графика функции на отрезке параболой. Метод Симпсона имеет порядок погрешности 4 и алгебраический порядок точности4.

Формула

Формулой Симпсона называется интеграл от интерполяционного многочлена второй степени на отрезке :

где , и — значения функции в соответствующих точках (на концах отрезка и в его середине)

Погрешность

При условии, что у функции на отрезке существует четвёртая производная, погрешность , согласно найденной Джузеппе Пеано формуле равна:

В связи с тем, что значение зачастую неизвестно, для оценки погрешности используется следующее неравенство:

Оптимизация

Применение в физике

Компьютерное моделирование играет в современной физике важную роль и метод Монте-Карло является одним из самых распространённых во многих областях от квантовой физики до физики твёрдого тела, физики плазмы и астрофизики.

Определение

Этот пример показывает интерполяционный многочлен Лагранжа для четырёх точек (-9,5), (-4,2), (-1,-2) и(7,9), а также полиномы y_i l_i(x), каждый из которых проходит через одну из выделенных точек, и принимает нулевое значение в остальных x_j

Лагранж предложил способ вычисления таких многочленов:

где базисные полиномы определяются по формуле:

обладают следующими свойствами:

§ являются многочленами степени

§

§ при

Отсюда следует, что , как линейная комбинация , может иметь степень не больше , и , Q.E.D.

Применения

Полиномы Лагранжа используются для интерполяции, а также для численного интегрирования.

Пусть для функции известны значения в некоторых точках. Тогда мы можем интерполировать эту функцию как

В частности,

Значения интегралов от не зависят от , и их можно вычислить заранее, зная последовательность .

Постановка задачи

Пусть задана функция .
Пусть заданы точки из некоторой области .
Пусть значения функции известны только в этих точках.
Точки называют узлами интерполяции.
- шаг интерполяционной сетки.
Задача интерполяции состоит в поиске такой функции из заданного класса функций, что

Метод решения задачи

Полином Лагранжа

Представим интерполяционную функцию в виде полинома

где - полиномы степели n вида:

Очевидно, что принимает значение 1 в точке и 0 в остальных узлах интерполяции. Следовательно в точке исходный полином принимает значение
Таким образом, построенный полином является интерполяционным полиномом для функции на сетке .

Полином Ньютона

Интерполяционный полином в форме Лагранжа не удобен для вычислений тем, что при увеличении числа узлов интерполяции приходится перестраивать весь полином заново.
Перепишем полином Лагранжа в другом виде:

где - полиномы Лагранжа степени i ≤ n.
Пусть
. Этот полином имеет степень i и обращается в нуль при .
Поэтому он представим в виде:
, где - коэффициент при . Так как не входит в , то совпадает с коэффициентом при в полиноме . Таким образом из определения получаем:

где

Препишем формулу в виде

Рекуррентно выражая пролучам окончательную формулу для полинома:

Такое представление полинома удобно для вычисления, потому что увеличение числа узлов на единицу требует добавления только одного слагаемого.

Выбор узлов интерполяции

Так как от выбора узлов завист точность интерполяции, то возникает вопрос о том, как их выбирать. С помощью выбора узлов можно минимизировать значение в оценке погрешности. Эта задача решается с помощью многочлена Чебышева [1]:

В качестве узлов следут взять корни этого многочлена, то есть точки:

Пример

В качастве примера рассмотрим интерполяцию синуса. Возьмем равномерную решетку x = [-3,-1.5,0,1.5,3];
Интерполяция полиномом Лагранжа:

Ошибка(максимальное отклонение от sin(x) на отрезке):0.1423
Интерполяция полиномом Ньютона:
Ошибка:
Возьмем решетку x с узлами в корнях полинома Чебышева= [-2.8531,-1.7632,0,1.7634,2.8532];
Интерполяция полиномом Лагранжа:

Ошибка: 0.0944
Интерполяция полиномом Ньютона:
Ошибка:

Введение

Изложение метода

Интерполяция кубическими сплайнами является частным случаем кусочно-полиномиальной интерполцией. В этом специальном случае между любыми двумя соседними узлами функция интерполируется кубическим полиномом.его коэффициенты на каждом интервале определяются из условий сопряжения в узлах:

Кроме того, на границе при и ставятся условия

( 2 )

Будем искать кубический полином в виде

( 3 )

Из условия имеем

( 4 )

Вычислим производные:

и потребуем их непрерывности при :

( 5 )

Общее число неизвестных коэффициентов, очевидно, равно , число уравнений (4) и (5) равно . Недостающие два уравнения получаем из условия (2) при и :

Выражение из (5) , подставляя это выражение в (4) и исключая , получим

Подставив теперь выражения для и в первую формулу (5), после несложных преобразований получаем для определения разностное уравнение второго порядка

( 6 )

С краевыми условиями

( 7 )

Условие эквивалентно условию и уравнению . Разностное уравнение (6) с условиями (7) можно решить методом прогонки, представив в виде системы линейных алгебраических уравнений вида , где вектор соответствует вектору , вектор поэлементно равен правой части уравнения (6), а матрица имеет следующий вид:

где и .

Метод прогонки

Метод прогонки, основан на предположении, что искомые неизвестные связаны рекуррентным соотношением:

( 8 )

Используя это соотношение, выразим и через и подставим в i-e уравнение:

,

где - правая часть i-го уравнения. Это соотношение будет выполняться независимо от решения, если потребовать

Отсюда следует:

Внутренняя сортировка данных методом подсчета. Эффективность данного алгоритма. Привести фрагмент программы, поясняющий данный алгоритм.

Сортировка подсчётом — алгоритм сортировки, в котором используется диапазон чисел сортируемого массива (списка) для подсчёта совпадающих элементов.

Применение сортировки подсчётом целесообразно лишь тогда, когда сортируемые числа имеют (или их можно отобразить в) диапазон возможных значений, который достаточно мал по сравнению с сортируемым множеством, например, миллион натуральных чисел меньших 1000. Эффективность алгоритма падает, если при попадании нескольких различных элементов в одну ячейку, их надо дополнительно сортировать. Необходимость сортировки внутри ячеек лишает алгоритм смысла, так как каждый элемент придётся просматривать более одного раза..

Оценим эффективность сортировки подсчетом по количеству сравнений. Так как мы сравниваем каждый элемент с каждым элементом массива, то имеем N*N сравнений. Эффективность алгоритма C=N*N=Θ(N²), т.е. сортировка подсчетом имеет квадратичную сложность. Множитель N² свидетельствует о том, что алгоритм неэффективен при большом N , т.к. при удвоении числа элементов массива количество сравнений увеличится в 4 раза. Но он очень прост в реализации.

Независимо от отсортированности массива, количество перестановок равно длине массива N. То есть эффективность алгоритма по перестановкам имеет линейную сложность.

Число перестановок: min=0, max= N² , med= N²/2

Число сравнений: N²

Пример

К 503 087 512 061 908 170 897 275 653 426 154 509 612 677 765 703

С 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

С1 6 0 1 0 1 0 1 0 1 0 0 1 1 1 1 1

К1 сравнивается с остальными, если больше Сn, то 1, если меньше – 0, потом количество нулей вписывается в С1.

Считаем, сколько элементов меньше первого элемента массива (503), затем – сколько элементов меньше второго числа(087), и т.д. Число 503 по значению превышает только шесть чисел.и.т.д

С2 6 1 2 0 2 1 2 1 1 1 1 2 2 2 2 2

С3 6 1 6 0 3 1 3 1 2 1 1 2 3 3 3 3

С4 6 1 8 0 4 2 4 …

…

С15 6 1 8 0 15 3 14 4 10 5 2 7 9 11 13 12

Фрагментпрограммы:

For (i=0; i<n-1; i++)

For (i=i+1; j<n; j++)

{ if (k[i]>k[j]) c[i]++;

Elsec[j]++;

}