Сложность в определении размера и. Ёмкостная сложность при равномерном весовом критерии. O – оценка для худшего случая

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

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

Модель RAM (Random Access Machine)

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

Модель состоит из памяти и процессора, которые работают следующим образом:

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

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

Подсчет операций. Классы входных данных

Одним из способов оценки трудоемкости (\(T_n\)) является подсчет количества выполняемых операций . Рассмотрим в качестве примера алгоритм поиска минимального элемента массива.

Начало; поиск минимального элемента массива array из N элементов min:= array для i от 2 до N выполнять: если array[i] < min min:= array[i] конец; вернуть min

При выполнении этого алгоритма будет выполнена:

1. N — 1 операция присваивания счетчику цикла i нового значения;
2. N — 1 операция сравнения счетчика со значением N;
3. N — 1 операция сравнения элемента массива со значением min;
4. от 1 до N операций присваивания значения переменной min.

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

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

1. исходные данные разбиваются на группы так, что трудоемкость алгоритма (\(t_i\)) для любого набора данных одной группы одинакова;
2. исходя из доли наборов данных группы в общем числе наборов, рассчитывается вероятность для каждой группы (\(p_i\));
3. оценка среднего случая вычисляется по формуле: \(\sum\limits_{i=1}^m p_i\cdot t_i\).

Асимптотические обозначения

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

При анализе скорости роста игнорируются постоянные члены и множители в выражении, т.е. функции \(f_x = 10 \cdot x^2 + 20 \) и \(g_x = x^2\) эквивалентны с точки зрения скорости роста. Незначащие члены лишь добавляют «волнистости», которая затрудняет анализ.

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

• \(\mathcal{O}(g)\) — функции, растущие медленнее чем g;
• \(\Omega(g)\) — функции, растущие быстрее чем g;
• \(\Theta(g)\) — функции, растущие с той же скоростью, что и g.

Запись \(f_n = \mathcal{O}(g_n)\) означает принадлежность функции f классу \(\mathcal{O}(g)\), т.е. функция f ограничена сверху функцией g для достаточно больших значений аргумента. \(\exists n_0 > 0, c > 0: \forall n > n_0, f_n \leq c \cdot g_n\).

Ограниченность функции g снизу функцией f записывается следующим образом: \(g_n =\Omega(f_n)\). Нотации \(\Omega\) и \(\mathcal{O}\) взаимозаменяемы: \(f_n = \mathcal{O}(g_n) \Leftrightarrow g_n =\Omega(f_n)\).

Асимптотические обозначения «О большое» и «Омега большое»

Если функции f и g имеют одинаковую скорость роста (\(f_n = \Theta(g_n)\)), то существуют положительные константы \(c_1\) и \(c_2\) такие, что \(\exists n_0 > 0: \forall n > n_0, f_n \leq c_1 \cdot g_n, f_n \geq c_2 \cdot g_n\). При этом \(f_n = \Theta(g_n) \Leftrightarrow g_n = \Theta(f_n)\).

Асимптотическое обозначение «Тета большое»

Примеры анализа алгоритмов

Алгоритм поиска минимального элемента массива , приведенный выше, выполнит N итераций цикла. Трудоемкость каждой итерации не зависит от количества элементов массива, поэтому имеет сложность \(T^{iter} = \mathcal{O}(1)\). В связи с этим, верхняя оценка всего алгоритма \(T^{min}_n = \mathcal{O}(n) \cdot \mathcal{O}(1) = \mathcal{O}(n \cdot 1) = \mathcal{O}(n)\). Аналогично вычисляется нижняя оценка сложности, а в силу того, что она совпадает с верхней — можно утверждать \(T^{min}_n = \Theta(n) \).

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

Начало; пузырьковая сортировка массива array из N элементов nPairs:= N; количество пар элементов hasSwapped:= false; пока что ни одна пара не нарушила порядок для всех i от 1 до nPairs-1 выполнять: если array[i] > array то: swap(array[i], array); обменять элементы местами hasSwapped:= true; найдена перестановка nPairs:= nPairs - 1; наибольший элемент гарантированно помещен в конец если hasSwapped = true - то перейти на п.3 конец; массив array отсортирован

