Главный параметр сложности алгоритма

Технологии программирования

Содержание лекции:

 

1) Свойства алгоритма;

2) Сложность алгоритма. O- и ϴ - нотации;

3) Исполнитель алгоритма;

4) Инварианты. Индуктивные функции;

5) Абстракции. Интерфейс абстракции;

6) Рекурсия. Принцип разделяй и властвуй;

7) Основная теорема о рекурсии;

8) Быстрое вычисление степеней.

 

Свойства алгоритма

Исполнитель

 

Алгоритм – это последовательность команд для исполнителя, обладающая рядом свойств:

1) полезность, т.е. умение решать поставленную задачу;

2) детерминированность, т.е. каждый шаг алгоритма должен быть строго определён во всех возможных ситуациях;

3) конечность, т.е. способность алгоритма завершиться для любого множества входных данных;

4) массовость, т.е. применимость алгоритма к разнообразным входным данным.

 

Алгоритм для своего исполнения требует от исполнителя некоторых ресурсов.

 

Программа – это запись алгоритма на формальном языке.

 

Исполнители

Одна задача – несколько алгоритмов – разные используемые ресурсы.

 

Разные исполнители – разные элементарные действия и элементарные объекты.

 

Исполнитель “компьютер”:

1) устройство центральный процессор;

2) элементарные действия – сложение, умножение, сравнение, переход и т.д.

3) устройство память как хранитель элементарных объектов;

4) элементарные объекты – целые, вещественные числа.

 

Эффективность – способность алгоритма использовать ограниченное количество ресурсов.

 

Сложность алгоритма. O- и ϴ - нотации

Сложность алгоритма

Какая бывает сложность алгоритма:

1) комбинационная сложность – минимальное число элементов для реализации алгоритма в виде вычислительного устройства;

2) описательная сложность – длина описания алгоритма на формальном языке;

3) вычислительная сложность – количество элементарных операций, исполняемых алгоритмом для неких входных данных.

 

Нет циклов – описательная сложность примерно коррелирует с вычислительной.

 

Есть циклы – интересна асимптотика зависимости времени вычисления от входных данных.

 

Главный параметр сложности алгоритма

 

Введём понятие главный параметр N, наиболее сильно влияющий на скорость исполнения алгоритма. Это может быть:

1) размер массива;

2) количество символов в строке;

3) количество битов в записи числа;

4) если таких параметров несколько – обобщённый параметр, функция от нескольких параметров.

 

Нотация сложности. Символ ϴ (читается " тэта большое" )

Далее: сложность ≡ – вычислительная сложность.

Функция f(N) имеет порядок ϴ (g(N)), если существуют постоянные c₁, c₂ и N₁ такие, что для всех N> N1.

0 ≤ c1g(N) ≤ f (N) ≤ c2g(N)

ϴ (f(n)) – класс функций, примерно пропорциональных f(n).

 

Нотация сложности. Символ O (читается " О большое" )

Функция f(N) имеет порядок O(g(N)), если существуют постоянные c1 и N1 такие, что для всех N> N1.

f(N) ≤ c1g(N)

O(f(n)) – класс функций, ограниченных сверху cf(n).

 

Приближённое вычисление сложности

 

Пусть F(N) – функция сложности алгоритма в зависимости от N.

Тогда если существует такая функция G(N) (асимптотическая функция) и константа C, что

то сложность алгоритма F(N) определяется функцией G(N) с коэффициентом амортизации C.

 

Асимптотика основных зависимостей

 

Класс сложности определяется по асимптотической зависимости F(N).

 

Экспонента с любым коэффициентом превосходит любую степень.

 

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

 

Логарифм по любому основанию, большему единицы превосходит 1.

 

F(N) = N³ + 7N² - 14N = ϴ (N³)

 

F(N) = 1.01^N + N¹⁰ = ϴ (1.01^N)

 

F(N) = N^1.3 + 10log₂N = ϴ (N^1.3)

 

На практике чаще используют O-нотацию, так как ϴ -нотацию обычно сложнее доказывать.

 

Зависимость времени исполнения от исходных данных

 

Пусть имеется массив A длиной N элементов.

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

 

K_min = 1

 

K_max = N

 

 

Подходит ли символ ϴ?

 

Нет. Для данного алгоритма подходит O-символ: f(N) = O(N).

 

 

Пусть имеется массив A длиной N элементов.

Сколько операций потребуется, чтобы сложить все элементы массива?

 

K = N

 

Подходит ли символ ϴ?

 

Подходит. f(N) = ϴ (N).

 

Задача о рюкзаке

 

Обратим внимание на то, что предметы разрезать на куски нельзя. Если это разрешить, то задача будет иметь простое решение.

 

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

 

Для определения количества комбинаций можно рассуждать так, что K предметов можно выбрать из N предметов (C_N^K), и так для всех K от 0 до N.

 

F(N) = (1 + 1) ^N = 2^N

 

