Сложность этой программы О(N2)

Оценка алгоритмов Для большинства задач существует много различных алгоритмов. Какой из них выбрать для решения конкретной задачи? Чаще всего интересен порядок роста необходимых для решения задачи времени и емкости памяти при увеличении входных данных. Свяжем с каждой задачей некоторое число, называемое ее размером, которое выражало бы меру количества входных данных. Например, размером задачи умножения матриц, может быть наибольший размер матриц сомножителей. Размером задачи сортировки массива – количество чисел. Пространственная (или емкостная) сложность измеряется количеством памяти, требуемой для выполнения алгоритма. Временная сложность алгоритма определяется временем, необходимым для его выполнения. Лучший способ сравнения эффективностей алгоритмов состоит в сопоставлении их порядков сложности. Этот метод применим как к временной, так и пространственной сложности. Если алгоритм обрабатывает входные данные размера n за время cn2, где c – некоторая константа, то временная сложность этого алгоритма есть О(n2) (читается “порядка n2”).

Вопросы 1. Оценка алгоритмов 2. Алгоритмы поиска 2.1. Линейный поиск 2.2. Бинарный поиск 3. Преобразование массивов

ЛЕКЦИЯ 15.

Точнее, говорят, что неотрицательная функция f(n) есть O(g(n)), если существует такая константа с, что для для всех n из некоторой окрестности точки n ₀ имеет место неравенство f(n)<=c*g(n).
Обозначают
f(n) = O(g(n))
И функция f(n) есть о(g(n)), если для любого с>0 существует такая окрестность точки n ₀, что для для всех n из этой окрестности имеет место неравенство f(n)<c*g(n).
Обозначают
f(n) = о(g(n))
В формулах вместо знака = может использоваться знак принадлежности:
Существуют три важных правила для определения сложности.
1. O(k*f)=O(f)
2. O(f*g)=O(f)*O(g) или O(f/g)=O(f)/O(g)
3. O(f+g) равна доминанте O(f) и O(g).
Здесь k обозначает константу, a f и g - функции.

Первое правило декларирует, что постоянные множители не имеют значения для определения порядка сложности.
1,5*N=O(N)

Из второго правила следует, что порядок сложности произведения двух функций равен произведению их сложностей.
O((17*N)*N) = O(17*N)*O(N) = O(N)*O(N)=O(N*N) = O(N²)
Из третьего правила следует, что порядок сложности суммы функций определяется как порядок доминанты первого и второго слагаемых, т.е. выбирается наибольший порядок.
O(N⁵+N²)=O(N⁵)
O(1)
Большинство операций в программе выполняются только раз или только несколько раз. Это алгоритм константной сложности. Любой алгоритм, всегда требующий независимо от размера данных одного и того же времени, имеет константную сложность.
О(N)
Время работы программы линейно обычно когда каждый элемент входных данных требуется обработать лишь линейное число раз.
О(N²), О(N³), О(N^а)
Полиномиальная сложность. О(N²)-квадратичная сложность, О(N³)- кубическая сложность
О(Log(N))
Когда время работы программы логарифмическое, программа начинает работать намного медленнее с увеличением N. Такое время работы встречается обычно в программах, которые делят большую проблему в маленькие и решают их по отдельности.
O(N*log(N))
Такое время работы имеют те алгоритмы, которые делят большую проблему в маленькие, а затем, решив их, соединяют их решения.
O(2^N)
Экспоненциальная сложность. Такие алгоритмы чаще всего возникают в результате подхода именуемого метод грубой силы.

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

Например, рассмотрим алгоритм обработки элементов массива.
for (i=0;i<N;i++)
{
...
}
Сложность этого алгоритма O(N), т.к. тело цикла выполняется N раз, и сложность тела цикла равна O(1).

Если один цикл вложен в другой и оба цикла зависят от размера одной и той же переменной, то вся конструкция характеризуется квадратичной сложностью.
for (i=0;i<N;i++)
for (j=0;j<N;j++)
{
...
}

Дата добавления: 2014-01-07