4394

Анализ алгоритмов на примере программы на языке С++

Контрольная

Информатика, кибернетика и программирование

Анализ алгоритмов на примере программы на языке С++ Обычно одну и ту же задачу можно решить различными способами. Среди различных алгоритмов, с помощью которых можно решить задачу, естественно выбрать один – наилучший. Обычно лучшим считается т...

Русский

2012-11-18

169.5 KB

14 чел.

Анализ алгоритмов на примере программы на языке С++

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

Рассмотрим следующий пример. Предположим, что имеется последовательность пар целых чисел, в которой каждое целое число представляет объект некоторого типа, а пара p-q интерпретируется в значении «p связано с q». Мы предполагаем, что отношение «связано с» является транзитивным: если p связано с q, а q связано с r, то p связано с r. Задача состоит в написании программы для исключения лишних пар из набора: когда программа вводит пару p-q, она должна выводить эту пару только в том случае, если просмотренные до данного момента пары не предполагают, что p связано с q. Если в соответствии с ранее рассмотренными парами следует, что p связано с q, программа должна игнорировать пару p-q и переходить ко вводу следующей пары. Пример такого процесса показан с помощью табл. 10.1. Назовем описанную выше задачу задачей связности.

При задании последовательности пар целых чисел, представляющих связь между объектами (вторая колонка таблицы), задача алгоритма связности заключается в выводе тех пар, которые обеспечивают новые связи (третья колонка). Например, пара 2-9 не должна выводиться, поскольку связь 2-3-4-9 определяется ранее указанными связями (подтверждение этого показано в последней колонке).

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

Таблица 10.1.

Связь между

объектами

Новые связи

Подтверждение ранее указанных связей

1

3-4

3-4

2

4-9

4-9

3

8-0

8-0

4

2-3

2-3

5

5-6

5-6

6

2-9

2-3-4-9

7

5-9

5-9

8

7-3

7-3

9

4-8

4-8

10

5-6

5-6

11

0-2

0-8-4-3-2

12

6-1

6-1

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

Все алгоритмы решения задачи связности используют массив целых чисел, каждое из которых соответствует отдельному объекту, для хранения информации, необходимой для реализации операций объединения и поиска (union and find).

Первый алгоритм назовем алгоритмом быстрого поиска. Ниже приведена программа на языке С++, реализующая данный алгоритм.

Листинг 10.1. Решение задачи связности методом быстрого поиска

 #include <iostream.h>

static const int N=10000;

int main()

 { int i, p, q, id[N];

  for (i=0; i<N; i++) id[i]=i;

  while (cin>>p>>q)

   { int t=id[p];

    if (t==id[q]) continue;

    for (i=0; i<N; i++)

     if (id[i]==t) id[i]=id[q];

    cout << " " << p << " " << q << endl;

   }

  char response;

  cin >> response;

  return 0;

 }

Эта программа считывает последовательность пар неотрицательных целых чисел, меньших чем N, из стандартного ввода (интерпретируя пару p-q, как «связать объект p с объектом q») и выводит пары, представляющие объекты, которые еще не связаны. Она поддерживает массив id, содержащий запись для каждого объекта и характеризующийся тем, что элементы id[p] и id[q] равны тогда и только тогда, когда объекты p и q связаны. Для простоты N определена как константа времени компиляции. Иначе можно было бы считывать ее из ввода и распределять массив id динамически.

Изменения массива при выполнении операции union показаны в табл. 10.2.

Таблица 10.2.

p-q

0 1 2 3 4 5 6 7 8 9

1

3-4

0 1 2 4 4 5 6 7 8 9

2

4-9

0 1 2 9 9 5 6 7 8 9

3

8-0

0 1 2 9 9 5 6 7 0 9

4

2-3

0 1 9 9 9 5 6 7 0 9

5

5-6

0 1 9 9 9 6 6 7 0 9

6

2-9

0 1 9 9 9 6 6 7 0 9

7

5-9

0 1 9 9 9 9 9 7 0 9

8

7-3

0 1 9 9 9 9 9 9 0 9

9

4-8

0 1 0 0 0 0 0 0 0 0

10

5-6

0 1 0 0 0 0 0 0 0 0

11

0-2

0 1 0 0 0 0 0 0 0 0

12

6-1

1 1 1 1 1 1 1 1 1 1

 Алгоритм быстрого поиска выполняет не менее MN инструкций для решения задачи связности при наличии N объектов, для которых требуется выполнение M операций объединения. На современных компьютерах можно выполнять десятки и сотни миллионов инструкций в секунду, поэтому затраты времени не заметны, если значения N и M малы, но в современных приложениях может потребоваться обработка миллиардов объектов и миллионов вводимых пар.

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

Листинг 10.2. Решение задачи связности методом быстрого объединения (но не очень быстрого поиска)

 #include <iostream.h>