Свойства алгоритма

 

Предложенный алгоритм:

1) детерминированный;

2) конечный;

3) массовый;

4) полезный.

Его сложность пропорциональна 2^N, так как требуется перебрать все возможные комбинации предметов.

 

NP-задачи о рюкзаке

 

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

 

Исполнитель алгоритма

Исполнители

 

Нашим исполнителем будет язык C++.

 

Элементарные типы отображаются на вычислительную систему char, int, double.

 

Элементарные операции аппаратного исполнителя: операции над элементарными типами и операции передачи управления.

 

Типы данных языка – комбинация элементарных типов данных.

 

Операции языка – комбинация элементарных операций.

 

Представление типов

 

Целые числа – двоичное представление.

 

Простые элементарные операции: сложение, вычитание, присваивание и т.д.

 

Сложные элементарные операции: целочисленное умножение, деление (не на степень двойки), переход.

 

Приведём пример кода:

if (x > 0) t = 1;

else t = 0;

Этот код выполнится выполняется намного медленнее, чем t = x > 0; (потому что для t = x > 0; есть машинная команда).

 

Инварианты. Индуктивные функции

Понятие абстракции

 

Как только появляются объекты, появляются абстракции – механизм разделения сложных объектов на более простые, без деталировки подробностей разделения.

 

Функциональная абстракция – разделение функций, методов, которые манипулируют с объектами, с их реализацией.

 

Интерфейс абстракции – набор методов, характерных для данной абстракции.

 

Пример: абстракция массива

 

1) create – создать массив (статический или динамический).

int a[100]; // статический

int *b = calloc(100, sizeof(int)); // динамический

int *c = new int[100]; // динамический

2) destroy – удалить массив (статический или динамический).

free(b);

delete c; // можно и delete [] c

3) fetch – обратиться к элементу массива.

int q1 = a[i];

int q2 = b[i];

int q3 = c[i];

 

Для массива основная операция – это доступ к элементу. Она выглядит одинаково для всех представлений.

 

Абстракция “стек”

 

Одна из удобных абстракций – стек.

 

Стек должен предоставлять нам методы:

1) create – создание стека (может быть, потребуется аргумент, определяющий максимальный размер стека);

2) push – занесение элемента в стек (размер стека увеличивается на единицу, занесённый элемент становится вершиной стека);

3) pop – извлечь элемент, являющийся вершиной стека и уменьшить размер стека на единицу (если стек пуст, то значение операции не определено);

4) peek – получить значение элемента, находящегося на вершине стека, не изменяя стека (если стек пуст, значение операции не определено);

5) empty – предикат истинен, когда стек пуст;

6) destroy – уничтожить стек.

 

Абстракция “множество”

 

Множество – это совокупность однотипных элементов, на которых определена операция сравнения.

 

Множество обозначается списком значений внутри фигурных скобок.

 

Пустое множество: s = {}.

 

Множество должно предоставлять нам методы:

 

1) insert – добавление элемента в множество.

{1, 2, 3}.insert(5) -> {1, 2, 3, 5}

{1, 2, 3}.insert{2} -> {1, 2, 3}

2) remove – удалить элемент из множества.

{1, 2, 3}.remove(3) -> {1, 2}

{1, 2, 3}.remove(5) -> не определено.

3) in – определить принадлежность множеству.

{1, 2, 3}.in(2) -> true

{1, 2, 3}.in(5) -> false

4) size – определить количество элементов в множестве.

 

Рекуррентность и рекурсия

 

Рекуррентная форма -> рекурсивный алгоритм.

int fibo(int n)

{

if (n == 0) return 0;

if (n == 1) return 1;

return fibo(n-1) + fibo(n-2);

}

 

Три вопроса:

1) корректен ли он?

2) как оценить время его работы?

3) как его ускорить?

 

Дерево вызовов функции для n = 5

 

 

Как ускорить?

 

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

 

Третий вопрос: можно ли ускорить алгоритм?

 

Вводим добавочный массив.

 

int fibo(int n)

{

const int MAXN = 1000;

static int c[MAXN];

if (n == 0) return 0;

if (n == 1) return 1;

if (c[n] > 0) return c[n];

return c[n] = fibo(n-1) + fibo(n-2);

}

 

Дерево вызовов модифицированной функции для n = 5

 

 

Как умножать длинные числа?

 

Школьный алгоритм: O(n²)

 

Алгоритм быстрого умножения

 

Можно ли быстрее?

 

Да. Используя принцип разделяй и властвуй.

 

Быстрый алгоритм умножения был изобретён Гауссом в 19 веке и переизобретён Анатолием Карацубой в 1960-м году.

 

Разделим число (n) на две примерно равные половины:

N₁ = Tx₁ + y₁

N₂ = Tx₂ + y₂

 

При умножении в столбик N₁ × N₂ = T²x₁x₂ + T (x₁y₂ + x₂y₁) + y₁y₂

 