Трудоемкость функции swap не зависит от количества элементов в массиве, поэтому оценивается как \(T^{swap} = \Theta(1) \). В результате выполнения внутреннего цикла, наибольший элемент смещается в конец массива неупорядоченной части, поэтому через N таких вызовов массив в любом случае окажется отсортирован. Если же массив отсортирован, то внутренний цикл будет выполнен лишь один раз.

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

• \(T^{bubble}_n = \mathcal{O}(\sum\limits_{i=1}^n \sum\limits_{j=1}^{n-i} 1) = \mathcal{O}(\sum\limits_{i=1}^n n) = \mathcal{O}(n ^2)\);
• \(T^{bubble}_n = \Omega(1 \cdot \sum\limits_{j=1}^{n-i} 1) = \Omega(n)\).

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

Начало; selection_sort - сортировка массива array из N элементов методом выбора для всех i от 1 до N выполнять: imin:= indMin(array, N, i) swap(array[i], array) конец; массив array отсортирован

Для поиска наименьшего элемента неупорядоченной части массива используется функция indMin, принимающая массив, размер массива и номер позиции, начиная с которой нужно производить поиск. Анализ сложности этой функции можно выполнить аналогично тому, как это сделано для функции min — количество операций линейно зависит от количества обрабатываемых элементов: \(T^{indMin}_{n, i} = \Theta(n — i)\).

У сортировки выбором нет ветвлений, которые могут внести различия в оценку наилучшего и наихудшего случаев, ее трудоемкость: \(T^{select}_n = \Theta(\sum\limits_{i=1}^{n} (T^{indMin}_{n, i} + T^{swap})) =\Theta(\sum\limits_{i=1}^{n} (n-i)) = \Theta(\frac{n-1}{2} \cdot n) = \Theta(n^2) \).

Математический аппарат анализа алгоритмов

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

Формулы суммирования

В примерах, рассмотренных выше, мы уже сталкивались с нетривиальными формулами суммирования. Чтобы дать оценку суммы можно использовать ряд известных тождеств:

• вынос постоянного множителя за знак суммы: \(\sum\limits_{i=1}^{n} (c \cdot f_i) = c \cdot \sum\limits_{i=1}^{n} \cdot f_i\);
• упрощение суммы составного выражения: \(\sum\limits_{i=1}^{n} (f_i + g_i) = \sum\limits_{i=1}^{n} (f_i) + \sum\limits_{i=1}^{n} (g_i)\);
• сумма чисел арифметической прогрессии: \(\sum\limits_{i=1}^{n} (i^p) = \Theta(n^{p+1})\);
• сумма чисел геометрической прогрессии: \(\sum\limits_{i=0}^{n} (a^i) = \frac {a \cdot (a^{n+1} — 1)}{a — 1}\). При \(n \to \infty \) возможны 2 варианта:
  • если a < 1, то сумма стремится к константе: \(\Theta(1)\);
  • если a > 1, то сумма стремится к бесконечности: \(\Theta(a^{n+1})\);
  • если a = 0, формула неприменима, сумма стремится к N: \(\Theta(n)\);
• логарифмическая сложность алгоритма: \(\sum\limits_{i=1}^{n} \frac{1}{i} = \Theta(\log n)\);
• сумма логарифмов: \(\sum\limits_{i=1}^{n} \log i = \Theta(n \cdot \log n)\).

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

Суммирование и интегрирование

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

На рисунках приведен пример аппроксимации функции \(f_x = \log x\) левыми и правыми прямоугольниками. Очевидно, они дадут верхнюю и нижнюю оценку площади под графиком:

• \(\int\limits_a^n f_x dx \leq \sum\limits_{i=a }^{n} f_i \leq \int\limits_{a+1}^{n+1} f_x dx\) для возрастающих функций;
• \(\int\limits_a^n f_x dx \geq \sum\limits_{i=a }^{n} f_i \geq \int\limits_{a+1}^{n+1} f_x dx\) для убывающих функций.

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

Сравнение сложности алгоритмов. Пределы

