Теория экономических информационных систем


Теория экономических информационных систем - стр. 60


е. время создания в памяти ЭВМ так или иначе упорядоченного представления данных (упорядочение способно ускорить выполнение алгоритмов поиска данных);

• время поиска данных. Как известно, условия поиска (выборки) на практике могут быть достаточно разнообразные. Анализируется обычно простейший и наиболее распространенный случай (поиск по совпадению) – найти записи, у которых значение ключевого атрибута равно заранее известной величине q;

• время корректировки данных. Из всех возможных вариантов корректировки учитывается включение или исключение одной записи;

• объем дополнительной памяти, расходуемой под служебную информацию (например, адреса связи).

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

При анализе алгоритмов необходим еще ряд допущений, обеспечивающих использование равномерного распределения вероятностей для всех случайных величин, описывающих работу алгоритма, в том числе:

• распределение значений ключевых атрибутов в массиве из М записей - равномерное;

• значение q при поиске по совпадению выбрано случайно: это означает, что поиск с одинаковой вероятностью 1/М может закончиться на любой записи массива;

• положение включаемой (исключаемой) записи при корректировке определяется теми же вероятностями, что и при поиске.

Массив, обладающий наибольшей неопределенностью своего состояния, будем называть случайным массивом. Все его М! состояний равновозможны. Через М! обозначено произведение 1*2*...*М.

Таким образом, минимальное число сравнений, необходимое для упорядочения массива из М записей, определяется как




Начало  Назад  Вперед



Книжный магазин