Это – четыре операции умножения и три операции сложения.

 

Число T определяет, сколько нулей нужно добавить к концу числа в соответствующей системе счисления.

 

Алгоритм Карацубы

 

Алгоритм Карацубы находит произведение по другой формуле:

 

N₁ × N₂ = T²x₁x₂ + T (x₁ + y₁)(x₂ + y₂) - x₁x₂ - y₁y₂) + y₁y₂

N₁ = 56, N₂ = 78, T = 10

x₁ = 5, y₁ = 6

x₂ = 7, y₂ = 8

x₁x₂ = 5 × 7 = 35

(x₁ + y₁) (x₂ + y₂) = (5 + 6) (7 + 8) = 11 ∗ 15 = 165

y₁y₂ = 6 × 8 = 48

N₁ × N₂ = 35 ∗ 100 + (165 - 35 - 48) ∗ 10 + 48 = 4368

 

Т.е. 3 операции умножения и 6 сложения.

 

Основная теорема о рекурсии

Основная теорема о рекурсии

 

Пусть для некоторых a > 0, b > 1, d ≥ 0. Тогда

 

 

Ещё о сложности

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

 

Для вектора-столбца из элементов F_n-1 и F_n умножение на ту же матрицу даст:

 

Таким образом,

 

Возведение в степень

 

Для нахождения n-го числа Фибоначчи достаточно вычислить

 

Можно ли возвести число в n-ую степень за число операций, меньших n - 1?

 

Быстрое вычисление степеней

 

Возведение в квадрат – это умножение на себя.

 

х¹⁶ = (х⁸)² = ((х⁴)²)² = (((х²)²)²)²

 

х¹⁸ = (х⁹)² = ((х⁸ * х)²)² = (((х²)²)² * х)²

 

Рекуррентная формула

 

Технологии программирования

Содержание лекции:

 

1) Свойства алгоритма;

2) Сложность алгоритма. O- и ϴ - нотации;

3) Исполнитель алгоритма;

4) Инварианты. Индуктивные функции;

5) Абстракции. Интерфейс абстракции;

6) Рекурсия. Принцип разделяй и властвуй;

7) Основная теорема о рекурсии;

8) Быстрое вычисление степеней.

 

Свойства алгоритма

Исполнитель

 

Алгоритм – это последовательность команд для исполнителя, обладающая рядом свойств:

1) полезность, т.е. умение решать поставленную задачу;

2) детерминированность, т.е. каждый шаг алгоритма должен быть строго определён во всех возможных ситуациях;

3) конечность, т.е. способность алгоритма завершиться для любого множества входных данных;

4) массовость, т.е. применимость алгоритма к разнообразным входным данным.

 

Алгоритм для своего исполнения требует от исполнителя некоторых ресурсов.

 

Программа – это запись алгоритма на формальном языке.

 

Исполнители

Одна задача – несколько алгоритмов – разные используемые ресурсы.

 

Разные исполнители – разные элементарные действия и элементарные объекты.

 

Исполнитель “компьютер”:

1) устройство центральный процессор;

2) элементарные действия – сложение, умножение, сравнение, переход и т.д.

3) устройство память как хранитель элементарных объектов;

4) элементарные объекты – целые, вещественные числа.

 

Эффективность – способность алгоритма использовать ограниченное количество ресурсов.

 

Сложность алгоритма. O- и ϴ - нотации

Сложность алгоритма

Какая бывает сложность алгоритма:

1) комбинационная сложность – минимальное число элементов для реализации алгоритма в виде вычислительного устройства;

2) описательная сложность – длина описания алгоритма на формальном языке;

3) вычислительная сложность – количество элементарных операций, исполняемых алгоритмом для неких входных данных.

 

Нет циклов – описательная сложность примерно коррелирует с вычислительной.

 

Есть циклы – интересна асимптотика зависимости времени вычисления от входных данных.

 

Главный параметр сложности алгоритма

 

Введём понятие главный параметр N, наиболее сильно влияющий на скорость исполнения алгоритма. Это может быть:

1) размер массива;

2) количество символов в строке;

3) количество битов в записи числа;

4) если таких параметров несколько – обобщённый параметр, функция от нескольких параметров.

 

Нотация сложности. Символ ϴ (читается " тэта большое" )

Далее: сложность ≡ – вычислительная сложность.

Функция f(N) имеет порядок ϴ (g(N)), если существуют постоянные c₁, c₂ и N₁ такие, что для всех N> N1.

0 ≤ c1g(N) ≤ f (N) ≤ c2g(N)

ϴ (f(n)) – класс функций, примерно пропорциональных f(n).

 

Нотация сложности. Символ O (читается " О большое" )

Функция f(N) имеет порядок O(g(N)), если существуют постоянные c1 и N1 такие, что для всех N> N1.

f(N) ≤ c1g(N)

O(f(n)) – класс функций, ограниченных сверху cf(n).

 

1234Следующая ⇒

Поделиться: