Файл: Основные структуры алгоритмов: сравнительный анализ и примеры их использования.pdf

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

Рис. 1.3. Наглядное изображение нотации большого О. Функция f(n) есть O(g(n)), так как f(n)≤ cg(n) при n ≥ n₀

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

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

Утверждение. Время выполнения алгоритма аггауМах, определяющего максимальный элемент массива целых чисел, есть функция O(n).

Доказательство. Как было отмечено, максимальное число простейших операций, выполняемых алгоритмом аггауМах, равно 7n - 2. Таким образом, существует положительная константа a, которая определяется единицами измерения времени, а также применяемым при реализации, компиляции и исполнении аппаратным и программным обеспечениями, при которой время выполнения алгоритма аггауМах для размера исходных данных n равно максимально a(7n - 2) . Используя нотацию большого О для с = 7a,a n ₀= 1, можно сделать вывод, что время выполнения алгоритма аггауМах является O(n).

Рассмотрим еще несколько примеров, демонстрирующих использование нотации большого О.

Пример: 20n³+ 10n log n + 5 есть О(n³).

Доказательство: 20n³+ 10n log n + 5 < 35n³ для n≥1.

- сущности, любой многочлен (полином) a^kn^k + a^k-1+ …+0 является

О(n^k).

Пример: 2¹⁰⁰ есть O(1)

Доказательство: 2¹⁰⁰ ≤ 2¹⁰⁰ • 1 для n ≥ 1. Заметьте, что переменная n не присутствует в неравенстве, так как в данном случае рассматриваются постоянные функции.

Пример: 5 / n есть O(1/n)

Доказательство: 5 / n ≤ 5(1/n) для n ≥1 (на самом деле это убывающая функция).

- целом можно сказать, что нотация большого О используется для максимально точного описания функции. Если верно, что функция F(n)
4n³ + Зn^4/3 есть О (n⁵) или даже O (n³ log n), то более точно будет сказать, что f(n) есть O(n³). Рассмотрим следующую аналогию. Голодный путешественник долго едет по пустынной проселочной дороге и встречает местного фермера, который возвращается домой с рынка. Если путешественник спросит фермера, сколько ему нужно ехать, чтобы добраться до ближайшего места, где он может поесть, фермер может вполне правдиво ответить: «Не более 12 часов», но более точным (и полезным) будет, если он скажет: «Всего в нескольких минутах езды отсюда находится рынок».

Таким образом, даже используя нотацию большого O, следует стремиться сообщать все возможные подробности.

При анализе алгоритмов и структур данных часто применяются некоторые функции, имеющие особые названия. Например, термин «линейная функция» обозначает функции вида O(n). В табл. 3.1 представлены функции, часто используемые при анализе алгоритмов.

Нотация большого О позволяет проводить асимптотический анализ, то есть определять, что функция «меньше или равна» другой функции. Существуют типы нотаций, которые позволяют проводить асимптотические сравнения других типов: Ω- и Θ- нотации, которые асимптотически задают ограничения на функцию снизу или снизу и сверху одновременно (рис 1.4)

Рис. 1.4. Графические примеры Θ, О и Ω, обозначений; в каждой части рисунка в качестве n₀ используется минимально возможное значение, т.е. любое большее значение также сможет выполнить роль n₀

Выскажем некоторые предостережения в отношении использования асимптотических нотаций. Во-первых, следует отметить, что нотация большого О и аналогичные ей могут привести к ошибочным результатам, если «скрываемые» ими постоянные множители достаточно велики. Например, хотя функция 10¹⁰⁰n есть Θ(n), если она обозначает время выполнения алгоритма, сравниваемого с алгоритмом, время выполнения которого равно 10n log n, следует выбрать алгоритм со временем Θ(n logn), даже несмотря на то, что асимптотически время выполнения, выраженное линейной функцией, меньше. Данный выбор обусловлен тем, что постоянный множитель 10¹⁰⁰, называемый «hiding», считается верхним пределом числа атомов в наблюдаемой части вселенной. Таким образом, маловероятно, что алгоритму придется решать задачу реального мира с таким размером исходных данных. Таким образом, при использовании нотации большого О следует обращать внимание на постоянные множители и элементы низшего порядка, которые могут «скрываться» за ними.

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

