Оценка сложности алгоритмов

Отказ от языка ассемблера был яблоком раздора в наших садах эдема: языки, использование которых приводит к растранжириванию машинного времени, греховны.

Алан Джей Перлис

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

Сложность алгоритма – количественная характеристика, которая говорит о том, сколько времени он работает (временная сложность), либо о том, какой объем памяти требуется для его работы (ёмкостная сложность).

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

Оценивая порядок сложности алгоритма, необходимо использовать только ту часть, которая возрастает быстрее всего. Предположим, что рабочий цикл описывается выражением N^3+N. В таком случае его сложность будет равна O(N^3). Рассмотрение быстро растущей части функции позволяет оценить поведение алгоритма при увеличении N. Например, при N=100, разница между N^3+N=1000100 и N=1000000 равна всего лишь 100, что составляет 0,01%.

При вычислении O можно не учитывать постоянные множители в выражениях. Алгоритм с рабочим шагом 3N^3 рассматривается, как O(N^3). Это делает зависимость отношения O(N) от изменения размера задачи более очевидной.

Основные функции вычисления сложности

1. C – константа

2. log(log(N))

3. log(N)

4. N^C, 0<C<1

5. N

6. N*log(N)

7. N^C, C>1

8. C^N, C>1

9. N!

Если во внутренних циклах функции Fast происходит вызов функции Slow, то сложности подпрограмм перемножаются.

void Slow(){

for(int i=0;i<N;i++)

 for(int j=0;j<N;j++)

for(int k=0;k<N;k++)

     //...какое-то действие

}

voidFast(){

for(int i=0;i<N;i++)

 for(int j=0;j<N;j++)

     Slow();

}

voidBoth(){

Fast();

}

В данном случае сложность алгоритма составляет:

       O(N^2)*O(N^3)=O(N^5)

Если основной алгоритм вызывает вспомогательные по очереди, то их сложности складываются:

       O(N^2 )+O(N^3)=O(N^3)

void Slow(){

for(int i=0;i<N;i++)

 for(int j=0;j<N;j++)

for(int k=0;k<N;k++)

     //...какое-то действие

}

voidFast(){

for(int i=0;i<N;i++)

 for(int j=0;j<N;j++)

     //...какое-то действие

}

voidBoth(){

Fast();

Slow();

}

Если алгоритм вызывается редко и для небольших объёмов данных, то приемлемой можно считать сложность O(N^2), если же алгоритм работает в реальном времени, то не всегда достаточно производительности O(N).

Обычно алгоритмы со сложностью N*log(N) работают с хорошей скоростью. Алгоритмы со сложностью N^C можно использовать только при небольших значениях C. Вычислительная сложность алгоритмов, порядок которых определяется функциями C^N и N! очень велика, поэтому такие алгоритмы могут использоваться только для обработки небольшого объёма данных. [1]

	N=10	N=20	N=30	N=40	N=50
N3	0,001 с	0,008 с	0,027 с	0,064 с	0,125 с
2N	0,001 с	1,05 с	17,9 мин	1,29 дней	35,7 лет
3N	0,059 с	58,1 мин	6,53 лет	3,86×105 лет	2,28×1010 лет
N!	3,63 с	7,71×104 лет	8,41×1018 лет	2,59×1034 лет	9,64×1050 лет

 

Сложность задачи естественно определить как сложность самого эффективного алгоритма, решающего эту задачу.

ВАЖНО: В тех случаях, когда требуется оценить время выполнения алгоритма на конкретной машине, удобно использовать заголовочный файл <time.h>(мы его уже использовали при генерации псевдослучайных чисел). Функция clock() возвращает количество временных тактов, прошедших с начала запуска программы. С помощью макроса CLOCKS_PER_SEC функция получает количество пройденных тактов за 1 секунду. Таким образом, зная сколько выполняется тактов в секунду, можно посчитать время работы всей программы или отдельного её фрагмента

#include <iostream>

#include <time.h>

intmain (){

clock_tt = clock(); //от начала программы

… // действия

t = clock() - t;     //тактов за интервал

std::cout<<"Прошло "<<float(t)/CLOCKS_PER_SEC <<" секунд";

return 0;

}

Структуры данных

Программист – художник новой эпохи, который, экспериментируя, создает миры по своему вкусу. Он свободен от уродливых корпоративных этик, практик и дурного шлака.

Николай Кононов. Код Дурова. Реальная история «ВКонтакте» и ее создателя

Структура данных (англ. data structure) — программная единица, позволяющая хранить и обрабатывать множество однотипных и/или логически связанных данных в вычислительной технике.[2]

 

Динамические структуры данных

Функции задерживают связь, структуры данных стимулируют связь. Мораль: Структурируйте данные как можно позднее в процессе программирования.

Перлис Алан

Списки

Очереди

Деки

Деревья

Ассоциативные массивы

Ассоциативный массив (словарь) — абстрактный тип данных (интерфейс к хранилищу данных), позволяющий хранить пары вида (ключ, значение) и поддерживающий операции добавления пары, а также поиска и удаления пары по ключу.

 

 

Некоторые исследовательские задачи

Подход к программированию не должен определяться используемыми инструментами. В связи с этим он проводит различие между программированием на языке (programminginlanguage) и программированием с использованием языка (programmingintolanguage). Разработчики, программирующие «на» языке, ограничивают свое мышление конструкциями, непосредственно поддерживаемых языком. Если предоставляемые языком средства примитивны, мысли программистов будут столь же примитивными.

С.Макконелл, «Совершенный код»