Сложность алгоритмов определяется для больших объемов обрабатываемых данных, т.е. при \(n\to\infty\). В связи с этим, при сравнении трудоемкости двух алгоритмов можно рассмотреть предел отношения функций их сложности : \(\lim\limits_{n \to \infty} \frac {f_n}{g_n}\). В зависимости от значения предела возможно сделать вывод относительно скоростей роста функций:

• предел равен константе и не равен нулю, значит функции растут с одной скоростью:\(f_n = \Theta(g_n)\);
• предел равен нулю, следовательно \(g_n\) растет быстрее чем \(f_n\): \(f_n = \mathcal{O}(g_n)\);
• предел равен бесконечности, \(g_n\) растет медленнее чем \(f_n\): \(f_n = \Omega(g_n)\).

Если функции достаточно сложны, то такой прием значительно упрощает задачу, т.к. вместо предела отношения функций можно анализировать предел отношения их производных (согласно правилу Лопиталя ): \(\lim\limits_{n \to \infty} \frac {f_n}{g_n} = \lim\limits_{n \to \infty} \frac {f’_n}{g’_n}\). Правило Лопиталя можно использовать если функции обладают следующими свойствами:

• \(\lim\limits_{n \to \infty} \frac {f_n}{g_n} = \frac{0}{0} или \frac {\infty}{\infty} \);
• \(f_n \) и \(g_n\) дифференцируемы;
• \(g’_n \ne 0 \) при \(n \to \infty\);
• \(\exists \lim\limits_{n \to \infty} \frac {f’_n}{g’_n}\).

Допустим, требуется сравнить эффективность двух алгоритмов с оценками сложности \(\mathcal{O}(a^n)\) и \(\mathcal{O}(n^b)\), где a и b — константы. Известно, что \((c^x)’ =c^x \cdot ln(c)\), но \((x^c)’ = c \cdot x^{c-1} \). Применим правило Лопиталя к пределу отношения наших функций b раз, получим: \(\lim\limits_{n \to \infty} \frac {\mathcal{O}(a^n)}{\mathcal{O}(n^b)} = \lim\limits_{n \to \infty} \frac {\mathcal{O}(a^n * ln^b (a))}{\mathcal{O}(b!)} = \infty\). Значит функция \(a^n\) имеет более высокую скорость роста. Без использования пределов и правила Лопиталя такой вывод может казаться не очевидным.

Логарифмы и сложность алгоритмов. Пример

По определению \(\log_a{x} = b \Leftrightarrow x = a^b\). Необходимо знать, что \(x \to \infty \Rightarrow \log_a{x} \to \infty\), однако, логарифм — это очень медленно растущая функция . Существует ряд формул, позволяющих упрощать выражения с логарифмами:

• \(\log_a{x \cdot y} = \log_a{x} + \log_a{ y}\);
• \(\log_a{x^b} = b \cdot \log_a{ x}\);
• \(\log_a{x} =\frac{\log_b{x}}{\log_b{a}}\).

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

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

Начало; поиск элемента E в отсортированном по возрастанию массиве array из N элементов left:= 1, right:= N; левая и правая граница, в которых находится искомый элемент выполнять пока left =< right: mid:= (right + left) div 2; вычисление индекса элемента посередине рассматриваемой части массива если array = E конец; вернуть true (элемент найден) если array < E; искомый элемент больше середины, значит все элементы левее mid можно отбросить left:= mid + 1; иначе right:= mid конец; вернуть false (элемент не найден)

Очевидно, что на каждом шаге алгоритма количество рассматриваемых элементов сокращается в 2 раза. Количество элементов, среди которых может находиться искомый, на k-том шаге определяется формулой \(\frac{n}{2^k}\). В худшем случае поиск будет продолжаться пока в массиве не останется один элемент, т.е. чтобы определить количество итераций для верхней оценки, достаточно решить уравнение \(1 = \frac{n}{2^k} \Rightarrow 2^i = n \Rightarrow i = \log_2 n\). Следовательно, алгоритм имеет логарифмическую сложность: \(T^{binSearch}_n = \mathcal{O}(\log n)\).