Глава 3. Примеры программ

3.1 Линейные программы

Теперь, когда мы познакомились с операторами, необходимыми для составления линейной программы, рассмотрим еще один пример такой программы. Пусть дано два числа a и b − длины сторон прямоугольника. Найти площадь s и периметр p прямоугольника. На рис.6 представлена графическая схема алгоритма решения данной задачи, а программа приведена в примере pr2.

Рис. 3

program pr2 ;

var

a,b,s,p:real;

begin

writeln('Введите длины стоpон пpямоугольника:');

read(a,b);

s:=a*b;

p:=(a+b)*2;

writeln('Площадь = ',s:5:3);

writeln('Пеpиметp = ',p:5:3);

end.

В этой программе все операторы выполняются последовательно друг за другом. Выполнение программы начинается с вызова процедуры вывода writeln, которая выводит на экран подсказку "Введите длины сторон прямоугольника:", что обеспечивает удобный интерфейс с пользователем. Вызов процедуры read приводит к прерыванию программы до тех пор, пока пользователь не введет два числа. Далее вычисляются площадь и периметр прямоугольника и выводятся результаты на экран.

3.2 Программы с использованием ветвлений

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

На рис.4 приведена графическая схема алгоритма, а программа − в примере pr3.

Рис. 4

program pr3;

var

x,y:real;

begin

writeln('Введите x:');

readln(x);

if x>0

then

y:=x*x*x+3

else

y:=x*sin(x);

writeln(y);

end.

В этой программе впервые встречается условный оператор и служит для выбора формулы вычисления y в зависимости от введенного значения x.

3.3 Программы с использования циклов

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

Пусть необходимо протабулировать функцию F(x) на интервале [a,b] c шагом h (где, F(x)=x*sin(x), a<b, h>0 ) и вывести полученные значения функции и аргумента.

Протабулировать функцию – это значит вычислить значения функции F(x) на отрезке [a,b] в точках a, a+h, a+2h и т.д.

Графическая схема алгоритма приведена на рис.5, а программа – в примере pr9.

Program pr9;

var a, b, h, x, y: real;

begin

writeln('Введите a,b,h:');

read(a,b,h);

x:=a;

repeat

y:=x*sin(x);

writeln('x = ',x:5, ' y= ',y:5);

x:=x+h; {К "старому" значению х добавляется

h и результат пересылается снова в х}

until x>b;

end.

Рис. 5

В этой программе оператор цикла используется для многократного выполнения группы операторов, расположенных между словами repeat, until. Каждый раз в цикле вычисляется значение y, выводятся x и y, задается новое значение х и проверяется, не выходит ли х за пределы интервала. В результате работы этой программы будут напечатаны в два столбика значения x и y.

Заключение

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

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

Ветвление позволяет реализовывать нелинейную логику выполнения программ[1-3]. При использовании полного ветвления необходимо учитывать, что оператор, стоящий сразу после выхода из ветвления будет выполнен в любом случае. При использовании неполного ветвления необходимо учитывать, что в ветвлении явно не указывается, что будет сделано в случае, если условие не выполняется (ложно). Цикл с предусловием стоит использовать в случае, если неизвестно точное количество повторений. Цикл с постусловием стоит использовать в случае, если необходимо, чтобы цикл был выполнен хотя бы один раз. Цикл с параметром является самым компактным способом записи циклической структуры.

Список использованных источников

Ахо А., Хопкрофт Д., Ульман Д. Структуры данных и алгоритмы: пер. с англ. – М.: Вильямс, 2017.
Агальцов, В. П. Математические методы в программировании / В.П. Агальцов. - М.: Форум, 2018. - 240 c.
Абрамов, В.Г.; Трифонов, Н.П. и др. Введение в язык Паскаль; Наука, 2017. - 320 c.
Акулов О.А. Информатика: учебник / О.А. Акулов, Н.В. Медведев. – М.: Омега-П, 2017. –270 с.
Алексеев А.П. Информатика 2007 / А.П. Алексеев. – М.: СОЛОН-ПРЕСС, 2017. – 608 с.
Баженова, И.Ю. Языки программирования: Учебник для студентов учреждений высш. проф. образования / И.Ю. Баженова; Под ред. В.А. Сухомлин. — М.: ИЦ Академия, 2018. — 368 с.
Вирт Н. Алгоритмы + структуры данных = программы: пер. с англ. –М.: Мир, 2016.
Вирт Н. Алгоритмы и структуры данных: пер. с англ. – М.: Мир, 2018.
Информатика: Учебник для вузов. Стандарт третьего поколения / Макарова Н.В, Волков В.Б.-СПб.:Питер, 2017.
Томас Х. Кормен, Чарльз И. Лейзерсон, Рональд Л. Ривест, Клиффорд Штайн. Алгоритмы: построение и анализ, 3-е издание — М.: Вильямс, 2017.
Стариченко, Б.Е. Теоретические основы информатики : учебник для вузов / Б.Е.Стариченко .— 3-е изд., перераб. и доп. — М. : Горячая линия – Телеком, 2016 .— 401 с.
Дж. Макконелл, Основы современных алгоритмов, М.: «Техносфера», 2016, С. 10-11
КуМир [Электронный ресурс]. URL: https://www.niisi.ru/kumir/(Дата обращения 15.02.2019)
Лукин С.М., Турбо-Паскаль 7.0. Самоучитель для начинающих // ¶М:Диалог-МИФИ, 2018.
Епанешников, А.М.; Епанешников, В.А. Программирование в среде Turbo Pascal 7.0; М.: ДИАЛОГ-МИФИ; Издание 4-е, испр., 2018. - 367 c
Учебник по паскалю [Электронный ресурс]. URL: http://pcfu.ru/stati/programmirovanie/uchebnik-po-paskalyu-oglavlenie//(Дата обращения 15.02.2019)
Доусон М. Программируем на Python / М.Доусон,. – СПб.: Питер, 2018. – 416 с.
Лутц М. Программирование на Python/М. Лутц- том II, 4-е издание. Пер. с англ. – СПб.: Символ-Плюс, 2017. – 992 с.
Грин, Д. Математические методы анализа алгоритмов / Д. Грин, Д. Кнут. - М., 2018. – 496 c.
Кнут Д. Искусство программирования для ЭВМ. Т.3. Сортировка и поиск: пер. с англ. – М.: Вильямс, 2017.
Гудман С., Хидетниеми С. Введение в разработку и анализ алгоритмов. – М.: Мир, 2016.
Кормен Т. и др. Алгоритмы. Построение и анализ: пер. с англ. -М.: Вильямс, 2017.
Гудрич M.T., Тамассия Р. Структуры данных и алгоритмы в Java: пер. с англ. – Мн.: Новое знание, 2017.
Гасфилд Д. Строки, деревья и последовательности в алгоритмах: пер. с англ. – СПб.: Невский Диалект; БХВ-Петербург, 2016.
Седжвик Р. Фундаментальные алгоритмы на C++. Ана-лиз/Структуры данных/Сортировка/Поиск: пер. с англ. – К.: Диа-Софт, 2018.
Топп У., Форд У. Структуры данных в С++. М.: Бином", 2017.
Ключарев А. А., Матьяш В. А., Щекин С. В. Структуры и алгорит-мы обработки данных: учеб. пособие/СПбГУАП. СПб., 2017.