###
  • Интернет
  • Программы
  • Игры
  • Проблемы
  • Windows
  • Социальные сети
  • Android
  • Ios

    • Классификация и примеры алгоритмов определенной сложности. Виды функции сложности алгоритмов

    16.11.2021 Разное

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

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

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

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

    Не менее интересен и пример вычисления -го числа Фибоначчи . В процессе ее исследования фактически уже было выяснено, что ее сложность является экспоненциальной и равна . Подобные программы практически не применимы на практике. В этом очень легко убедиться, попробовав вычислить с ее помощью 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 .

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

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

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

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

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

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

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

    Определения

    Основным показателем сложности алгоритма является время, необходимое для решения задачи и объём требуемой памяти.
    Также при анализе сложности для класса задач определяется некоторое число, характеризующее некоторый объём данных – размер входа .
    Итак, можем сделать вывод, что сложность алгоритма – функция размера входа.
    Сложность алгоритма может быть различной при одном и том же размере входа, но различных входных данных.

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

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

    Порядок роста сложности алгоритмов

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

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

    Виды асимптотических оценок

    O – оценка для худшего случая

    Рассмотрим сложность f(n) > 0 , функцию того же порядка g(n) > 0 , размер входа n > 0 .
    Если f(n) = O(g(n)) и существуют константы c > 0 , n 0 > 0 , то
    0 < f(n) < c*g(n),
    для n > n 0 .

    Функция g(n) в данном случае асимптотически-точная оценка f(n). Если f(n) – функция сложности алгоритма, то порядок сложности определяется как f(n) – O(g(n)).

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

    Примеры асимптотических функций
    f(n) g(n)
    2n 2 + 7n - 3 n 2
    98n*ln(n) n*ln(n)
    5n + 2 n
    8 1
    Ω – оценка для лучшего случая

    Определение схоже с определением оценки для худшего случая, однако
    f(n) = Ω(g(n)) , если
    0 < c*g(n) < f(n)


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

    Θ – оценка для среднего случая

    Стоит лишь упомянуть, что в данном случае функция f(n) при n > n 0 всюду находится между c 1 *g(n) и c 2 *g(n) , где c – константный множитель.
    Например, при f(n) = n 2 + n ; g(n) = n 2 .

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

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

    Временная сложность при ЛВК определяется значением l(O p) , где O p – величина операнда.
    Ёмкостная сложность при ЛВК определяется значением l(M) , где M – величина ячейки памяти.

    Пример оценки сложности при вычислении факториала

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

    Void main() { int result = 1; int i; const n = ...; for (i = 2; i <= n; i++) result = result * n; }

    Временная сложность при равномерном весовом критерии

    Достаточно просто определить, что размер входа данной задачи – n .
    Количество шагов – (n - 1) .

    Таким образом, временная сложность при РВК равна O(n) .

    Временная сложность при логарифмическом весовом критерии

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

    Итак, в данной задаче выделяется три операции:

    1) i <= n

    На i-м шаге получится log(n) .
    Так как шагов (n-1) , сложность данной операции составит (n-1)*log(n) .

    2) i = i + 1

    На i-м шаге получится log(i) .
    .

    3) result = result * i

    На i-м шаге получится log((i-1)!) .
    Таким образом, получается сумма .

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

    Ёмкостная сложность при равномерном весовом критерии

    Здесь всё просто. Необходимо подсчитать количество переменных. Если в задаче используются массивы, за переменную считается каждая ячейка массива.
    Так как количество переменных не зависит от размера входа, сложность будет равна O(1) .

    Ёмкостная сложность при логарифмическом весовом критерии

    В данном случае следует учитывать максимальное значение, которое может находиться в ячейке памяти. Если значение не определено (например, при операнде i > 10), то считается, что существует какое-то предельное значение V max .
    В данной задаче существует переменная, значение которой не превосходит n (i) , и переменная, значение которой не превышает n! (result) . Таким образом, оценка равна O(log(n!)) .

    Выводы

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

    Обозначение Интуитивное объяснение Определение
    f ограничена сверху функцией g style="max-width: 98%; height: auto; width: auto;" src="/pictures/wiki/files/101/eebfe73c29ff3f9bc886d263bd3e91f3.png" border="0"> или style="max-width: 98%; height: auto; width: auto;" src="/pictures/wiki/files/100/d96907f9d7419a7e0c74e4089c35c35e.png" border="0">
    f ограничена снизу функцией g (с точностью до постоянного множителя) асимптотически style="max-width: 98%; height: auto; width: auto;" src="/pictures/wiki/files/48/0fda981f377ae7b8d361f58ce148c173.png" border="0">
    f ограничена снизу и сверху функцией g асимптотически 0), n_0: \forall (n>n_0) \; |Cg(n)|
    g доминирует над f асимптотически style="max-width: 98%; height: auto; width: auto;" src="/pictures/wiki/files/49/176ce786e936badb831a0bb87f25249d.png" border="0">
    f доминирует над g асимптотически style="max-width: 98%; height: auto; width: auto;" 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 .

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

      временная сложность (алгоритма) - — Тематики защита информации EN time complexity … Справочник технического переводчика

      СЛОЖНОСТЬ ОПЕРАТОРСКОЙ ДЕЯТЕЛЬНОСТИ - совокупность объективных факторов, влияющих на качество и продолжительность выполнения человеком требуемых функций в СЧМ. С. о. д. разделяется на несколько видов, каждый из которых характеризуется совокупностью факторов, определенным образом… … Энциклопедический словарь по психологии и педагогике

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

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

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

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

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

      - (GM) криптографическая система с открытым ключом, разработанная Шафи Голдвассером и Сильвио Микали в 1982 году. GM является первой схемой вероятностного шифрования с открытым ключом, доказуемо стойкая при стандартных криптографических… … Википедия Подробнее


    Глава 2. Сложность алгоритмов.

    2.1 Временная и вычислительная сложность алгоритмов.

    Временная сложность алгоритма (T (N ) , где N – размер задачи) – это время выполнения алгоритма, измеренное в шагах (инструкциях алгоритма, которые нужно выполнять для достижения результата). Т. е. это – число элементарных операций, из которых складывается алгоритм решения задачи (:=, <>, =, +, –, *, /; and, or, not, xor; call, return).

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

    https://pandia.ru/text/78/183/images/image002_151.gif" width="178 height=60" height="60">

    Случай T (N )= C * N 2 применим для квадратной матрицы.

    Элементарные операции в данном случае – совокупность «+» и «*».

    Если исходная матрица – единичная, то получаем Best Case.

    Если в матрице половина элементов – 0, половина – 1, то получаем Average Case.

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

    2.2 O и Ω – нотации.

    Характер поведения временной сложности при увеличении N (N ® ¥ ) называется асимптотической сложностью алгоритма.

    Для описания скорости роста асимптотической сложности используется О-нотация. Когда говорят, что временная сложность алгоритма имеет порядок N 2 :

    T (N )= O (N 2 )= O (f (N )),

    То подразумевается, что существуют положительные константы C , n0= const (C >0), такие, что для всех N ³ N 0 выполняется неравенство

    T (N ) £ C * f (N )

    Это – верхняя граница оценки сложности.

    Пример 2 :

    Пусть Т(0)=1, Т(1)=4, …, Т(N )=(N +1)­­­­2 , тогда временная сложность этого алгоритма имеет порядок роста T (N )= O (N 2 ).

    Можно показать, что для всех N > n 0 при n 0 = 1, C = 4 выполняется неравенство (1).

    (N +1)2 £ 4* N 2

    Пример 3 :

    Если временная сложность записывается в виде полинома

    T (N )= C 1 N 2 + C 2 N + C 3 ,

    то такой алгоритм имеет порядок сложности, кратный степени максимального элемента полинома, т. к. он растет наиболее быстро при N ® ¥ :

    T (N )= O (N 2 ).

    Например:

    3 n 2 +5 n +1 £ 5 n 2

    " n ³ 1

    Пример 4 :

    Если некоторый алгоритм имеет сложность, кратную 3 n , тогда можно показать, что порядок роста скорости не может быть кратен O (2 n ):

    T (N )=3 n ¹ O (2 n ).

    Пусть существуют константы C , n 0 , такие, что выполняются неравенство:

    3­­­­­ n £ C *2 n , n > n 0 .

    Отсюда получаем:

    С ³ (3/2)2, n > n 0 .

    Но при n ® ¥ не существует такой константы С , которая удовлетворяла бы данному неравенству.

    Кроме верхней границы сложности существует и нижняя граница скорости роста временной сложности:

    T (N ) ³ W (f (N ))

    Неравенство (2) подразумевает, что существует некоторая константа С , для которой при N ® ¥ временная сложность

    T (N ) ³ C * f (N ).

    Учитывая сложность точного определения T(N) (асимптотической временной сложности), в зависимости от размеров исходных данных на практике используют нижние и верхние границы временной сложности алгоритма:

    T (N ) = q (f (N ))

    В зависимости от значения константы С скорость роста сложности алгоритма может существенно меняться.

    Пример 5 :

    Пусть временная сложность записывается формулой

    T(N)=3n2 –100n+6=O(n2)

    3n2 >3n2 –100n+6, n ³ 1, C=3.

    Если С1 » 0 (С1=0,00001) , тогда неравенство

    10-5 n 2 > 3 n 2 –100 n +6, n ³ 1

    не выполняется.

    Но можно показать, что порядок роста сложности

    3n2 –100n+6 ¹ O(N).

    C*N < 3N2, N>C.

    3n2 –100n+6=(n2)

    C =2.29, n ³ n 0.

    2.99* n 2 < 3 n 2 –100 n +6

    Можно показать, что нижняя граница

    3 n 2 –100 n +6 ¹ W (n 3 ) при С=1.

    Неравенство 3 n 2 –100 n +6 ³ n 3 не выполняется.

    3 n 2 –100 n +6= W (n )

    C 1 = , n > n 0 .

    https://pandia.ru/text/78/183/images/image007_89.gif" width="305" height="247 src=">

    f 1 (N )=100 n 2

    f 2 (N )=5 n 3

    n 0 =20 – критическая точка.

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

    0 " style="margin-left:5.4pt;border-collapse:collapse;border:none">

    n !

    Пример 6:

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

    В этом случае алгоритм с быстро растущей сложностью может оказаться предпочтительнее для решения задач с малыми размерами данных (n ® 0 ).

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

    А1: 100 N

    А2: 100 N * logN

    А3: 10 N 2

    А4: N 3

    А5: 2 N

    Тогда для задач с N =2 ¸ 9 более быстродействующим будет А5 (f (N ) ~ 4 ¸ 512 ). Другие алгоритмы при подстановке дадут существенно более низкие показатели.

    При N =10 ¸ 58 предпочтительным оказывается А3.

    При N =59 ¸ 1024 самым эффективным будет А2.

    При N >1024 предпочтителен А1.

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

    Правило сумм : Пусть программа состоит из двух последовательно выполняющихся алгоритмов Р1 и Р2, для которых определены сложности O (f (n )) и O (g (n )) соответственно. Тогда временная сложность всей программы будет определяться как сумма временных сложностей каждого из алгоритмов:

    T (n ) = T 1 (n )+ T 2 (n )

    В общем случае получаем:

    T(n) Þ O(max f(n), g(n))

    Правило произведений: Пусть временная сложность программы, состоящей из двух параллельно выполняющихся алгоритмов, имеющих порядок сложности O (f (n )) и O (g (n )) соответственно, определяется как произведение временных сложностей каждого из алгоритмов:

    T (n ) = T 1 (n )* T 2 (n )

    В общем случае:

    T (n ) Þ O (f (n )* g (n ))

    Логарифмы.

    2.3. Рекурсия.

    Сложность рекурсивных алгоритмов оценить непросто в силу вложенности алгоритмических структур

    f (n ) Þ f (n * f (n -1))

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

    В общем случае T (n ) ~ O (N ).

    Другие рекурсивные алгоритмы в общем случае имеют временную сложность T (n ) ~ O (an ) , где a = const , что в результате дает суммарную сложность, большую, чем сложность не рекурсивного алгоритма решения этой же задачи.

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

    2.4.2 Алгоритмы восстановления зависимостей.

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

    Для построения аналитической зависимости сложности программы оценивают функцию T (N ) на некотором интервале [ Nmin , Nmax ] . Затем проводят аппроксимацию найденной кривой некоторой аналитической функции с изменением параметров функции и оценкой ошибки аппроксимации.

    Как правило, в качестве такой функции используют известные функции временной сложности: O (n !), O (XN ), O (NX ), O (logN ), O (https://pandia.ru/text/78/183/images/image010_72.gif" width="307" height="225 src=">В результате эксперимента над программой была получена таблица временных сложностей:

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

    https://pandia.ru/text/78/183/images/image012_68.gif" width="321" height="143 src=">

    Пример 2:

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

    В этом случае строят семейство функций аппроксимации и находят аналитически сложность алгоритма.

    Трудоемкость" href="/text/category/trudoemkostmz/" rel="bookmark">трудоемкостью (временем работы).

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

    Говорят, что алгоритм является полиномиальным, если время его работы, т. е. временная сложность, ограничивается сверху полиномом некоторой степени T (N )= O (Nm ) . Тогда все задачи, которые решаются таким алгоритмом, образуют Р-класс задач. Говорят, что эти задачи входят в Р.

    Задачи, временная сложность которых экспоненциальна (T (N )= O (K N ) ), не входят в Р.

    Замечание : Можно показать, что задачи с линейной сложностью входят в Р

    T (N )= O (N 1 )

    Введем класс NP-задач, которые можно решить за полиномиальное время с помощью недетерминированного алгоритма.

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

    В недетерминированном алгоритме (НДА) для любого данного состояния может быть больше одного допустимого следующего состояния, т. е. такой алгоритм в каждый момент времени может выполнить больше одного оператора.

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

    Пример :

    Детерминированный алгоритм (ДА) решал бы эту задачу последовательно (перебор всех вариантов, сравнение с критерием оптимальности K0 до тех пор, пока не выберет альтернативу А0).

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

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

    Т. о. НДА характеризуется тремя параметрами:

    1. выбор – многозначная функция, значения которой являются элементами множества S;

    2. неудача заставляет копию алгоритма прекратить работу;

    3. успех заставляет все копии алгоритма прекратить работу и сформировать результат.

    Очевидно, что никакое физическое устройство не способно на неограниченное недетерминированное поведение, значит, НДА является теоретическим методом.

    Задачи, которые можно решить с помощью полиномиального НДА, образуют класс NP-задач.

    2.5.2 NP -трудные и NP -полные задачи.

    Задача, входящая в Р, является NP -трудной , если существует полиномиальный ДА (ПДА) ее решения, который модно использовать для получения решения всех задач, входящих в NP. Т. е. такая задача является NP-трудной, если она, по крайней мере, так же трудна, как любая задача, входящая в NP.

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

    Для доказательства того, что задача является NP-трудной, необходимо показать, что если для задачи существует ПДА, то его можно использовать для получения другого ПДА решения задач, входящих в NP.

    Чтобы установить, что задача является NP-полной, необходимо доказать, что она принадлежит NP.

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

    Определение 1 : Задача Р1 преобразуется в задачу Р2, если любой частный случай задачи Р1 можно преобразовать за полиномиальное время в некоторый частный случай задачи Р2. Тогда решение Р1 можно получить за полиномиальное время из решения частного случая задачи Р2.

    https://pandia.ru/text/78/183/images/image024_39.gif" width="158 height=56" height="56">

    Например:

    f 2 (xi )=(x 1 Ú x 2 ) Ù ( ) Ù ()

    не является выполнимой, т. к. при любых xi f 2 (xi )= false .

    Теорема :

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

    xi выбор (true, false)

    if E(x1, x2, …, xN) then успех

    else неудача

    Используя преобразование задачи Р1 в Р2, можно показать, что даже ограниченный случай задачи о выполнимости является NP-полным.

    К-выполнимость .

    К-выполнимость означает, что любой дизъюнкт, входящий в КНФ, содержит не более К логических переменных.

    Минимальный случай К=3. Для булевской функции, представленной в КНФ, за полиномиальное время можно найти функцию Е*(х2) , содержащую не более трех переменных в каждом дизъюнкте. Тогда Е выполнима, если выполнима Е*.

    E * (x 1 , x 2 ,…, xn ) ® E * (xi )

    Для этого используется метод уменьшения порядка дизъюнкта

    (a 1 Ú a 2 Ú … Ú a k )=(a 1 Ú a 2 Ú z ) Ù (a 3 Ú a 4 Ú … Ú a k Ú )

    Применяя итерационный процесс разложения, можно получить Е* .

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

    Частный случай: при К=2 функция Е входит в Р.

    Примерами задач NP-класса могут послужить также задачи на графах :

    1) Определение максимума клик неориентированного графа (NP-трудная задача).

    2) Задача определения полного подграфа (NP-полная задача).

    3) Определение вершинного покрытия мощности L для неориентированного графа (NP-полная задача).

    4) Определение максимума вершинных покрытий неориентированного графа (NP-трудная задача).

    5) Задача определения существования Гамильтонова цикла для графа (NP-полная задача).

    6) Задача коммивояжера: определение оптимального движения по графу с единым вхождением в каждую вершину (NP-трудная задача).

    7) Задача составления расписания (NP-полная задача).

    2.6 Алгоритмически неразрешимые проблемы

    Разделяют проблемы одиночные и массовые .

    Например:

    5+7=? – одиночная проблема.

    х+у=? – массовая проблема.

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

    Например, парадоксами являются:

    Пример 1:

    10-ая проблема Гильберта.

    Д. Гильберт в 1901 г. при решении диофантовых уравнений выдвинул проблему, которая гласит:

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

    F (x , y , …)=0

    Это – полином с целыми показателями степеней и целыми коэффициентами при неизвестных

    anxn+an-1xn-1+…+a2x2+a1x+a0=0

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

    В 1970 г. ленинградский математик Ю. Матиясевич математически доказал алгоритмическую невозможность решения диофантового уравнения в общем виде.

    Пример 2:

    Теорема Ферма:

    Не существует таких целых чисел a , b , с, n (n >2) , для которых справедливо равенство

    an + bn = cn

    Эта теорема была доказана для многих значений n и проверена для частных случаев, однако до сих пор не создано общее доказательство теоремы.

    Пример 3:

    Проблема Гольдбаха.

    Х. Гольбах в 1742 г. в письме к Эйлеру сформулировал проблему:

    Доказать, что каждое целое число N ³ 6 может быть представлено в виде суммы трех простых чисел

    N = a + b + c

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

    Частый случай решения этой проблемы предложил Эйлер: для четных N эта проблема разрешима и равносильна разложению на два простых слагаемых.

    И. Виноградов в 1937 г. доказал, что для нечетных N можно найти три простых слагаемых, но для четных чисел решение не найдено до сих пор.

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

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

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

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

    Как правило, временная сложность алгоритма зависит от исходных данных. Это может быть зависимость как от величины исходных данных, так и от их объема. Если обозначить значение параметра временной сложности алгоритма α символом Tα, а буквой V обозначить некоторый числовой параметр, характеризующий исходные данные, то временную сложность можно представить как функцию Tα(V). Выбор параметра V зависит от решаемой задачи или от вида используемого алгоритма для решения данной задачи.

    Пример 1. Оценим временную сложность алгоритма вычисления факториала целого положительного числа.

    Function Factorial(x:Integer): Integer;

    Var m,i: Integer;

    For i:=2 To x Do m:=ro*i;

    Подсчитаем общее число операций, выполняемых программой при данном значении x. Один раз выполняется оператор m:=1; тело цикла (в котором две операции: умножение и присваивание) выполняется х - 1 раз; один раз выполняется присваивание Factorial:=m. Если каждую из операций принять за единицу сложности, то временная сложность всего алгоритма будет 1 + 2 (x - 1) + 1 = 2х Отсюда понятно, что в качестве параметра следует принять значение х. Функция временной сложности получилась следующей:

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

    Пример 2. Вычисление скалярного произведения двух векторов А = (a1, a2, …, ak), В = (b1, b2, …, bk).

    For i:=l To k Do AB:=AB+A[i]*B[i];

    В этой задаче объем входных данных п = 2k. Количество выполняемых операций 1 + 3k = 1 + 3(n/2). Здесь можно взять V= k= п/2. Зависимости сложности алгоритма от значений элементов векторов А и В нет. Как и в предыдущем примере, здесь можно говорить о линейной зависимости временной сложности от параметра данных.

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

    Вторая проблема связана с классификацией алгоритмов по временной сложности. Функция Tα(V) обычно растет с ростом V. Как быстро она растет? Существуют алгоритмы с линейной зависимостью Тα от V (как это было в рассмотренных нами примерах), с квадратичной зависимостью и с зависимостью более высоких степеней. Такие алгоритмы называются полиномиальными. А существуют алгоритмы, сложность которых растет быстрее любого полинома. Проблема, которую часто решают теоретики - исследователи алгоритмов, заключается в следующем вопросе: возможен ли для данной задачи полиномиальный алгоритм?

    Функции, часто встречающиеся при анализе алгоритмов:

    • log n (логарифмическое время),
    • n (линейное время),
    • n log n ,
    • n 2 (квадратичное время),
    • 2 n (экспоненциальное время).

    Первые четыре функции имеют невысокую скорость роста и алгоритмы, время работы которых оценивается этими функциями, можно считать быстродействующими. Скорость роста экспоненциальной функции иногда характеризуют как «взрывную». Для сравнения допустим, что имеются алгоритмы, трудоемкость которых (число операций) достаточно точно отражается этими функциями. Пусть эти алгоритмы выполняются на компьютере, работающем со скоростью 10 12 операций в секунду. При длине входа n ≤ 100000 алгоритмы, скорость работы которых оценивается первыми четырьмя функциями, получат ответ за ничтожные доли секунды. Для алгоритма с трудоемкостью 2 n время работы оценивается следующим образом:

    • n = 50 ≈ 19 минут,
    • n = 60 ≈ 320 часов,
    • n = 70 ≈ 37 лет.

    Вопрос 15=49. Последовательные, циклические и рекурсивные алгоритмы.

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

    Пример. Вычислить периметр треугольника со сторонами a,b,c.13

    Алгоритм разветвляющейся структуры

    На практике редко удается представить решение задачи в виде алгоритма

    линейной структуры. Часто в зависимости от каких-либо промежуточных

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

    формулам, т.е. в зависимости от выполнения некоторого логического условия

    вычислительный процесс осуществляется по одной или другой формуле.

    Алгоритм такого вычислительного процесса называется алгоритмом

    разветвляющейся структуры.

    Ветвление - управляющая структура, организующая выполнение лишь

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

    некоторого условия.

    Условие - вопрос, имеющий два варианта ответа: да или нет.

    Запись ветвления выполняется в двух формах: полной и неполной (Рис. 1 а, б).

    а) полная форма б) неполная форма

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

    алгоритма и длину соответствующей ей программы. Различают циклы с

    заданным и неизвестным числом повторений. С заданным числом повторений -

    цикл со счетчиком. С неизвестным числом повторений - цикл с предусловием,

    цикл с постусловием.

    Функция (или процедура), которая прямо или косвенно обращается к себе, называется рекурсивной. Рекурсия - метод определения функции через её предыдущие и ранее определенные значения, а так же способ

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

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

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

    – условие для завершения цикла;

    – тело рекурсии, которое включает действия, предназначенные для

    выполнения на каждой итерации;

    – шаг рекурсии, на котором рекурсивный алгоритм вызывает сам себя.

    Различают прямую и косвенную рекурсию. В первом случае алгоритм

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

    называется косвенно рекурсивной.

    Основное требование к рекурсивным алгоритмам – процесс обращения не

    должен быть бесконечным. Другими словами, должна быть реализована

    проверка завершения вызова, или в рекурсивном определении должно

    присутствовать ограничение, при котором дальнейшая инициализация

    рекурсии прекращается.

    Примером рекурсивной функции является вычисление факториала числа.

    int factoria(int n)

    if (n) return n* factoria(n-1);

    else return 1;

    Пример рекурсивной процедуры:

    procedure Rec(a: integer); begin if a>0 then Rec(a-1); writeln(a); end;

    Рассмотрим, что произойдет, если в основной программе поставить вызов, например, вида Rec(3). Ниже представлена блок-схема, показывающая последовательность выполнения операторов.