static const int N=10000;

int main()

 { int i, j, p, q, id[N];

  for (i=0; i<N; i++) id[i]=i;

  while (cin>>p>>q)

   {

    for (i=p; i!=id[i]; i=id[i]);

    for (j=q; j!=id[j]; j=id[j]);

    if (i==j) continue;

    id[i]=j;

    cout << " " << p << " " << q << endl;

   }

  char response;

  cin >> response;

 

  return 0;

 }

Данная программа выполняет меньше вычислений для операции union за счет выполнения большего количества вычислений для операции find. Циклы for и последующий оператор if в этом коде определяют необходимые и достаточные условия для того, чтобы массив id для p и q был связанным. Оператор присваивания id[i]=j реализует операцию union.

В табл. 10.3 показано содержимое массива  id после обработки каждой из показанной слева пар алгоритмом быстрого поиска. При обработке пары p и q мы следуем указателям, указывающим из p, чтобы добраться до записи i, у которой id[i]= = i; затем мы следуем указателям, исходящим из q, чтобы добраться до записи j, у которой id[j]= = j; затем, если i и j различны, мы устанавливаем id[i]= id[j]. Для выполнения операции find для пары 5-8 (последняя строка) i принимает значение 56901, а jзначения 801.

Таблица 10.3.

p-q

0 1 2 3 4 5 6 7 8 9

1

3-4

0 1 2 4 4 5 6 7 8 9

2

4-9

0 1 2 4 9 5 6 7 8 9

3

8-0

0 1 2 4 9 5 6 7 0 9

4

2-3

0 1 9 4 9 5 6 7 0 9

5

5-6

0 1 9 4 9 6 6 7 0 9

6

2-9

0 1 9 4 9 6 6 7 0 9

7

5-9

0 1 9 4 9 6 9 7 0 9

8

7-3

0 1 9 4 9 6 9 9 0 9

9

4-8

0 1 9 4 9 6 9 9 0 0

10

5-6

0 1 9 4 9 6 9 9 0 0

11

0-2

0 1 9 4 9 6 9 9 0 0

12

6-1

1 1 9 4 9 6 9 9 0 0

13

5-8

1 1 9 4 9 6 9 9 0 0

На рис. 10.1. показано представление быстрого объединения в виде дерева.

Рис. 10.1. Представление быстрого объединения в виде дерева

При наличии M пар N объектов, в худшем случае, когда M>N, для решения задачи связности алгоритму быстрого объединения может потребоваться выполнения более чем MN/2 инструкций.

Можно модифицировать этот алгоритм, чтобы худшие случаи гарантированно не имели места. Вместо того чтобы произвольным образом соединять второе дерево с первым для выполнения операции union, можно отслеживать количество узлов в каждом дереве и всегда соединять меньшее дерево с большим. Это изменение требует несколько более объемного кода и наличия еще одного массива для хранения счетчиков узлов, как показано в следующей программе, но оно ведет к существенному повышению эффективности. Мы будем называть этот алгоритм алгоритмом взвешенного быстрого объединения (weighted quick-union algorithm).

Листинг 10.3. Взвешенная версия быстрого объединения

 #include <iostream.h>

 static const int N=10000;

int main()

 { int i, j, p, q, id[N], sz[N];

  for (i=0; i<N; i++)

{ id[i]=i; sz[i]=1;}

  while (cin>>p>>q)

   {

    for (i=p; i!=id[i]; i=id[i]);

    for (j=q; j!=id[j]; j=id[j]);

    if (i==j) continue;

    if (sz[i]<sz[j])

     {id[i]=j; sz[j]+=sz[i];}

    else {id[j]=i; sz[i]+=sz[j];}

    cout << " " << p << " " << q << endl;

   }

  char response;

  cin >> response;

  return 0;

 }

Эта программа – модификация алгоритма быстрого объединения, которая в служебных целях для каждого объекта, у которого id[i]= = i, поддерживает дополнительный массив sz, представляющий собой массив количества узлов в соответствующем дереве, чтобы операция union могла связывать меньшее из двух указанных деревьев с большим, тем самым предотвращая разрастание длинных путей в деревьях. Представление взвешенного быстрого объединения в виде дерева показано на рис. 10.2.

Рис. 10.2. Представление взвешенного быстрого объединения

в виде дерева

На приведенной последовательности рисунков демонстрируется результат изменения алгоритма быстрого объединения для связывания корня меньшего из двух деревьев с корнем большего из деревьев. Расстояние от каждого узла до корня его дерева не велико, поэтому операция поиска выполняется эффективно. Для определения того, связаны ли два из N объектов, алгоритму взвешенного быстрого объединения требуется отследить максимум logN указателей. Поэтому количество инструкций, которые алгоритм взвешенного быстрого объединения использует для обработки М ребер между N объектами, не превышает МlogN, умноженного на некоторую константу.

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