Результаты анализа. Замечания

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

Анализ алгоритмов позволяет определить минимально возможную трудоемкость, например:

• алгоритм поиска элемента в неупорядоченном массиве не может иметь верхнюю оценку сложности лучше, чем \(\mathcal{O}(n)\). Это связано с тем, что невозможно определить отсутствие элемента в массиве (худший случай) не просмотрев все его элементы;
• возможно формально доказать, что не возможен алгоритм сортировки произвольного массива, работающий лучше чем \(\mathcal{O}(n \cdot \log n)\) .

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

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

1. – режим доступа: https://сайт/archives/578. Дата обращения: 06.01.2014.
2. Васильев В. С. [Электронный ресурс] – режим доступа: https://сайт/archives/1462. Дата обращения: 06.01.2014.
3. Дж. Макконелл . Активный обучающий подход. - 3-е дополненное издание. М: Техносфера, 2009. -416с.
4. Миллер, Р. Последовательные и параллельные алгоритмы: Общий подход / Р. Миллер, Л. Боксер; пер. с англ. - М. : БИНОМ. Лаборатория знаний, 2006. - 406 с.
5. Скиена С. Алгоритмы. Руководство по разработке. 2-е изд.: Пер. с англ. - СПб.: БХВ-Петербург. 2011. - 720 с.: ил.

Если для решения задачи существует один алгоритм, то можно придумать и много других алгоритмов для решения этой же задачи. Какой алгоритм лучше подходит для решения конкретной задачи? По каким критериям следует выби­рать алгоритм из множества возможных? Как правило, мы высказываем суждение об алгоритме на основе его оценки исполнителем-человеком. Алгоритм кажется нам сложным, если даже после внимательного его изучения мы не можем понять, что же он делает. Мы можем наз­вать алгоритм сложным и запутанным из-за того, что он обладает разветвленной логической структурой, содержа­щей много проверок условий и переходов. Однако для компьютера выполнение программы, реализующей та­кой алгоритм, не составит труда, так как он выполняет одну команду за другой, и для компьютера неважно - операция ли это умножения или проверка условия.

Более того, мы можем написать громоздкий алгоритм, в котором выписаны подряд повторяющиеся действия (без использования циклической структуры). Однако с точки зрения компьютерной реализации такого алгорит­ма практически нет никакой разницы, использован ли в программе оператор цикла (например, 10 раз на экран выводится слово "Привет") или 10 раз последовательно выписаны операторы вывода на экран слова "Привет".

Для оценки эффективности алгоритмов введено поня­тие сложности алгоритма.

Определение. Вычислительным процессом, порожденным алгоритмом, называется последовательность шагов алгоритма, пройденных при исполнении этого ал­горитма.

Определение. Сложность алгоритма - коли­чество элементарных шагов в вычислительном процессе этого алгоритма.

Обратите внимание, именно в вычислительном про­цессе, а не в самом алгоритме. Очевидно, для сравнения сложности разных алгоритмов необходимо, чтобы слож­ность подсчитывалась в одних и тех же элементарных действиях.

Определение. Временная сложность алгорит­ма - это время Т, необходимое для его выполнения. Оно равно произведению числа элементарных действий на среднее время выполнения одного действия: Т = kt.

Поскольку t зависит от исполнителя, реализующего алгоритм, то естественно считать, что сложность алго­ритма в первую очередь зависит от k. Очевидно, что в наибольшей степени количество операций при выполне­нии алгоритма зависит от количества обрабатываемых данных. Действительно, для упорядочивания по алфавиту списка из 100 фамилий требуется существенно меньше операций, чем для упорядочивания списка из 100 000 фамилий. Поэтому сложность алгоритма выражают в виде функции от объема входных данных.

Пусть есть алгоритм А. Для него существует пара­метр а, характеризующий объем обрабатываемых алго­ритмом данных, этот параметр часто называют размер­ностью задачи. Обозначим через Т(n) время выполне­ния алгоритма, через f - некую функцию от п.

