Главная  Полное построение алгоритма 

[0] [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] [11] [12] [13] [14] [15] [16] [17] [18] [19] [20] [21] [22] [23] [24] [25] [26] [27] [28] [29] [30] [31] [32] [33] [34] [35] [36] [37] [38] [39] [40] [41] [42] [43] [44] [45] [46] [47] [48] [49] [50] [51] [52] [53] [54] [55] [56] [57] [58] [59] [60] [61] [62] [63] [ 64 ] [65] [66] [67] [68] [69] [70] [71] [72] [73] [74] [75] [76] [77] [78] [79] [80] [81] [82] [83] [84] [85] [86] [87] [88] [89] [90] [91] [92] [93] [94] [95] [96] [97] [98] [99] [100] [101] [102] [103] [104] [105] [106] [107] [108] [109] [110] [111] [112] [113] [114] [115] [116] [117]

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

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

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

6. Чрезвычайно легко потерять дробные степени или логарифмические множители при экспериментальном анализе. Алгоритм порядка О(/\ 0. возможно, будет выглядеть, как алгоритм порядка 0{N-) или 0(N).

7. Не будьте слишком доверчивы к параметрам «качества аппроксимации», вычисляемым попутно аппроксимируюш,ими алгоритмами (например, библиотечными пакетами «наименьших квадратов»).

8. Не забывайте о возможности ошибки в программе. Все ваши результаты могут оказаться ложными.

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

Легче ли сравнить два алгоритма, если они решают одну и ту же задачу? Можно ли измерить относительную вычислительную сложность надежнее, чем абсолютную? Ответом на эти вопросы будет ограниченное «да» (в отличие от безусловного «да!»). Разумеется, существуют серьезные проблемы:

1. Важно устранить «мешающие параметры», запутывающие суть дела. Сюда входят различия в машинах, языках и программистах. Искушенный программист может реализовать экспоненциальный алгоритм настолько эффективно, что он может показаться лучше полиномиального алгоритма, реализованного новичком. Прямое сравнение продолжительностей прогонов окажется бессмысленным, если такие различия не устранены или иным способом не учтены в эксперименте.

2. Как выбирать набор задач, на котором будет основано сравнение? Это тот же вопрос, который возникает при обсуждении любого вида проверки. Простейший ответ состоит в том, чтобы произвести объединение всех нетривиальных задач, которые использовались при Разработке алгоритмов, и проверить эти два алгоритма раздельно. Три этом, вероятно, возникнут отдельные случаи, когда каждый



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

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

4, Абсолютная продолжительность прогона (с учетом различий в машинах) не является единственной мерой относительного качества. Важны также потребность в памяти, специфические особенности, длина программы, простота. Пользователь может найти более привлекательным алгоритм, решающий задачу за 5 секунд времени центрального процессора, по сравнению с алгоритмом, требующим 1 секунду. Почему? Возможно, из-за того, что на обучение пользованию вторым алгоритмом может потребоваться несколько часов, а на обучение пользованию первым - считанные минуты.

Этот раздел мы завершим обсуждением того, как можно было бы проверить подпрограмму PRIM (разд. 4.1) на правильность, эффективность реализации и вычислительную сложность.

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

Во-первых, структурирована ли (разумным образом) эта подпрограмма? Проверка блок-схемы (рис. 4.1.6) показывает, что это так. Во-вторых, соответствует ли блок-схема тексту программы? Можно считать, что комментарии (и блоки операторов между ними) соответствуют блокам на схеме. Здесь мы могли бы предпринять мысленную проверку, чтобы удостовериться, что логика каждого блока операторов согласуется с намеченной в блок-схеме целью. Далее выпишем список всех переменных подпрограммы, чтобы (1) убедиться, что они объявлены правильно, (2) убедиться, что им присвоены правильные начальные значения, (3) определить диапазон значений каждой переменной, (4) сосчитать число операторов, содержащих каждую из переменных, и (5) определить, какие переменные используются в качестве индексов. Это можно записать, как, например, в прилагаемой ниже таблице.

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

Для необъявленных переменных мы можем проверить, нуждаются ли они в объявлении и правильного ли они типа. Для переменных, которым не присвоены начальные значения (FROM, ТО, COST), мы



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

Имя переменной

Объявлено

Индекс

Начальное значение

Диапазон

Число операторов

EDGES

1-*(М-1)

NEXT

1 (М-1)

NUMUN

(М-1)-0

входн.

2-100

WEIGHT

0-(М-1)*10б

цикл DO

1.- NUMUN

I NUMUN

I-IOe

1 NUMUN

3

как LIGHT

LIGHT (100)

1 loe

UNCHSN(IOO)

1 -> NUMUN

VERTEX (100)

1 ->(М-I)

FROM (100)

как UNCHSN

TO (100)

как VERTEX

COST (100)

как L

С (100, 100)

входн.

I lOe

Подсчет числа операторов, в которые входит данная переменная, может оказаться полезным не только при определении диапазона значений, которые она могла бы принимать, но и для выяснения, какие операторы нужно изменить, если изменяется имя переменной. Например, имена переменных I, Jf, JK, К и L в подпрограмме PRIM почти никак не связаны с их использованием в подпрограмме. Более того, переменная I служит нескольким различным целям. Поэтому произведем изменения, перечисленные во второй таблице.

Переменная Заменяется на Число операторов

I II В цикле DO 100 4

I 13 в цикле DO 300 5

I 14 в цикле DO 400 4

J VTX 2

JK NEWCST 3

К NEW VTX 3

L LEAST 5



[0] [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] [11] [12] [13] [14] [15] [16] [17] [18] [19] [20] [21] [22] [23] [24] [25] [26] [27] [28] [29] [30] [31] [32] [33] [34] [35] [36] [37] [38] [39] [40] [41] [42] [43] [44] [45] [46] [47] [48] [49] [50] [51] [52] [53] [54] [55] [56] [57] [58] [59] [60] [61] [62] [63] [ 64 ] [65] [66] [67] [68] [69] [70] [71] [72] [73] [74] [75] [76] [77] [78] [79] [80] [81] [82] [83] [84] [85] [86] [87] [88] [89] [90] [91] [92] [93] [94] [95] [96] [97] [98] [99] [100] [101] [102] [103] [104] [105] [106] [107] [108] [109] [110] [111] [112] [113] [114] [115] [116] [117]

0.0017