Таблица 10.4

N

M

Quick find

Quick union

Weighted QU

1000

6206

14

25

6

2500

20236

82

210

13

5000

41913

304

1172

46

10000

83857

1216

4577

91

25000

309802

219

50000

708701

469

100000

1545119

1071

Здесь M – количество случайных соединений, генерируемых до тех пор, пока все N объектов не оказываются связанными. Этот процесс требует значительно больше операций find, чем операций union, поэтому быстрое объединение выполняется существенно медленнее быстрого поиска. Ни быстрый поиск, ни быстрое объединение не годятся для случая, когда значение N очень велико. Время выполнения при использовании взвешенных методов явно пропорционально значению N, поскольку оно уменьшается вдвое при уменьшении N вдвое.

Большинство алгоритмов имеет главный параметр N, который значительно влияет на время их выполнения. Параметр N может быть степенью полинома, размером файла при сортировке или поиске, количеством символов в строке или некоторой другой абстрактной мерой размера рассматриваемой задачи. Чаще всего он прямо пропорционален величине обрабатываемого набора данных. Когда таких параметров существует более одного (например, М и N в алгоритмах union- find), задачу часто сводят к одному параметру, задавая его как функцию других.

Обычно алгоритмы имеют время выполнения, пропорциональное одной из следующих функций: N,  logN,  NlogN,  .


0

1

2

3

4

5

6

7

8

9

0

1

2

3

4

5

6

7

9

0

1

2

3

4

5

6

7

8

9

0

1

3

5

6

7

8

2

9

4

0

1

3

5

6

7

8

2

9

4

0

1

3

5

7

8

2

9

4

6

1

3

5

8

2

4

6

9

7

0

1

3

5

2

4

6

9

7

0

8

3

5

2

4

6

9

7

8

1

0

0

1

2

3

4

5

6

7

8

9

0

1

2

5

6

7

8

4

3

9

0

1

2

5

6

7

8

4

3

9

0

1

5

6

7

8

4

3

9

2

0

1

5

6

7

8

4

3

9

2

0

1

6

7

8

2

9

4

3

5

0

1

6

8

2

9

4

5

3

7

0

1

6

2

9

4

5

7

3

8

0

6

2

9

4

5

7

8

3

1


 

А также другие работы, которые могут Вас заинтересовать

19467. Не коммерческие юридические лица 29.5 KB
  Не коммерческие юридические лица. Некоммерческие организации могут создаваться в форме: общественных или религиозных организаций объединений некоммерческих партнерств учреждений автономных некоммерческих организаций социальных благотворительных и иных фондов...
19468. Понятие и виды обязательств 31 KB
  Понятие и виды обязательств. Обязательство это гражданское правоотношение в силу которого одно лицо должник обязано совершить в пользу другого лица кредитора определенное действие передать вещь выполнить работу либо воздержаться от определенного действия а кре...
19469. Понятие и виды юридических лиц 23.5 KB
  Понятие и виды юридических лиц. Юридическое лицо́ организация имеющая в собственности хозяйственном ведении или оперативном управлении обособленное имущество в соответствии с которым отвечают по обязательствам. Виды. Юр.Лица бывают: Коммерческие Тов...
19470. Понятие и классификация вещей 30.5 KB
  Понятие и классификация вещей Вещи объекты гражданских прав имеющие материальную осязаемую форму товара имеют следующую классификацию: недвижимые объекты перемещение которых затруднено в связи с их особой связью с землей земельные участки леса здания...
19471. Основні види архітектури ВМ 14.02 KB
  Основні види архітектури ВМ. По разрядности интерфейсов и машинных слов: 8 16 32 64 128 разрядные ряд ЭВМ имеет и иные разрядности По особенностям набора регистров формата команд и данных: CISC RISC VLIW; По количеству центральных процессоров: однопроцессорные многопроцесс
19472. Основные характеристики ЭВМ 15.34 KB
  Основные характеристики ЭВМ быстродействие. Оно часто измеряется в единицах которые называются ФЛОПС количество арифметических операций в секунду. Первые ЭВМ имели быстродействие в несколько сотен ФЛОПС современные суперЭВМ достигают скорости в несколько десят...
19473. Режим роботы компьютеров 14.84 KB
  Существует несколько режимов работы ЭВМ эти режимы имеют свои преимущества и недостатки. Монопольный режим один пользователь решает одну задачу. Это исторически первый режим работы ЭВМ. Первые машины были спроектированы только на такую работу. Этот режим отличаетс
19474. Арифметико-логічний пристрій (АЛП) 13.06 KB
  Арифметикологічний пристрій АЛП. Так називається пристрій для цілочислових операцій. Арифметичні операції такі як додавання множення і ділення а також логічні операції OR AND ASL ROL і ін. обробляються за допомогою АЛП. Ці операції складають переважну більшість програмн...