8

Глава 3. Размер задачи. Сложность алгоритма

3.1. Размер задачи. Скорость роста

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

а) при проверке, будет ли заданное число простым или составным, характерным является само число,

б) при поиске максимального элемента массива - длина массива.

При вводе в ЭВМ исходные данные кодируются каким–либо способом. Числовые данные обычно представляют в позиционных системах счисления. Символьная информация задаётся в стандартных кодах либо в специальном графическом представлении.

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

Размером задачи называют длину последовательности символов, в которой закодированы все исходные данные.

Для ЭВМ размер памяти обычно оценивается числом байтов – последовательностей из восьми бинарных разрядов.

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

Рассмотрим на множестве натуральных чисел N функции f(n) и g(n).

1. Функции g(n) и f(n) имеют одинаковую скорость роста, если при всех достаточно больших n, начиная с некоторого n₀, выполняется условие:

С₁ f(n) ≤ g(n)≤ С₂ f(n), где С₁>0,С₂>0 – некоторые константы.

2. Скорость роста функции g(n) больше скорости роста функции f(n), если для любой сколь угодно большой константы С существует некоторое n₀, начиная с которого выполняется условие:

С f(n) ≤ g(n).

3. Скорость роста функции g(n) ограничена снизу скоростью роста функции f(n), если при всех достаточно больших n, начиная с некоторого n₀, выполняется:

С f(n) ≤ g(n), где С – константа.

4. Скорость роста функции g(n) ограничена сверху скоростью роста функции f(n), если при всех достаточно больших n, начиная с некоторого n₀, выполняется условие:

g(n) ≤ С f(n), где С – константа.

Данное определение позволяет сравнивать между собой скорости роста функций достаточно произвольного вида – как имеющих, так и не имеющих предел отношения g(n)/f(n) при n  .

Замечание. Если скорость роста функции g(n) равна скорости роста функции f(n), то скорость роста f(n) ограничивает скорость роста g(n) и сверху и снизу.

Пример 1. Рассмотрим задачу с характерным параметром n, у которой входными данными являются все простые делители числа n, не равные единице. С увеличением n число делителей k(n) будет постоянно изменяться в пределах от 1 (у простого числа) до log₂n (у степеней 2). Поэтому для длины входа k(n) не существует элементарной монотонной функции с одинаковой скоростью роста. Для неё можно только лишь указать ограничения, верные при любых n: 1≤ k(n) ≤ log₂n.

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

1) не существует монотонной функции f(n) со скоростью роста, равной k(n), но при всех n, начиная с некоторого n₀, возможны лишь оценки:

C_н f_н(n) ≤ k(n) ≤ C_в f_в(n),

где C_н>0, C_в>0 – нижняя и верхняя константы, f_н(n), f_в(n) – различные функции.

2) существует монотонная функция f(n), имеющая одинаковую скорость роста с k(n), для которой по определению при всех n, начиная с некоторого n₀, выполняется:

C_н f(n) ≤ k(n) ≤ C_в f(n),

где C_н, C_в – константы,

В варианте 2) предел отношения k(n)/f(n) при n  может:

а) не существовать и

б) существовать, при этом:

Случай 2 б) является наиболее распространенным при анализе скорости роста реальных функций натурального параметра. Константу С_р в приведенном выше пределе назовем константой скорости роста, а соответствующую скорость роста – устойчивой.

Функции g(n), зависящие от натурального параметра n, могут иметь любой вид, однако скорости их роста f(n) для большей наглядности и упрощения сравнений выражают через модельные элементарные функции (логарифмы, степенные, показательные и др) либо их произведения. Наиболее часто используют степенные функции n^α. При α = 1 скорость роста функции n^α называют линейной, при α = 2 – квадратичной, при α =3 – кубической и т.д. Все скорости роста вида n^α называют полиномиальными. С увеличением показателя α полиномиальная скорость роста также возрастает.

Существуют функции, скорости роста которых превосходят при n→ ∞ любую (со сколь угодно большим показателем α) полиномиальную скорость. Например, 2ⁿ, еⁿ, n!. Скорости такого типа называют экспоненциальными.

Из двух функций g₁(n), g₂(n) с одинаковой устойчивой скоростью роста f(n) меньшие значения в пределе будет иметь функция с меньшей константой скорости роста С_р.

Пример 2. Определить скорость роста f(n) функции g₁(n)=(n–5)/3, константу скорости роста С_р, а также определить пороговое значение параметра n₀ и константы С₁ , С₂, при которых справедливо соотношение: С₁ f(n) ≤ g(n) ≤ С₂ f(n).

Решение. Так как при n предел отношения g₁(n)/n существует и равен 1/3, то скорость роста функции g₁(n) равна линейной полиномиальной f(n)=n¹, а константа скорости роста С_р =1/3.

Определим параметры n₀, С₁, С₂. Для этого используем следующие соотношения :