Определение. Будем говорить, что Т(n) алгорит­ма имеет порядок роста f(n), или, по-другому, алго­ритм имеет теоретическую сложность O * (f(n)) , если найдутся такие константы с 1 , с 2 > 0 и число п 0 , что c 1 f(n)) < Т(п) < c 2 f(n) при всех п >= n 0 . Здесь предпола­гается, что функция f(n) неотрицательна, но крайней мере при п >= n 0 . Если для Т(п) выполняется условие Т(n) <= сf(п), то говорят, что алгоритм имеет теорети­ческую сложность О(п) (читается "о" большое от n).

Так, например, алгоритм, выполняющий только опе­рации чтения данных и занесения их в оперативную па­мять, имеет линейную сложность 0(п). Алгоритм сорти­ровки методом прямого выбора имеет квадратичную сложность 0(п 2) , так как при сортировке любого мас­сива надо выполнить (п 2 - п)/2 операций сравнения (при этом операций перестановок вообще может не быть, на­пример, на упорядоченном массиве, в худшем случае надо будет выполнить п перестановок). А сложность алгоритма умножения матриц (таблиц) размера п x п будет уже кубической O(n 3) , так как для вычисления каждого эле­мента результирующей матрицы требуется п умножений и п - 1 сложений, а всего этих элементов п 2 .

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

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

Если мы рассматриваем алгоритмы, реализующиеся на компьютере, то к требованию выполнения за разумное время прибавляется требование выполнения в ограни­ченном объеме оперативной памяти.

Известно, что во многих языках программирования нет операции возведения в степень, следовательно, такой алгоритм надо программисту писать самостоятельно. Опе­рация возведения в степень реализуется через операции умножения; с ростом показателя степени растет количе­ство операций умножения, которые выполняются доста­точно долго. Следовательно, актуален вопрос о создании эффективного алгоритма возведения в степень.

Рассмотрим метод быстрого вычисления натуральной степени вещественного числа х. Этот метод был описан еще до нашей эры в Древней Индии.

Запишем п в двоичной системе счисления.

Заменим в этой записи каждую " 1" парой букв КХ, а каждый "О" - буквой К.

Вычеркнем крайнюю левую пару КХ.

Полученная строка, читаемая слева направо, дает правило быстрого вычисления х n , если букву К рассматривать как операцию возведения результата в квад­рат, а букву X - как операцию умножения результата на х. Вначале результат равен х.

Пример 1. Возвести х в степень п = 100.

Переведем число п в двоичную систему счисления: п = 100 10 = 1100100,

Строим последовательность КХКХКККХКК

Вычеркиваем АХ слева => КХКККХКК

Вычисляем искомое значение

К => возводим х в квадрат => получаем х 2 ,

X => умножаем результат на х=> получаем х 3

К => возводим результат в квадрат => получаем х 6

К=> возводим результат в квадрат => получаем х 12 ,

К=> возводим результат в квадрат => получаем х 24 ,

Х=> умножаем результат на х =>получаем х 25

К=> возводим результат в квадрат => получаем x 50

К=> возводим результат в квадрат => получаем х 100 .

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

Например, при п = 49 учащиеся могут предложить такой эффективный алгоритм возведения в степень:

При реализации этого алгоритма было выполнено 7 операций умножения (вместо 48 операций при вы­числении "в лоб") и использовано 3 ячейки (для хранения переменной х , для хранения значения х 16 и для хране­ния текущего результата, получаемого на каждом шаге). Если же использовать алгоритм "Быстрого возведения в степень", то получим то же количество операций (7 операций умножения), но для реализации этого алгоритма потребуется только 2 ячейки (для хранения переменной х и для хранения текущего результата).

Сама операция умножения реализуется в процессоре не "в лоб", а опять же через эффективные рекурсивные алгоритмы. Об одном из таких алгоритмов вы можете прочитать в Хрестоматии. Мы же рассмотрим алгоритм "бы­строго" умножения, который был известен еще в Древнем Египте, его также называют "русским", или "крестьян­ским", методом. Разберем пример применения этого алгоритма.

Пример 2. Умножим 23 на 43 "русским" методом.

Ответ: 23 х 43 = 23 + 46 + 184 + 736 = 989.

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

Похожая информация.

