Математическая логика и теория алгоритмов. Стенюшкина В.А. - 67 стр.

UptoLike

ВУЗ: 

ОГУ | Оренбург

Составители: 

Рубрика: 

(n-1)+с
7
(n-1)=аn+b; а=с
1
+с
2
+с
3
+с
4
+с
7
, b=-(с
2
+с
3
+с
4
+с
7
) и является линейной фун-
кцией размера входа.
Если массив на входе отсортирован в обратном порядке, то t
j
= j. Общее
время максимально: Т(n) = с
1
n+ с
2
(n-1)+с
3
(n-1)+с
4
(n(n-1)/2 – 1)+ с
5
(n-1)/2 +
с
6
(n-1)/2 +с
7
(n-1)=аn
2
+bn+c; а=с
5
/2+с
6
/2, в=с
1
+с
2
+с
3
+с
4
/2–с
5
/2–с
6
/2+с
7
, с=-(с
2
+с
3
+
с
4
с
7
); учтено, что ∑
j=2
n
j = n(n=1)/2 – 1, ∑
j=1
n
(j–1)=n(n=1)/2. Сама функция Т(n)
уже квадратичная.
Итак, мы рассмотрели худший и лучший случаи. В промежуточном слу-
чае, если считать, что в среднем около половины элементов массива А (1..(j–1))
больше А(j), и в строке 4 взять t
j
= j/2, то окажется, что среднее время квадрати-
чно зависит от размера входа – как и в худшем случае (конечно, коэффициенты
другие). Среднее время зависит от распределения вероятностей, которое может
не быть равномерным. Худшее время – максимальное время по всем входам.
Его нужно знать и как срок выполнения любого варианта вычислений и потому,
что оно имеет тот же порядок, что и среднее время довольно часто.
Функцию времени выполнения алгоритма оценивают по возможности
полиномам; если существует полином, эквивалентный функции времени при
n→∝, то порядок этого полинома называют порядком роста. Таким образом,
порядок роста работы алгоритма (процедуры) Sort_Ins равен двум. Алгоритм с
меньшим порядком считается более эффективным, для достаточно больших n,
время его выполнения меньше.
3.3 Асимптотика роста функций
Определение 1 Если f(n), g(n), n∈N – некоторые функции, то запись f(n)
=Θ(g(n)) означает, что существуют числа с
1
, с
2
>0 и n
0
∈N такие, что 0≤с
1
g(n)≤
f(n)≤ с
2
g(n) для всех n≥n
0
(здесь символ “=“ читается как “ есть “).
Пример – Проверить, что (1/4)n
2
-3n=Θ(n
2
).
Проверка – Требуемое неравенство имеет вид с
1
n
2
≤(1/4)n
2
-3n≤с
2
n
2
, n≥n
0
.
Это неравенство эквивалентно следующему: с
1
≤1/4-3/n≤с
2
, n ≥ n
0
. Второе нера-
венство, очевидно, выполняется при с
2
=1/4 и любого n
0
∈N. Первое неравенство
можно записать в виде n ≥3/(1/4-с
1
). Если с
1
=1/5, то достаточно взять n
0
= 60.
Если f(n)=Θ((n)), то g(n) называется асимптотически точной оценкой для
f(n). Заметим, далее, что если f(n) = Θ (g(n)), то и g(n)= Θ(f(n)).
Определение 2 Если f(n), g(n), n∈N – некоторые функции, то запись f(n) =
О(g(n)) означает, что существуют числа с > 0 и n
0
∈ N такие, что 0 ≤ f(n) ≤ с g(n)
для всех n ≥ n0.
Определение 3 Если f(n), g(n), n∈N – некоторые функции, то запись f(n) =
Ω (g(n)) означает, что существуют числа с > 0 и n
0
∈ N такие, что 0 ≤ сg(n) ≤ f(n)
для всех n ≥ n
0
.
Таким образом, Θ – обозначение используется для двусторонней оценки
(снизу и сверху), а О- и Ω- обозначения используются для односторонних оце-
нок. Для любых двух функций f(n), g(n), n∈N свойства f(n)= О(g(n)) и g(n)=Ω 
(n-1)+с7(n-1)=аn+b; а=с1+с2+с3+с4+с7, b=-(с2+с3+с4+с7) и является линейной фун-
кцией размера входа.
        Если массив на входе отсортирован в обратном порядке, то tj = j. Общее
