1. 
   О-нотация
   

Очень часто требуется оценить, сколько времени работают эти алгоритмы. Но тут возникают проблемы:

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

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

Таблица О нотации:

1. 
   O(1) – Константная
   
2. 
   O(n) – Логарифмическая
   
3. 
   O(n^2) – Квадратическая
   
4. 
   O(log n) – логарифмическая
   
5. 
   O(n log n) – Квазилинейная
   

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

Линейных структуры данных обладают следующими свойствами:

• 
  Каждый элемент имеет не более 1 предшественника
  
• 
  Два разных элемента не могут иметь одинакового последователя
  

К линейным структурам данным можно отнести:

• 
  Массивы
  
• 
  Динамические массивы
  
• 
  Связный список
  
• 
  Стек
  
• 
  Очередь
  
• 
  Дек
  
• 
  Хэш-таблица
  

Квадратичные сортировки

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

Квадратичные сортировки:

1. 
   Сортировка пузырьком
   
2. 
   Сортировка вставками
   

2. 
   Оптимальные сортировки и поиски за логарифм
   

Сортировка слиянием(Merge) - это стабильный метод сортировки.
Пусть у нас есть два отсортированных по неубыванию массива размера n и m. Хотим получить отсортированный массив размера n+m из исходных.

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

---

Сложность:
Наилучший случай: O (n)
Наихудший случай: O (nlogn)
Средний случай: O (nlogn)

Сортировка подсчетом

Подсчетная сортировка применима, когда известно, что каждый вход принадлежит определенному набору S возможностей.Он работает путем создания целочисленного массива размером | S | и использование i- го бункера для подсчета вхождений i- го члена S во входных данных. Затем каждый ввод подсчитывается путем увеличения значения соответствующей ячейки. После этого счетный массив проходит по циклу, чтобы упорядочить все входы.
Сложность:
Наилучший случай: O (n + S)
Наихудший случай: O (n + S)
Средний случай: O (n + S)

Быстрая сортировка(QSort)
Основная идея быстрой сортировки: разделите записи, которые нужно отсортировать, на две независимые части с помощью сортировки, и ключевые слова одной части записей меньше, чем ключевые слова другой части, тогда две части записей могут сортировать отдельно для достижения Вся последовательность в порядке.
Сложность:
Наилучший случай: O (nlogn)
Худший случай: O (n2)
Средний случай: O (nlogn)

Heapsort

Heapsort - это алгоритм сортировки, разработанный с использованием структуры данных кучи. Стекирование представляет собой приблизительно полную структуру двоичного дерева, и в то же время удовлетворяет природе наложения: то есть значение ключа или индекс дочернего узла всегда меньше (или больше) его родительского узла.
Сложность:
Наилучший случай: O (nlogn)
Худший случай: O (nlogn)
Средний случай: O (nlogn)

Бинарный поиск — тип поискового алгоритма, который последовательно делит пополам заранее отсортированный массив данных, чтобы обнаружить нужный элемент. 
Основная последовательность действий алгоритма выглядит так:

1. 
   Сортируем массив данных.
   
2. 
   Делим его пополам и находим середину.
   
3. 
   Сравниваем срединный элемент с заданным искомым элементом.
   
4. 
   Если искомое число больше среднего — продолжаем поиск в правой части массива (если он отсортирован по возрастанию): делим ее пополам, повторяя пункт 3. Если же заданное число меньше — алгоритм продолжит поиск в левой части массива, снова возвращаясь к пункту 3.
   

---

Тернарный поиск — это алгоритм поиска минимума (или максимума) выпуклой функции на отрезке. Можно искать минимум (максимум) функции от вещественного аргумента, можно минимум (максимум) на массиве. Будем, для определённости, искать минимум функции f(x).
Это похоже на бинарный поиск, когда мы делим массив на две части, но в этом алгоритме мы делим данный массив на три части и определяем, в какой из них есть ключ (искомый элемент). Мы можем разделить массив на три части, взяв mid1 и mid2, которые можно вычислить

Шаги для выполнения троичного поиска:

1. 
   Сначала мы сравниваем ключ с элементом mid1. Если найдено равное, мы возвращаем mid1.
   
2. 
   Если нет, то мы сравниваем ключ с элементом mid2. Если найдено равное, мы возвращаем mid2.
   
3. 
   Если нет, то мы проверяем, меньше ли ключ, чем элемент mid1. Если да, то вернемся к первой части.
   
4. 
   Если нет, то мы проверяем, больше ли ключ, чем элемент mid2. Если да, то вернемся к третьей части.
   
5. 
   Если нет, то возвращаемся ко второй (средней) части.
   

3. 
   Динамическое программирование — метод решения задачи путём её разбиения на несколько одинаковых подзадач, рекуррентно связанных между собой. Самым простым примером будут числа Фибоначчи — чтобы вычислить некоторое число в этой последовательности, нам нужно сперва вычислить третье число, сложив первые два, затем четвёртое таким же образом на основе второго и третьего, и так далее.
   

Чтобы решить задачу по динамике вы должны ответить на 5 вопросов:

• 
  Что лежит в массиве?
  
• 
  Как инициализировать начало массива?
  
• 
  Как обходить массив?
  
• 
  Какой формулой считать элементы массива?
  
• 
  Где в массиве лежит ответ?
  

В отличие от жадного алгоритма, динамическое программирование находит оптимальное решение.

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

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

---

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

4. 
   Рекурсивный перебор и комбинаторные объекты
   

В терминах процесса и его шагов основные параметры рекурсивной функции:

- формальные параметры рекурсивной функции представляют начальное состояние для текущего шага процесса;

 - фактические параметры рекурсивного вызова представляют начальное состояние для следующего шага, в который производится переход из текущего при рекурсивном вызове;

 - локальные (автоматические) переменные представляют внутренние характеристики процесса на текущем шаге его выполнения;

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


Формальные параметры рекурсивной функции, глобальные и локальные переменные не могут быть взаимозаменяемы, как это иногда делается в обычных функциях. Особо следует быть внимательным при работе с глобальными переменными, т.к. множество экземпляров рекурсивных вызовов фактически их разделяют. Если речь идет о поисковых алгоритмах, и в последовательности вызовов рекурсивных функций производятся изменения в глобальных переменных, то по возвращении из рекурсивного вызова необходимо возвратить значения этих переменных в исходное состояние, в котором они находились на этом шаге рекурсии, т.е. произвести «откат».  Это объясняется тем, что смежные шаги рекурсивного алгоритма должны быть «прозрачны» по отношению друг к другу.

Перечислим последовательность и содержание шагов в проектировании и «сведении вместе» фрагментов рекурсивной функции.

1.      «Зацепить рекурсию» - определить, что составляет шаг рекурсивного алгоритма;

2.      Инварианты рекурсивного алгоритма. Основные свойства, соотношения, которые присутствуют на входе рекурсивной функции и которые сохраняются до следующего рекурсивного вызова, но уже в состоянии, более близком к цели;

3.      Глобальные переменные – общие данные процесса в целом;

4.      Начальное состояние шага рекурсивного алгоритма – формальные параметры рекурсивной функции;

5.      Ограничения рекурсии – обнаружение «успеха» - достижения цели на текущем шаге рекурсии и отсечение «неудач» - заведомо неприемлемых вариантов;

---

6.      Правила перебора возможных вариантов – способы формирования рекурсивного вызова;

7.      Начальное состояние следующего шага – фактические параметры рекурсивного вызова;

8.      Содержание и способ обработки результата – полный перебор с сохранением всех допустимых вариантов, первый возможный, оптимальный;

9.      Условия первоначального вызова рекурсивной функции в main.

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

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

Комбинаторные объекты — конечные множества, на элементы которых могут накладываться определённые ограничения, такие как: различимость или неразличимость элементов, возможность повторения одинаковых элементов и т. п.

Примеры комбинаторных объектов

• 
  Битовые векторы-последовательность нулей и единиц заданной длины.
  
• 
  Перестановки-упорядоченный набор чисел 1,2,…,n, обычно трактуемый как биекция на множестве {1,2,…,n}, которая числу i ставит соответствие i-й элемент из набора.
  Примером перестановки может служить задача о рассадке n человек за стол по n местам.
  
• 
  Перестановки с повторениями-те же перестановки, однако некоторые элементы могут встречаться несколько раз.
  В пример можно привести следующую задачу: имеется набор книг {a1,a2,…,an}, каждая из которых имеется в k1,k2,…,kn экземплярах соответственно. Сколько существует способов переставить книги на полке?
  
• 
  Размещения из n по k — упорядоченный набор из k различных элементов некоторого n-элементного множества.
  Примером размещения может служить задача о рассадке k человек за стол по n местам, где n>k.
  
• 
  Размещения с повторениями, составленное из данных n элементов по k — отображение множества k первых натуральных чисел 1,2,…,k в данное множество {a1,a2,…,an}.
  В пример можно привести следующую задачу: имеется n книг, каждая в k экземплярах. Сколькими способами может быть сделан выбор книг из числа данных?
  
• 
  Сочетания из n по k — набор k элементов, выбранных из данных n элементов.
  Примером сочетания может служить задача о выборе k книг из n вариантов.
  
• 
  Сочетания с повторениями— те же сочетания, только теперь даны n типов элементов, из которых нужно выбрать k элементов, причем элементов каждого типа неограниченное количество, и элементы одного типа должны стоять подряд друг за другом.
  В пример можно привести следующую задачу: имеется n пирожных. Сколько способов купить k пирожных?
  
• 
  Разбиение на неупорядоченные слагаемые-представление числа n в виде суммы слагаемых.
  

---

Смотрите также файлы

• Министерство образования Республики Башкортостан.docx

• При каком положительном значении параметра t прямые, заданные уравнениями 3tx.doc

• Социальная педагогика как вид профессиональной деятельности.docx

• Тесты для самоконтроля Ситуационные задачи.doc

• Задача 1 Для ступенчатого стального стержня находящегося под воздействием заданных внешних сил.docx