Обозначение	Интуитивное объяснение	Определение
	f ограничена сверху функцией g	src="/pictures/wiki/files/101/eebfe73c29ff3f9bc886d263bd3e91f3.png" border="0"> или src="/pictures/wiki/files/100/d96907f9d7419a7e0c74e4089c35c35e.png" border="0">
	f ограничена снизу функцией g (с точностью до постоянного множителя) асимптотически	src="/pictures/wiki/files/48/0fda981f377ae7b8d361f58ce148c173.png" border="0">
	f ограничена снизу и сверху функцией g асимптотически	0), n_0: \forall (n>n_0) \; |Cg(n)|
	g доминирует над f асимптотически	src="/pictures/wiki/files/49/176ce786e936badb831a0bb87f25249d.png" border="0">
	f доминирует над g асимптотически	src="/pictures/wiki/files/53/554bc3f42cfa6d0638722e58e4a99d8b.png" border="0">
	f эквивалентна g асимптотически

Примеры

Замечания

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

Если решение некоторой задачи для n-вершинного графа при одном алгоритме занимает время (число шагов) порядка n C , а при другом - порядка n+n!/C, где C - постоянное число, то согласно «полиномиальной идеологии» первый алгоритм практически эффективен, а второй - нет, хотя, например, при С=10 (10 10) дело обстоит как раз наоборот.

1. Эффективные, но сложные алгоритмы могут быть нежелательными, если готовые программы будут поддерживать лица, не участвующие в написании этих программ. Будем надеяться, что принципиальные моменты технологии создания эффективных алгоритмов широко известны, и достаточно сложные алгоритмы свободно применяются на практике. Однако необходимо предусмотреть возможность того, что эффективные, но «хитрые» алгоритмы не будут востребованы из-за их сложности и трудностей, возникающих при попытке в них разобраться.
2. Известно несколько примеров, когда эффективные алгоритмы требуют таких больших объемов машинной памяти (без возможности использования более медленных внешних средств хранения), что этот фактор сводит на нет преимущество «эффективности» алгоритма.
3. В численных алгоритмах точность и устойчивость алгоритмов не менее важны, чем их временная эффективность.

Классы сложности

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

Класс P

Проблема равенства классов P и NP

Знаменитые ученые

• Леонид Левин
• Александр Разборов
• Эди Шеймир

См. также

Ссылки

• Юрий Лифшиц «Современные задачи теоретической информатики » . Курс лекций по алгоритмам для NP-трудных задач.
• А. А. Разборов Theoretical Computer Science: взгляд математика // Компьютерра . - 2001. - № 2. (альтернативная ссылка)
• А. А. Разборов О сложности вычислений // Математическое просвещение . - МЦНМО , 1999. - № 3. - С. 127-141.

Wikimedia Foundation . 2010 .

время выполнения программы для различных входных данных (параметра ).

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

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

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

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

Задача 5.4 линейную сложность .

Вот решение этой задачи, в котором переменные j и k содержат значения двух последовательных чисел Фибоначчи.

Текст программы