время максимально: Т(n) = с1n+ с2 (n-1)+с3 (n-1)+с4 (n(n-1)/2 – 1)+ с5 (n-1)/2 +
с6(n-1)/2 +с7(n-1)=аn2+bn+c; а=с5/2+с6/2, в=с1+с2+с3+с4/2–с5/2–с6/2+с7, с=-(с2+с3+
с4 с7); учтено, что ∑j=2 n j = n(n=1)/2 – 1, ∑j=1 n (j–1)=n(n=1)/2. Сама функция Т(n)
уже квадратичная.
        Итак, мы рассмотрели худший и лучший случаи. В промежуточном слу-
чае, если считать, что в среднем около половины элементов массива А (1..(j–1))
больше А(j), и в строке 4 взять tj = j/2, то окажется, что среднее время квадрати-
чно зависит от размера входа – как и в худшем случае (конечно, коэффициенты
другие). Среднее время зависит от распределения вероятностей, которое может
не быть равномерным. Худшее время – максимальное время по всем входам.
Его нужно знать и как срок выполнения любого варианта вычислений и потому,
что оно имеет тот же порядок, что и среднее время довольно часто.
        Функцию времени выполнения алгоритма оценивают по возможности
полиномам; если существует полином, эквивалентный функции времени при
n→∝, то порядок этого полинома называют порядком роста. Таким образом,
порядок роста работы алгоритма (процедуры) Sort_Ins равен двум. Алгоритм с
меньшим порядком считается более эффективным, для достаточно больших n,
время его выполнения меньше.

       3.3 Асимптотика роста функций

       Определение 1 Если f(n), g(n), n∈N – некоторые функции, то запись f(n)
=Θ(g(n)) означает, что существуют числа с1, с2 >0 и n0∈N такие, что 0≤с1g(n)≤
f(n)≤ с2g(n) для всех n≥n0 (здесь символ “=“ читается как “ есть “).
       Пример – Проверить, что (1/4)n2-3n=Θ(n2).
       Проверка – Требуемое неравенство имеет вид с1n2≤(1/4)n2-3n≤с2n2, n≥n0.
Это неравенство эквивалентно следующему: с1≤1/4-3/n≤с2, n ≥ n0. Второе нера-
венство, очевидно, выполняется при с2=1/4 и любого n0∈N. Первое неравенство
можно записать в виде n ≥3/(1/4-с1). Если с1=1/5, то достаточно взять n0 = 60.
       Если f(n)=Θ((n)), то g(n) называется асимптотически точной оценкой для
f(n). Заметим, далее, что если f(n) = Θ (g(n)), то и g(n)= Θ(f(n)).
       Определение 2 Если f(n), g(n), n∈N – некоторые функции, то запись f(n) =
О(g(n)) означает, что существуют числа с > 0 и n0 ∈ N такие, что 0 ≤ f(n) ≤ с g(n)
для всех n ≥ n0.
       Определение 3 Если f(n), g(n), n∈N – некоторые функции, то запись f(n) =
Ω (g(n)) означает, что существуют числа с > 0 и n0 ∈ N такие, что 0 ≤ сg(n) ≤ f(n)
для всех n ≥ n0.
       Таким образом, Θ – обозначение используется для двусторонней оценки
(снизу и сверху), а О- и Ω- обозначения используются для односторонних оце-
нок. Для любых двух функций f(n), g(n), n∈N свойства f(n)= О(g(n)) и g(n)=Ω

Страницы