(1/6) n ¹  (n-5)/3  (1/3)  n ¹.

Правое неравенство очевидно и выполняется при любых n, константа (1/6) в левой части задана произвольно из условия (1/6) < (1/3), величину n₀ определим из левого неравенства:

(1/6) n¹  (n – 5)/3  3 n  6 n – 30  3 n  30 n  10.

Ответ: f(n)=n¹, С_р =1/3, n₀ =10, С₁ = 1/6, С₂ =1/3.

Пример 3. Определить скорость роста f(n) функции g₂(n)=0,25(n–1)(n+2), константу скорости роста С_р, а также определить пороговое значение параметра n₀ , нижнюю и верхнюю константы С₁ , С₂ , при которых справедливо соотношение С₁ f(n)≤ g(n) ≤ С₂ f(n).

Решение. При n предел отношения g₂(n)/n² существует и равен 1/4. Следовательно, скорость роста функции g₂(n) равна квадратичной полиномиальной f(n)=n², С_р =1/4.

Определим n₀ , С₁ , С₂ . Для этого используем соотношение

n²/4  0,25(n–1)(n+2)  n²/3.

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

Левая часть:

n²/4  0,25 (n–1)(n+2) n² n²+n –2  n  2  n₀ =2.

Правая часть:

0,25(n–1)(n+2) n²/3 3n²+3n–6  4n²  n²–3n+6  0.

Так как дискриминант уравнения отрицательный, то данное неравенство справедливо при любых n.

Ответ: f(n)=n², С_р =1/4, n₀ =2, С₁ = 1/4, С₂ =1/3.

Обозначим скорость роста размера задачи через r(n). Рассмотрим примеры её определения.

Пример 4. При проверке, будет ли число n простым или составным, r(n) задачи определяется длиной записи самого числа n. В позиционной системе с основанием р число бит, в записи числа n равно ]log_р n[, а размер задачи в байтах r(n)=]log_р n[/8.

Пример 5. Задача коммивояжера (ЗК). Задано n упорядоченных населенных пунктов {vⁿ}={v₁, v₂, ... , v_n}. Все расстояния между ними известны и заданы симметричной матрицей стоимости С размером n  n, элементы которой удовлетворяют неравенству треугольника, т.е. при любых i, j, k, лежащих в пределах 1≤ i, j, k ≤ n, справедливы соотношения: с _{i j} = с _{j i} ; с _{i j} + с _{j k} ≥ с _{i k} .

Коммивояжеру требуется выбрать из всего множества циклических обходов {О (vⁿ )} пунктов {vⁿ}, такой обход Оⁿ_опт, у которого общая длина

_n-1

L(Оⁿ_опт)= ∑ с _{i j, i (j+1)} + с _{i n, i 1}

^j=1

будет минимально возможной.

В задаче изо всех исходных данных наиболее быстро (n²) растёт число элементов симметричной матрицы стоимости С размером nn. Поэтому скорость роста размера данной задачи будет квадратичной полиномиальной – r(n)= n².

Вопросы для проверки знаний.

1. Что называют размером задачи и в каких единицах ее измеряют в ЭВМ ?

2. Что означает, что функции g(n) и f(n) имеют одинаковую скорость роста ?

3. Что означает, что скорость роста одной функции больше скорости роста другой функции ?

4. Что означает, что скорость роста функции g(n) ограничена снизу скоростью роста функции f(n) ?

5. Могут ли значения функции g(n), у которой скорость роста ограничена сверху скоростью роста функции f(n), превышать значения данной функции ?

6. В каком случае скорость роста функции называют устойчивой и что называют константой скорости роста ?

7. Какие скорости роста функций называют полиномиальными, линейными, квадратными и кубическими ?

8. Какие скорости роста функций называют экспоненциальными ?

Практические задания.

1. Определить постоянную скорость роста f(n) функции g(n) =5(n-1)(n+3)/(n+5), константу скорости роста С_р , а также найти значения n₀ , С₁ , С₂ , при которых справедливо соотношение С₁ f(n) ≤ g(n) ≤ С₂ f(n).

2. Найти скорость роста f(n) и константы скорости роста С_р функций:

а) g₁(n)=0,1 (n! – 2n²+ 3n+ 10)/(3n–1);

б) g₂(n)=(еⁿ+ 3n¹⁰+ 7)(4n³ -6n² + 2n + 5);

в) g₃(n)= 2ⁿ+ n ⁿ – n² .

3. Доказать, что:

а) скорость роста функции n! превосходит в пределе при n→∞ скорость роста функции 2ⁿ ;

б) скорость роста функции 2ⁿ превосходит в пределе при n→ ∞ любую (со сколь угодно большим показателем α) скорость роста полиномиальной функции n^α .

4. Выяснить для функции скорости роста f(n) = n²(1+(–1)ⁿ) + 2n+1:

а) устойчивость скорости роста,

б) ограниченность снизу,

в) ограниченность сверху.