public class FibIv1 { public static void main(String args) throws Exception { int n = Xterm.inputInt("Введите n -> < 0) { Xterm.print(" не определено\n"); } else if (n < 2) { Xterm.println(" = " + n); } else { long i = 0; long j = 1; long k; int m = n; while (--m > 0) { k = j; j += i; i = k; } Xterm.println(" = " + j); } } }

Следующий вопрос вполне естественен - а можно ли находить числа Фибоначчи еще быстрее?

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

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

Текст программы

public class FibIv2 { public static void main(String args) throws Exception { int n = Xterm.inputInt("Введите n -> "); double f = (1.0 + Math.sqrt(5.)) / 2.0; int j = (int)(Math.pow(f,n) / Math.sqrt(5.) + 0.5); Xterm.println("f(" + n + ") = " + j); } }

На самом деле эта программа использует вызов функции возведения в степень { Math.pow(f,n) }, которая не может быть реализована быстрее, чем за логарифмическое время (). Про алгоритмы, в которых количество операций примерно пропорционально (в информатике принято не указывать основание двоичного логарифма) говорят, что они имеет логарифмическую сложность ().

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

Задача 5.5 . Напишите программу, печатающую -ое число Фибоначчи , которая имела бы логарифмическую сложность .

Текст программы

public class FibIv3 { public static void main(String args) throws Exception { int n = Xterm.inputInt("Введите n -> "); Xterm.print("f(" + n + ")"); if (n < 0) { Xterm.println(" не определено"); } else if (n < 2) { Xterm.println(" = " + n); } else { Matrix b = new Matrix(1, 0, 0, 1); Matrix c = new Matrix(1, 1, 1, 0); while (n>0) { if ((n&1) == 0) { n >>>= 1; c.square(); } else { n -= 1; b.mul(c); } } Xterm.println(" = " + b.fib()); } } } class Matrix { private long a, b, c, d; public Matrix(long a, long b, long c, long d) { this.a = a; this.b = b; this.c = c; this.d = d; } public void mul(Matrix m) { long a1 = a*m.a+b*m.c; long b1 = a*m.b+b*m.d; long c1 = c*m.a+d*m.c; long d1 = c*m.b+d*m.d; a = a1; b = b1; c = c1; d = d1; } public void square() { mul(this); } public long fib() { return b; } }

Если попробовать посчитать десятимиллионное число Фибоначчи с помощью этой и предыдущей программ, то разница во времени счета будет вполне очевидной. К сожалению, результат будет неверным (в обоих случаях) в силу ограниченности диапазона чисел типа long .

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

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

Также как из другими "навскидку" оценками (основанными на интуиции), суть в уже усвоенном опыте: в доступности строительных блоков, которыми вы можете оперировать бессознательно в выбранной области, благодаря целенаправленной практике.

Большинство кода имеет простую алгоритмическую структуру. И если знать оценку для распространённых блоков (алгоритмов и операций над структурами данных в вашей области), то сложность кода очевидна. В C++ сложность для стандартных алгоритмов явно указана. Знание только к какой из трёх категорий ввод относится (случайный доступ/ RandomAccessIterator, последовательный/ForwardIterator, однопроходной/InputIterator) уже достаточно во многих случаях, чтобы оценить сложность алгоритма.

Можно даже не знать как что-то конкретно реализовано. К примеру, если алгоритм на каком-то шаге требует сортировки случайных данных, то разумно предположить O(n log n) для алгоритма, основанного на сравнениях, вне зависимости от конкретной реализации. Или при поиске в таблице в базе данных, если строк много (когда о big O имеет смысл говорить), можно ожидать что добротная реализация индекс создаст (поиск из O(n) в O(log n) превращается). В случае сомнений, можно измерить .

Чтобы найти или проверить интуитивный ответ, можно рекуррентные выражения или частичные суммы построить, которые с помощью компьютера вычислить. Так как есть O(c*n) == O(n) и O(n*n + n) == O(n*n) и другие упрощающие преобразования, то многие алгоритмы можно свести к небольшому числу базовых случаев. Процесс требует внимательности, но достаточно прямолинеен (особенно если задействовать что-нибудь вроде wolframalpha, Maple, Maxima, sympy). How to find time complexity of an algorithm .

Соответственно есть случаи, когда концентрированные усилия, используя очевидные подходы, результат не дают, тогда стоит отвлечься на какое-то время, переключиться на другие задачи. Озарение может прийти в самый неожиданный момент (но это уже за рамками "навскидку").

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

Начните с самого простого кода на вашем языке, framework и узнайте его сложность (к примеру, "удаление по индексу элемента из массива"). Зная сложность для элементарных конструкций, найдите сложность для блоков кода (составленных из этих конструкций), с которыми вы часто встречаетесь.

Можно в обратную сторону: начать с более высокоуровневого кода и постепенно спускаться ниже по уровням абстракции, пока до известных блоков не дойдёте (сложение фиксированных чисел, которые в машинном слове помещаются: O(1). Если произвольное число n взять, то O(log n) - пропорционально количеству бит в числе). См. таблицу сложностей по времени .

Практикуйтесь, пока большинство повседневного интересного вам кода не сможете навскидку оценить.