y(n) = O(y(n)), если и только если g(n) = Ω(y(n)) g(n) = W(y(n))

5.

Пусть a = y(n), b = g(n):

y(n) = O(g(n)) a ≤ b

y(n) = Ω(g(n)) a ≥ b

y(n) = Ө(g(n)) a = b

y(n) = o(g(n)) a < b

y(n) = W(g(n)) a > b

Ограниченность показателя функции роста

Пусть даны две программы, время выполнения одной O(n²), а вторая O(n³), причем при определенной комбинации компилятора ПК одна программа выполнятся за 100n², а вторая 5n³ может ли быть вторая программа предпочтительней другой? При n < 20, 5n³ < 100n². Следовательно вторая программа предпочтительней, хотя имеет асинтетику, при n < 20 первая программа становится предпочтительней. Вообще выбор определяется между программами на основе оценки трудоемкости и по возможности выбирается функция с меньшим полиномом. Чем меньше степень роста, тем больше размер задачи, которую можно решить на компьютере.

f(n) T1 = 10000 мс T2 = 100*10000 затрат в 100 раз выше

100n² 10 n2 = 100 рост размерности задачи в 10 раз

5n³ 12 n2 = 60 в 5 раз

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

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

Увеличение времени соответствует увеличению производительности ЦП (центрального процессора) от версии к версии. Однако существуют такие задачи с такими функциями роста, производительность процессов которых слабо влияет.

Практически вычислимыми, т.е. реализуемыми являются алгоритмы f(n) = n(k - степень), где k константа, полиномиальный класс. Линейные алгоритмы вид C*n, между которыми находятся задачи C*n и C*n², где n – логарифм время сортировки, C*n< n*log 2n < C*n²

Анализ программы на псевдоязыке

Реализация программы трудоемкости отличается от трудоемкости на псевдоязыке, как в большую, так и в меньшую сторону, если существует Яну (Яву), использующие аппаратные особенности процессора, что уменьшает трудоемкость выполнения программ; в тоже время на псевдоязыке могут использоваться операторы, при анализе трудоемкость принимается U(1), тогда как реализация на языке программирования будет зависеть от длины входа, т.е. от n. Поэтому при анализе программы на псевдокоде алгоритм необходимо детализировать до такого уровня, который слабо бы зависел от реализации программиста.

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

Абстрактный тип данных в списках

С математической точки зрения линейный список - это множество, состоящее из n>0 элементов или узлов X1,X2,Xn, структурные свойства которого (множества) по сути, ограничиваются лишь линейно (в математическом смысле), т.е. относительным порядком следования положения узлов, определяемыми условиями, что если n>0, X1 первый элемент последовательности.

1<k<n1, если k измениться, тогда Xk предследствует элемент Xk-1.

Реализация АТД (Абстрактный тип данных). Линейный список

Согласно определению реализация должна обеспечивать упорядоченность элементов ( упорядоченного следования одного c другим). Либо тоже самое по порядковому номер, а не в смысле возрастания или убывания. Что может быть реализовано двумя способами:

1. Последовательное распределение элементов в памяти, когда элементы располагаются физически друг за другом без пропусков, тем самым очередность следования определяется местом в памяти. Пример – массив.

2. Связанные распределение - элементы в памяти располагаются в произвольном (определенном) порядке, однако каждый элемент кроме значения имеет специальное поле. Поле - поле связи, в значение которого есть физический адрес в порядке обхода элемента. ИЗ определения следует, что и первый элемент может располагаться в произвольном порядке. Поэтому необходимо специальная ячейка, которая называется головой списка, содержащая адрес первого элемента линейного связанного списка (ЛСС).

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

информацион. поля связи

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

1. Однонаправленный линейный связанный список

Tuzel = record { неверно }

Info: anytype

Next: ^tuzel;

End;

Prev INFO Next

1. Двунаправленный список , 2 поля связи.

Tuzell = record

Info1,...., infomLanytype;

Next,prev:^tuzel { неверно }

End;

1

2

Xk-1 Xk Xk+1

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

1. Var head, tail:^tuzee;

head

1

teal

2

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

По структуре организации линейного связанного списка списки делятся на:

- концевые, в таких списках последний элемент специальным образом обозначается, а точнее обычно в поле связи записывается

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

В кольцевой структуре: в отличие от признака конца (null), в кольцевом списке признаком завершения обхода является совпадение адресов начала обхода. Одиночный обход завершается, если адрес текущего элемента совпадает с адресом начала обхода.

Сравнение последовательного и связанного распределения

Критерий	Последовательные распр.	Связанные распр.
1.Доступность к элементу.	Массив K адрес(Хк)=адрес(Х1) + К*размер(Хi) O(1) Реализует модель с произвольным доступом к элементу	ЛСС O(n) Реализует модель с последовательным доступом.
2.Расположение в памяти	Область должна быть единой , однако как правило операционная система (ОС) память выделяет по страничное, при этом размер страницы может быть меньше чем требуемый размер под страницу. Последовательность областей – таблицы дескрипторов областей, выделенных под массив. Задается под ОС, следует разделять динамический и статический массив. Статические элементы должны умещаться в 64Мб, а если нет – то создаются динамические массивы, которым доступно всё ОЗУ ОС. Доступ к элементу динамического массива на порядок медленнее доступа к статическому массиву.	Это изначально динамический список. Поэтому ему доступно всё адресное пространство ОС.
3.Добавление элемента Пусть требуется добавить новый элемент в позиции с номером k.	О(N)	Вставка заключается в трех шагах 1. Выделение памяти под новый элемент
4.Удаление элемента – аналогично	О(N)
5.Объединение или соединение.	= О(N)	Объединение ЛСС заключается в том, что вместо признака конца первого списка записывает адрес первого элемента первого списка. Казалось что доступ к последнему элементу первого списка осуществится за О(N). Однако для экономии операций, если алгоритм ориентирован на регулярное слияние, то кроме головы можно хранить и хвост а’ и в’, которые указывают на последний элемент. Тогда операция добавления элемента в конец списка будет, осуществляется O(1).

Примечание 3,4: заметим, что добавление и удаление в ЛСС осуществляется очень быстро, однако надо получить доступ к k-му элементу, трудоемкость примерно одинакова.

Структуры данных на основе линейных списков

Стек, очередь, дек

1. Стек- это линейный список, на котором все включения и исключения элементов делаются на одном конце. Пример стека: Монетница (монеты добавляются строго по одной), стопка тарелок. В любой момент времени пользователю доступен только верхний элемент. Таким образом, самый первый элемент, добавленный в стек, будет исключен из него самым последним. Или иными словами последний добавленный первым "выйдет". Last in, First Out. LIFO.

2. Очередь - линейный список, в котором все включения делаются на одном конце, а все исключения - на другом. В очереди первый добавленный элемент оказывается самым ближайшим элементом на выходе, после его удаления из очереди можно будет удалить второй добавленный элемент. Таким образом, исключение из очереди осуществляется в линейном порядке его добавления. Такой принцип получил название «First In, First Out», FIFO.

3. Дек - является обобщением очереди и стека, то есть включения, и исключение элементов могут быть выполнены на любом конце. Различают деки, ограниченные по входу (все включения в элементы списка - строго на одном конце), и деки, ограниченные по выходу.