4394

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

Контрольная

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

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

Русский

2012-11-18

169.5 KB

12 чел.

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

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

Рассмотрим следующий пример. Предположим, что имеется последовательность пар целых чисел, в которой каждое целое число представляет объект некоторого типа, а пара 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


 

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

80531. Національно-культурне відродження 1920-1930-х рр. Українська культура періоду тоталітаризму (1933 – 1953 рр.) 28.11 KB
  Коренізація була викликана прагненням більшовиків заручитися підтримкою місцевого (корінного) населення з тим, щоб зміцнити свою соціальну базу. У середині 20-х рр. 80% населення республіки складали українці, а 20% – представники інших національностей.
80532. Українська культура початку ХХ ст. (1900 – 1921 рр.) 547 KB
  Української наукової громадськості було надано сім професорських місць у Львівському університеті і три професорських місця в Чернівецькому університеті. Спроби української громадськості з інших регіонів надати закарпатцям допомогу також припинялися угорською владою. Зростання числа грамотних українців стимулював розвиток української літератури. Коцюбинського Цвіт яблуні Intermezzo Тіні забутих предків стали класикою золотим фондом української літератури.
80534. Культура українських земель XIX ст. Національно-культурне відродження 917.5 KB
  У XIX ст. розвиток української культури обумовлювався підпорядкуванням українських земель двом імперіям – Російській та Австро-Угорській. Обидві імперії були багатонаціональними, з титульною (панівної) нацією. І Росія, і Австро-Угорщина проводили колонізаторську політику
80535. Культура українських земель ІІ пол. XIX- поч. ХХ ст 910 KB
  Криза феодального ладу в Російській імперії заглиблювалася повільно, революційна ситуація ще не дозріла. Тому діяльність частини української інтелігенції відбувалася в руслі російської культури. У Росії XIX ст. панувала думка, що український народ...
80536. Культура Київської Русі 1.59 MB
  Культура Київської Русі. В епоху Київської Русі IXXII ст. була створена яскрава і самобутня культура її основою став економічний і духовний розвиток Русі освоєння досягнень інших словянських країн і Візантії. Писемність у Київській Русі стала відомою в Х ст.
80537. ОРГАНІЗАЦІЯ ПОСЛУГ КОМУНІКАЦІЇ 49 KB
  Транспорт - це засіб пересування, за допомогою якого можна добратися до туристичного центру. Це може бути літак, теплохід, поїзд, туристичний автобус, автомобіль та ін. Значну частину витрат вартості турпакету складають витрати на перевезення. Чим більш комфортабельний і швидкісний вид транспорту використовується, тим вища вартість подорожі.
80538. ОРГАНІЗАЦІЯ ПОСЛУГ РОЗМІЩЕННЯ 174 KB
  До найбільш розповсюджених у міжнародній практиці форм управління підприємствами гостинності відносяться: управління за контрактом; управління через договір франчайзингу; оренда. В індустрії гостинності поширення й інші організаційні форми управління акціонерні товариства T спільні підприємства СП синдикати консорціуми і т. що відрізняються змістом й пропорціями функцій структурою і ступенем централізації управління. Управління за контрактом Однією з основних форм управління підприємствами індустрії гостинності що...
80539. ОРГАНІЗАЦІЯ ПОСЛУГ ХАРЧУВАННЯ 113.5 KB
  Сутність і соціальноекономічна значущість харчування у сфері туристичних послуг. Соціальнопросторова модель організації послуг харчування. Сутність і соціальноекономічна значущість харчування у сфері туристичних послуг Дядечко Л.