Программирование - это просто
Advertisement
Главная arrow Математика и информатика arrow Теория алгоритмов для чайников. arrow Теория алгоритмов для чайников. Урок 4. Трудоемкость алгоритмов и временные оценки
21.10.2017 г.
Главное меню
Главная
Системный подход
Интернет магазин
Биржевые роботы
Программные продукты
Математика и информатика
1С:Предприятие
C#, Delphi, VB, F#, Web и пр.
Искусственный интеллект
Услуги
Ча. Во. (FAQ)
Платный раздел
Наука для чайников
Разное
Размышления
Карта сайта
Друзья сайта
Excel-это не сложно
Все о финансах
Теория алгоритмов для чайников. Урок 4. Трудоемкость алгоритмов и временные оценки Печать E-mail
Автор megabax   
25.05.2017 г.
New Page 1

Теория алгоритмов для чайников. Урок 4. Трудоемкость алгоритмов и временные оценки

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

  • Простое присваивание.

  • Доступ по индексу.

  • Арифметические операции.

  • Операция сравнения.

  • Логическая операция.

Анализ трудоемкости алгоритма делается по разному для различных конструкций. Разберем их.

Конструкция следования. Это просто шаг алгоритма, его трудоемкость определяется трудоемкостью все операций на этом шаге. Например, если надо сосчитать 2+2 и присвоить результат какой-то переменной, то тут будут две операции: "сложение" и "присваивание".

Конструкция ветвления. Тут немножко посложнее, чем с конструкцией следования, так как не всегда сразу понятно, по какой ветке пойдет программа. Более того, в разных ситуациях программа может идти по разным веткам. Поэтому для вычисления трудоемкости алгоритма ветвления вычисляют вероятность того, что программа пойдет по той или иной ветке, и суммируют трудоемкость всех веток, умноженную  на вероятность того, что программа пойдет по этой ветке. Например, пусть у нас проверяется условие равенства некой переменной числу 3. Допустим, мы знаем, что эта переменная может равновероятно принимать значения от 1 до 10. Значит, вероятность того, что условие выполниться 10%, а что не выполниться 90%. Правда, не всегда бывает так просто определить вероятность. Рассмотрим, например, такую ситуацию: программа запрашивает возраст пользователя. Если введенное значение меньше 18, то она работает в одном режиме, если больше или равно то в другом режиме. Здесь для определения вероятности необходимо иметь какую-то статистику, какие значения вводят пользователи (а не какой их возраст на самом деле, так как они могут и обмануть программу).

Конструкция цикла. Для определения трудоемкости цикла необходимо трудоемкость одной итерации цикла умножить на количество повторений.

Теперь рассмотрим ряд примеров.

Пример 1. Суммирование элементов квадратной матрицы. Опишем данную программу на некотором бэйсикоподобном псевдоязыке:

SumM (A, n; Sum)
Sum <-- 0
For i <-- 1 to n
For j <-- 1 to n
Sum <-- Sum + A[i,j]
Next j

Next i
Return (Sum)
End

Итак, что у нас в этой программе: две конструкции следования (присвоение Sum <-- 0 и Return (Sum)), а также вложенный цикл. В теле цикла у нас операция присваивания и сложения. Таким образом, трудоемкость программы будет 2+2n2. Здесь n - это размер матрицы. Как видим, трудоемкость данного алгоритма  пропорционально квадрату размера матрицы. То есть, если мы увеличим матрицу в два раза, то скорость работы нашего алгоритма замедлиться практически в 4 раза (на самом деле чуть меньше из-за того, что прибавляем 2, но при больших n этим можно пренебречь).

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

Пример 2. Задача поиска максимума в массиве. Псевдокод данного алгоритма выглядит вот так:

MaxS (S,n; Max)
Max <-- S[1]
For i <-- 2 to n
if Max < S[i]
then Max <-- S[i]
Next i
return Max
End

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

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

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

Средний случай. Алгоритм поиска максимума последовательно перебирает элементы массива, сравнивая текущий элемент массива с текущим значением максимума. На очередном шаге, когда просматривается k-ый элемент массива, переприсваивание максимума произойдет, если в подмассиве из первых k элементов максимальным элементом является последний. Очевидно, что в случае равномерного распределения исходных данных, вероятность того, что максимальный из k элементов расположен в определенной (последней) позиции равна 1/k. Тогда в массиве из n элементов общее количество операций переприсваивания максимума определяется как:

Теория алгоритмов для чайников. Урок 4. Трудоемкость алгоритмов и временные оценки

(4.1)

Где Hn - это так называемое n-ое гармоническое число.

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

На пути построения временных оценок мы сталкиваемся с целым набором различных проблем, пофакторный учет которых вызывает существенные трудности. Укажем основные из этих проблем:

  • неадекватность формальной системы записи алгоритма и реальной системы команд процессора;

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

  • различные времена выполнения реальных машинных команд;

  • различие во времени выполнения одной команды, в зависимости от значений операндов

  • различные времена реального выполнения однородных команд в зависимости от типов данных;

  • неоднозначности компиляции исходного текста, обусловленные как самим компилятором, так и его настройками.

Существуют различные различные способы решения проблемы временных оценок работы алгоритма. Рассмотрим их:

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

Метод Гиббсона. Метод предполагает проведение совокупного анализа по трудоемкости и переход к временным оценкам на основе принадлежности решаемой задачи к одному из следующих классов:

  • задачи научно-технического характера с преобладанием операций с операндами действительного типа;

  • задачи дискретной математики с преобладанием операций с операндами целого типа;

  • задачи баз данных с преобладанием операций с операндами строкового типа.

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

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

Теория алгоритмов для чайников. Урок 4. Трудоемкость алгоритмов и временные оценки

(4.2)

Где Теория алгоритмов для чайников. Урок 4. Трудоемкость алгоритмов и временные оценки - время время выполнения элементарной операции,

Теория алгоритмов для чайников. Урок 4. Трудоемкость алгоритмов и временные оценки - время выполнения элементарной операции, полученной в ходе эксперимента,

Теория алгоритмов для чайников. Урок 4. Трудоемкость алгоритмов и временные оценки - экспериментально измеренное время работы алгоритма,

Теория алгоритмов для чайников. Урок 4. Трудоемкость алгоритмов и временные оценки- размерность входных данных, заданная при проведении эксперимента,

Теория алгоритмов для чайников. Урок 4. Трудоемкость алгоритмов и временные оценки - трудоемкость алгоритма.

 

 

Последнее обновление ( 25.05.2017 г. )
 
Пред. »
 
© 2017 Программирование - это просто
Joomla! - свободное программное обеспечение, распространяемое по лицензии GNU/GPL.
Русская локализация © 2005-2008 Joom.Ru - Русский Дом Joomla!
Design by Mamboteam.com | Powered by Mambobanner.de
Я принимаю Яндекс.Деньги
Мы принимаем
Банковские карты
Оплатите покупку в интернет-магазине банковскими картами VISA и Mastercard любого банка.
узнать больше
Электронный кошелек
Моментальная оплата покупок с помощью вашего электронного кошелька RBK Money.
узнать больше
Банковский платеж
Оплатите покупку в любом российском банке. Срок зачисления средств на счет - 3-5 рабочих дней.
узнать больше
Денежные переводы
Оплата покупок через крупнейшие системы денежных переводов CONTACT и Unistream.
узнать больше
Почтовые переводы
Оплатите покупку в любом отделении Почты России. Срок зачисления платежа - 3-4 рабочих дня.
узнать больше
Платежные терминалы
Оплата покупок в терминалах крупнейших платежных систем в любом городе России - быстро и без комиссии.
узнать больше