Помимо проверки того, что алгоритм, реализованный школьником в качестве решения способен выдать правильный ответ задачи к при тех или иных исходных данных, при проверке решения также учитывается и время работы программы. Это не значит, то жизненно необходимо во всех без исключения задачах писать оптимальные алгоритмы (которые, зачастую могут отнять много времени на их грамотную реализацию и отладку). Это просто означает, что в некоторых отдельных задачах параметр времени может играть очень важную роль. Вполне может случиться, что на каком-нибудь олимпиадном туре вообще не будет ни одной задачи, в которой необходима оптимальность. Однако, может случиться и наоборот.
Таким образом и школьники, и преподаватели должны уметь сравнивать разные алгоритмы по их эффективности. Школьники - для того, чтобы выбрать в нужный момент наиболее подходящий способ решения задачи, преподаватели - чтобы грамотно подбирать задачи и понимать, какое решение подразумевал автор той или иной задачи, задавая именно такие ограничения по времени.
Для оценки эффективности алгоритма применяется функция сложности, обозначаемая O (читается «о большое»). На самом деле есть и другие оценки, но на этапе когда школьник только-только начинает знакомиться с различными алгоритмами они не очень нужны. Функция сложности отражает по какой закономерности будет расти время выполнения программы в зависимости от исходных данных или их количества.
В качестве примера алгоритма, время выполнения которого зависит от исходного данного - алгоритм нахождения всех натуральных делителей числа N. Очевидно, что чем больше число, тем больше шагов цикла будет необходимо сделать. Примером алгоритма, время выполнения которого зависит от количества входных данных будет поиск наибольшего числа в массиве. Чем длиннее массив, тем больше операций сравнения необходимо сделать, чтобы определить какое число является наибольшим.
Основными функциями являются:
l O(1) - такая функция сложности говорит о том, что время работы программы постоянно при любых исходных данных;
l O(N) - количество операций растет пропорционально N (здесь N может быть как параметром задачи, так и количеством элементов в массиве).
l O(log N) - количество операций растет пропорционально логарифму N (именно такой сложностью обладает, например, метод половинного деления при поиске элемента в упорядоченном массиве). При увеличении N на порядок количество операций меняется на единицу. Основание логарифма обычно не уточняется, нас интересует характер роста (быстро/медленно), а не точное значение времени.
l O(N2) - количество операций растет пропорционально квадрату N. В общем случае может быть O(Nk) в зависимости от сложности задачи.
l O(N!) - количество операций растет пропорционально факториалу N.
Здесь существует некоторое количество тонкостей, связанных с тем что не все операции выполняются за одинаковое время, поэтому при оценке временной сложности используются те операции, которые требуют наибольшего времени.
Чаще всего при описании алгоритмов приводится оценка времени их работы в чистом виде, то есть без учета операций ввода/вывода.
Пример: оценим сложность программы, вводящей с клавиатуры массив и находящей в нем наибольший элемент.
Сложим количество операций N+(N-1)+1=2N. То есть существует такая константа, что при любом N количество операций не превышает CN. Следовательно, сложность алгоритма равна O(N).
Пример: оценим сложность программы, вводящей с клавиатуры массив и находящей в нем элемент с заданным свойством (например, равный определенному значению).
Алгоритм состоит из следующих шагов:
Ввод массива (N операций ввода) поиск элемента с заданным свойством (как повезет: элемент может находиться как ближе к началу массива, так и в самом конце; если элемента не существует, то необходимо сделать все N сравнений, чтобы в этом убедиться) вывод результата.
В лучшем случае данный алгоритм потребует N+2 операции (ввод всего массива, единственное сравнение, вывод), в худшем (когда такого элемента нет - 2N+1 операцию). Если N будет большим числом, к примеру порядка 106, то единицей можно пренебречь. Следовательно, сложность алгоритма равна O(N).
Пример: определим функцию сложности алгоритма шифрования слова, длины L методом подстановки. Пусть существует таблица, в которой для каждого символа алфавита записан символ, на который его надо заменить. Обозначим количество букв алфавита S.
Алгоритм состоит из следующих шагов:
Ввод слова (одна операция) цикл по всем символам
1. для каждого символа найти его замену в таблице (если таблица не упорядочена и не обладает какими-нибудь свойствами, облегчающими поиск, то в худшем случае S операций для одного символа, если искомый элемент находится в самом конце)
2. вывод найденного символа
Конец цикла
Общее количество операций 1+(S+1)*L. В случае достаточно больших S и L единицами можно пренебречь, получится что функция сложности данного алгоритма есть O(S*L).
Пример: определим функцию сложности алгоритма перевода натурального числа N в двоичную систему счисления (без операций ввода и вывода данных).
Алгоритм состоит из следующих шагов:
Цикл, пока результат деления числа на 2 не станет равным 0
1. разделить число на 2 и запомнить остаток
2. принять результат деления за новое число
Конец цикла
Общее количество операций не превышает 1+log2N. Поэтому данный алгоритм имеет сложность O(log N).
Если программа состоит из нескольких частей с различными функциями сложности, то бо льшая функция сложности «поглотит» меньшие. Например, если делается ввод массива O(N), сортировка O(N2) и вывод упорядоченного массива за O(N), то можно сказать, что вся программа имеет сложность O(N2)
Практическое применение знаний о функиях сложности алгоритмов двояко. Во-первых, для какой-то задачи можно выбрать более оптимальный алгоритм, если о нем есть соответствующие данные в литературе. Во-вторых, зная время работы своего решения на одном наборе исходных данных, школьник может примерно прикинуть время работы этой же программы на данных, которые соответствуют максимальным ограничениям по данной задаче.
Вопросы
Данные задачи служат для самопроверки по изложенному материалу и не являются обязательными.
1. Определите функцию сложности алгоритма решения квадратного уравнения.
2. Определите фукцию сложности алгоритма рисования правильного многоугольника по заданному количеству сторон.
3. Определите функцию сложности алгоритма вставки элемента в массив на заданную позицию (со предварительным смещением всех элементов с номерами большими либо равными данному на одну позицию вправо).
4. Определите функцию сложности алгоритма сложения двух натуральных чисел в столбик (пусть A - количество цифр первого числа, B - количество цифр второго).
5. Определите функцию сложности алгоритма умножения двух натуральных чисел в столбик.
Библиотека программиста
«Если отладка - процесс удаления ошибок, то программирование должно быть процессом их внесения»
Э.Дейкстра
1.2. Зачем изучать алгоритмы? Эффективность алгоритмов
Во-первых, алгоритмы являются жизненно необходимыми составляющими для решения любых задач по различным направлениям компьютерных наук. Алгоритмы играют ключевую роль на современном этапе развития технологий. Здесь можно вспомнить такие распространенные задачи, как:
- решения математических уравнений различной сложности, нахождения произведения матриц, обратных матриц;
- нахождения оптимальных путей транспортировки товаров и людей;
- нахождения оптимальных вариантов распределения ресурсов между различными узлами (производителями, станками, работниками, процессорами и т.д.);
- нахождения в геноме последовательностей, которые совпадают;
- поиск информации в глобальной сети Интернет;
- принятия финансовых решений в электронной коммерции;
- обработка и анализ аудио и видео информации.
Этот список можно продолжать и продолжать и, собственно говоря, почти невозможно найти такую область компьютерных наук и информатики, где бы ни использовались те или иные алгоритмы.
Во-вторых, качественные и эффективные алгоритмы могут быть катализаторами прорывов в отраслях, которые являются на первый взгляд далеки от компьютерных наук (квантовая механика, экономика и финансы, теория эволюции).
И, в-третьих, изучение алгоритмов это также невероятно интересный процесс, который развивает наши математические способности и логическое мышление.
1.3. Эффективность алгоритмов
Предположим, быстродействие компьютера и объем его памяти можно увеличивать до бесконечности. Была бы тогда необходимость в изучении алгоритмов? Да, но только для того, чтобы продемонстрировать, что метод развязку имеет конечное время работы и что он дает правильный ответ. Если бы компьютеры были неограниченно быстрыми, подошел бы произвольный корректный метод решения задачи. Конечно, тогда чаще всего избирался бы метод, который легче реализовать.
Сегодня очень мощные компьютеры, но их быстродействие не является бесконечно большой, как и память. Таким образом, при исчислении - это такой же ограниченный ресурс, как и объем требуемой памяти. Этими ресурсами следует пользоваться разумно, чем и способствует применение алгоритмов, которые эффективны в плане использования ресурсов времени и памяти.
Алгоритмы, разработанные для решения одной и той же задачи, часто могут очень сильно отличаться по эффективности. Эти различия могут быть намного больше заметными, чем те, которые вызваны применением различного аппаратного и программного обеспечения.
Как отмечалось выше, в этом разделе центральную роль будет посвящено задачи сортировка. Первый алгоритм, который будет рассматриваться - сортировка включением, для своей работы требует времени, количество которого оценивается как c 1 n 2 , где n - размер входных данных (Количество элементов в последовательности для сортировки), c 1 - Некоторая постоянная. Это выражение указывает на то, как зависит время работы алгоритма от объема исходных данных. В случае сортировки включением эта зависимость является квадратичной. Второй алгоритм - сортировка слиянием - требует времени, количество которого оценивается как 2 nLog 2 n. Обычно константа сортировки включением меньше константы сортировки слиянием, то есть c12 растет быстрее с увеличением n, чем функция яLog 2 n. И для некоторого значения n = n 0 будет достигнуто такой момент, когда влияние разницы констант перестанет иметь значение и в дальнейшем функция c 2 nLog 2 n будет меньше c 1 n 2 для любых n > n 0 .
Для демонстрации этого рассмотрим два компьютера - А и Б. Компьютер А более быстрый и на нем работает алгоритм сортировки, а компьютер Б более медленный и на нем работает алгоритм сортировки методом слияния. Оба компьютера должны выполнить сортировку множества, состоит из миллиона чисел. Предположим, что компьютер А выполняет миллиард операций в секунду, а компьютер Б - лишь десять миллионов, есть А работает в 100 раз быстрее Б. Чтобы разница стала более ощутимой, допустим что код метода включения написан лучшим программистом в мире с использованием команд процессору, и для сортировки n чисел с этим алгоритмом нужно выполнить 2n 2 операций (то есть C 1 = 2). Сортировка методом слияния на компьютере Б написано программистом начинающим с использованием языка высокого уровня и полученный код требует 50nlog 2 n операций (то есть c 2 = 50). Таким образом, для сортировки миллиона чисел компьютеру А потребуется
а компьютеру Б -
Поэтому, использование кода, время работы которого растет медленнее, даже при плохом компьютере и плохом компиляторе требует на порядок меньше процессорного времени! Для сортировка 10000000 цифр преимущество сортировки слиянием становится еще более ощутимой: если сортировка включением требует для такой задачи примерно 2,3 дня, то для сортировка слиянием - меньше 20 минут. Общее правило таково: чем больше количество элементов для сортировки, тем заметнее преимущество сортировки слиянием. Приведенный выше пример демонстрирует, что алгоритмы, как и программное обеспечение компьютеру, представляют собой технологию . Общая производительность системы настолько же зависит от эффективности алгоритма, как и от мощности аппаратных средств.
Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже
Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.
HTML-версии работы пока нет.
Cкачать архив работы можно перейдя по ссылке, которая находятся ниже.
Подобные документы
Описание формальной модели алгоритма на основе рекурсивных функций. Разработка аналитической и программной модели алгоритма для распознающей машины Тьюринга. Разработка аналитической модели алгоритма с использованием нормальных алгоритмов Маркова.
курсовая работа , добавлен 07.07.2013
Понятие алгоритма и анализ теоретических оценок временной сложности алгоритмов умножения матриц. Сравнительный анализ оценки временной сложности некоторых классов алгоритмов обычным программированием и программированием с помощью технологии Open MP.
дипломная работа , добавлен 12.08.2017
Общее понятие алгоритма и меры его сложности. Временная и емкостная сложность алгоритмов. Основные методы и приемы анализа сложности. Оптимизация, связанная с выбором метода построения алгоритма и с выбором методов представления данных в программе.
реферат , добавлен 27.11.2012
Проблема улучшения качества отпечатков пальца с целью повышения эффективности работы алгоритмов биометрической аутентификации. Обзор алгоритмов обработки изображений отпечатков пальцев. Анализ алгоритма, основанного на использовании преобразования Габора.
дипломная работа , добавлен 16.07.2014
Способы организации вычислительного процесса в системах с несколькими процессорами. Разработка программы на основе алгоритмов мультипроцессорных систем при пакетной обработке задач. Вычисление основных показателей эффективности для каждого алгоритма.
курсовая работа , добавлен 21.06.2013
Оценка вычислительной сложности программы. Реализация алгоритма кодирования информации Хаффмана. Кодировка теста двоичным кодом и в дереве Хаффмана. Бинарный код символов. Символ и частота его появления в тексте. Вычисление трудоемкости алгоритма.
контрольная работа , добавлен 16.12.2012
Переход от словесной неформальной постановки к математической формулировке данной задачи. Оценка различных вариантов с целью выбора наиболее эффективных структур данных и алгоритмов обработки. Реализация алгоритмов на одном из языков программирования.
курсовая работа , добавлен 25.06.2013
Для решения одной и той же задачи можно разработать несколько разных алгоритмов. Поэтому возникает задача выбора наиболее эффективных алгоритмов. Заметим, что точная оценка эффективности алгоритмов очень сложная задача и в каждом конкретном случае требует проведения специального исследования .
Ту часть теории алгоритмов, которая занимается оценкой характеристик алгоритмов, называют метрической. Ее можно разделить на дескриптивную (качественную) и метрическую (количественную) . Первая исследует алгоритмы с точки зрения устанавливаемого ими соответствия между исходными данными и результатами. Вторая исследует алгоритмы с точки зрения сложности как самих алгоритмов, так и задаваемых ими «вычислений», т. е. процессов последовательного преобразования конструктивных объектов. Важно подчеркнуть, что сложность алгоритмов и вычислений может определяться различными способами, причём может оказаться, что при одном способе алгоритм А будет сложнее В , а при другом способе - наоборот.
Чаще всего алгоритмы оцениваются по требуемой памяти, числу выполняемых операций, времени решения или погрешности вычислений. Эти характеристики зачастую зависят от параметров (размерности) задачи и имеют нелинейный характер. Поэтому в теории алгоритмов существует направление оценки эффективности алгоритмов по асимптотическим оценкам функций: требуемой памяти, времени вычисления и т.п. При этом определяется наиболее существенный параметр функции и исследуется поведение функции при возрастании значений параметра. В ходе исследования пытаются определить, какой характер носит зависимость значений рассматриваемой характеристики алгоритма от параметра. Она может быть линейной (т.е. пропорциональной параметру n), логарифмической (т.е. пропорциональной log n), квадратичной (т.е. пропорциональной n 2) и т.д. Сравнивая асимптотические оценки алгоритмов, решающих одну и ту же задачу, можно выбрать более эффективный алгоритм. Говорят, что значение некоторого параметра T(n) имеет порядок n x , если существуют такие положительные константы k и n o , что для всех n³n o , выполняется неравенство T(n) ≤ k n x .
Предположим, что n – количество числовых данных, поступающих на вход нескольких разных алгоритмов (А 1 , А 2 , А 3 , А 4 , А 5), которые производят вычисления с одинаковой скоростью - 1000 операций в секунду, но имеют разные асимптотические оценки. В табл.1.8 показаны значения n, которые могут обработать эти алгоритмы в 1 секунду, 1 минуту и 1 час (значения округлены в меньшую сторону до целого числа). Данные табл.1.3 наглядно показывают, что производительность алгоритма (т.е. число данных, обрабатываемых в единицу времени) существенно зависит от характера функции асимптотической оценки.
Тестирование разработанных алгоритмов обычно проводится при небольших значениях параметра n. Такое тестирование позволяет получить уверенность в работоспособности алгоритма, но вовсе не гарантирует выполнение задачи при больших значениях n. Нам может просто не хватить памяти ЭВМ или времени для решения реальной задачи. Асимптотические оценки важны в том смысле, что позволяют оценить достаточность ресурсов ЭВМ для практических вычислений при известных пределах изменения параметра n.
Итак, рассмотрены различные варианты вычислительных машин от простейшей машин Тьюринга до однородной вычислительной среды. Все они могут быть использованы для решения тех задач, для которых существует алгоритм. На основе этих моделей строятся более специализированные модели вычислений, а именно: неветвящиеся арифметические программы, битовые вычисления, вычисления с двоичными векторами и деревья решений.
Алгоритмы имеют следующие характеристики:
а) сложность;
б) трудоемкость;
в) надежность, и др.
Для оценки сложности алгоритмов существует много критериев. Чаще всего нас будет интересовать порядок роста необходимых для решения задачи времени и емкости памяти при увеличении количества входных данных. Свяжем с каждой конкретной задачей некоторое число, называемое ее размером . Например, размером задачи умножения матрицы может быть наибольший размер матриц - сомножителей; размером задачи на графе может быть число ребер данного графа, и т.п.
Время, затрачиваемое алгоритмом, как функция размера задачи, называется временной сложностью этого алгоритма. Поведение этой сложности в пределе при увеличении размера задачи называется асимптотической временной сложностью . Аналогично определяются емкостная сложность и асимптотическая емкостная сложность .
Важным мотивом, побуждающим рассматривать формальные модели вычислений, является желание раскрыть вычислительную сложность различных задач с целью получить нижние оценки на время вычисления. Чтобы показать, что не существует алгоритма, выполняющего данное задание менее, чем за определенное время, необходимо точное и подчас высоко специализированное определение того, что есть алгоритм. Одним из примеров такого определения служат машины Тьюринга.
4.1.1. Машины рам и рам*
Рассмотрим две машины:
1. Машины с произвольным доступом к памяти равнодоступная адресная машина - РАМ) моделирует вычислительную машину с одним сумматором, в которой команды программы не могут изменять сами себя.
2. Модель с хранимой программой - это машина с произвольным доступом к памяти и возможностью модификаций команд (РАМ*).
Рис.2.9 Структура машин РАМ (РАМ*)
Для РАМ программа не записывается в память, поэтому программа не изменяет саму себя. Программа - последовательность помеченных команд. Имеются арифметические команды, команды ввода-вывода, команды косвенной адресации и команды разветвления. Все вычисления производятся в регистре r 0 (сумматор), который, как и любой другой регистр памяти, может хранить произвольное целое число. Каждая команда состоит из двух частей - кода операции и адреса. РАМ-команды являются подмножеством команд языка Ассемблер; это подмножество можно по желанию расширить, но при этом порядок сложности задач не изменится.
Операнд может быть одного из следующих типов:
1. =i означает само целое число i и называется литералом;
2. i - содержимое регистра i (i должно быть неотрицательным);
3. *i означает косвенную адресацию, то есть значением операнда служит содержимое регистра j ,где j - целое число, которое находится в регистре I ;если j<0, машина останавливается.
Можно определить значение программы Р с помощью двух объектов: отображения c из множества неотрицательных целых чисел в множество целых чисел и “счетчика команд”, который определяет очередную выполняемую команду. Функция c есть отображение памяти, а именно с(i)- целое число, содержащееся в регистре с номером I (содержимое регистра I ).
Вначале с(i)=0 для всех i 0 , счетчик команд установлен на первую команду в Р, а выходная лента пуста. После выполнения k -й команды из Р счетчик автоматически переходит на (k+1) -ю (то есть на очередную) команду, если k -я команда не была командой вида JUMP, HALT, JGTZ и тому подобное.
РАМ*-программа находится в регистрах памяти. Каждая РАМ*-команда занимает два последовательных регистра памяти: первый регистр содержит код операции, второй - адрес. Набор команд для РАМ* совпадает с соответствующим набором для РАМ во всем, кроме косвенной адресации, которая исключена: РАМ* может моделировать косвенную адресацию путем изменения команд в процессе выполнения программы.
