Сложность ниже приведенного алгоритма O(N3).


O(H)=O(1)+O(1)+O(1)=O(1);
O(I)=O(N)*(O(F)+O(J))=O(N)*O(доминанты условия)=О(N);
O(G)=O(N)*(O(C)+O(I)+O(K))=O(N)*(O(1)+O(N)+O(1))=O(N2);
O(E)=O(N)*(O(B)+O(G)+O(L))=O(N)* O(N2)= O(N3);
O(D)=O(A)+O(E)=O(1)+ O(N3)= O(N3)


10.2. Алгоритмы поиска
Будем рассматривать на примере поиска в массиве.
10.2.1. Линейный поиск
Линейный, последовательный поиск — нахождения заданного элемента в некотором массиве. Поиск значения осуществляется простым сравнением очередного значения и искомого, если значения совпадают, то поиск считается завершённым.
Если у массива длина = N, найти решение можно за N шагов.
Сложность алгоритма - O(n). В связи с малой эффективностью линейный поиск используют только если N не большое.

Алгоритм:
1. Определяем начало интервала поиска и выбираем элемент для поиска.
2. Сравниваем образец с выбранным элементом. Если элемент совпадает с образцом, то определяем его индекс и переходим к шагу 4.
3. Если элемент не совпадает с образцом, то выбираем следующий, если он есть и переходим к шагу 2.
4. Если индекс определен, то элемент найден, иначе - искомого элемента в массиве нет.
int i=0;
int x; // образец
int n; // размерность массива
int a[100];
while (i<n)&&(a[i]!=x))
i=i+1;
if (i==n) printf("no");
else printf("%d ",i);

Можно упростить логическое выражение, которое состоит из двух членов.
Уберем условие (i<n), но при этом необходимо гарантировать, что совпадение произойдет всегда. Для этого достаточно в конец массива поместить дополнительный элемент со значением x. Такой вспомога-тельный элемент называется “барьером”.
Теперь массив будет описан так:
int a[101];
a[n]=x;
while (a[i]!=x) i=i+1;

int LineSearch (int *a, int n, int x)
{
for (int i=0;i<n; i++)
if (a[i]==x)
return i;
return -1; //элемент не найден
}

10.2.2. Бинарный поиск
Или метод дихотомии или метод половинного деления.
Как обычно, за скорость взимается плата: массив должен быть упорядочен. Сам по себе этап предварительного упорядочения, или сортировки, обходится недешево, во всяком случае - дороже однократного линейного поиска.
Алгоритм:
1. Определяем середину интервала поиска.
2. Сравниваем образец с элементом, расположенным посередине. Если образец оказался больше, то областью дальнейшего поиска становится правая половина; в противном случае - левая половина интервала, но в любом случае индексный интервал уменьшается вдвое. (Если осуществить еще одну проверку, то можно установить и совпадение, после чего дальнейшие шаги не обязательны.)
3. Если остался интервал единичной длины, то переходим к заключительному шагу 4, в противном случае - к шагу 1.
4. Либо единственный элемент интервала совпадает с образцом, либо - искомого элемента в массиве нет.

int BinarySearch(int a[],
int n, int x)
{
int i, j, middle;
i=0; j=n-1;
while (i<=j)
{
middle=(i+j)/2;
if (x==a[middle])
return middle;

else
if (x>a[middle])
i=middle+1;
else
j=middle-1;
}
return -1;
}
Оценим алгоритм бинарного поиска в массиве.
Первая итерация цикла имеет дело со всем массивом. Каждая последующая итерация делит пополам размер подмассива. Так, размерами массива для алгоритма являются
n n/21 n/22 n/23 n/24 ... n/2m
В конце концов будет такое целое m, что
n/2m<2 или n<2m+1

Так как m - это первое целое, для которого n/2m<2, то должно быть верно
n/2m-1>=2 или 2m<=n
Из этого следует, что
2m<=n<2m+1
Возьмем логарифм каждой части неравенства и получим
m<=log2n=x<m+1
Значение m - это наибольшее целое, которое <=х.
Итак, O(log2n).
Упр. Читать “Оценка программ”.

 

10.3. Преобразования массивов
Переворачивание элементов массива

void Revers(int *a, int n)
// Переворачивание элементов массива
{int k;
for (int i=0;i<n/2;i++)
{
k=a[i];
a[i]=a[n-i-1];
a[n-i-1]=k;
}
}

 

void ReversP(int *a, int n)
{
int k;
for (int i=0;i<n/2;i++)
{
k=*(a+i);
*(a+i)=*(a+n-i-1);
*(a+n-i-1)=k;
}
}

void ReversL(int *a, int n)
{
for (int i=0;i<n/2;i++)
{
*(a+i)^=*(a+n-i-1);
*(a+n-i-1)^=*(a+i);
*(a+i)^=*(a+n-i-1);
}
}

Расширение и сжатие массивов
При обработке массивов можно вставлять и удалять элементы

void MoveRight(int * a, int *n, int num)
{ //сдвигает все элементы на
// одну позицию вправо до номера num

for (int i=*n; i>=(num+1); i--)
a[i]=a[i-1];

(*n)++; //увелич реальный размер массива //не путать с *n++ !!!!!
}

void MoveLeft(int *a, int *n, int num)
{//сдвигает все элементы на
// одну позицию влево c номера num

for (int i=num; i<*n-1; i++)
a[i]=a[i+1];
*n=*n-1;
}
Дублирование четных в массиве

void InsertCh(int *a, int *n)
{int i=0;
while (i<*n)
{
if (a[i]%2==0)
{ MoveRight(a, n, i+1);

//Сдвигаем и добавляем элемент
a[i+1]=a[i]; i++ ;
}
i++;
}
}

Удаление чисел равных item в массиве
void DeleteCh(int *a, int *n,int item)
{
int i=0;
while (i<*n)
{
if (a[i]==item)
MoveLeft(a, n, i);
//Сдвигаем и удаляем элемент
else
i++; }
}