Единое окно доступа к образовательным ресурсам

Теория алгоритмов: Учебное пособие

Голосов: 3

В пособии содержится материал спецкурса, читаемого автором в последние годы на механико-математическом факультете ТГУ для студентов специализации "Компьютерная математика". Основные разделы: алгоритмы и вычислимые функции, ламбда-исчисление. вычислимое и невычислимое, формальные аксиоматические теории, элементарная арифметика и неполнота, сложность вычислений. NP-полнота. Предназначено для преподавателей математики и компьютерных наук, а также для студентов высших учебных заведений.

Приведенный ниже текст получен путем автоматического извлечения из оригинального PDF-документа и предназначен для предварительного просмотра.
Изображения (картинки, формулы, графики) отсутствуют.
    В построении следующей последовательности повторяется применение оператора Fb с
последующим вычитанием 1. Первые девять членов суть

G0(266)   =             ( 22+1 )
              266 = 2              + 2 2+1 + 2
G1(266)   =                        (33+1 )
            F2(266)–1 = 3           + 33+1 + 2
          = 443426488243037769948249630619149892886
            (39 цифр)
G2(266)   =                      ( 44+1)
            F3(G1(266))–1 = 4            + 4 4+1 + 1
          = 3231700607…853611059596231681 (617 цифр)
G3(266)   =                      (55+1 )
            F4(G2(266))–1 = 5            + 55+1 (10922 цифры)
G4(266)   =                      (66+1 )
            F5(G3(266))–1 = 6            + 6 6+1 − 1
          =     6+1
            6 (6 ) + 5 ⋅ 6 6 + 5 ⋅ 6 5 + ... + 5 ⋅ 6 + 5 ≈ 4⋅10217832
G5(266)   = F6(G4(266))–1
          =     7 +1
            7 (7 ) + 5 ⋅ 7 7 + 5 ⋅ 7 5 + ... + 5 ⋅ 7 + 4 ≈ 104871822
G6(266)   = F7(G5(266))–1
          = 888+1 + 5⋅88 + 5⋅85 +… + 5⋅8 + 3 ≈ 2⋅10121210686
G7(266)   = F8(G6(266))–1
          = 999+1 + 5⋅99 + 5⋅95 +… + 5⋅9 + 2 ≈ 5⋅103327237896
G8(266)   = F9(G7(266))–1
          = 101010+1 + 5⋅1010 + 5⋅105 +… + 5⋅10 + 1 ≈ 101011

Последовательность {Gk(n)} называется последовательностью Гудстейна.
Теорема 25. (Гудстейн).
Для любого n существует такое k, что Gk(n) = 0.
       Кажется невероятным, но это так. А чтобы в это поверить, мы рекомендовали бы
читателю проделать вышеописанную процедуру, для начала – с числом «3».
G0(3) = 2 + 1
G1(3) = F2(3) –1 = 3
G2(3) = F3(G1) –1 = 4 – 1 = 3
G3(3) = F4(G2) –1 = 2
G4(3) = F5(G3) –1 = 1
G5(3) = F6(G6) –1 = 0

        Попробуем проверить утверждение теоремы для n=4:
22
33 – 1 = 2×32+2×3+2
2×42+2×4+1
2×52+2×5
2×62+ 6 +5
2×72+ 7 +4
2×82+ 8 +3
2×92+ 9 +2
2×102+ 10 +1
2×112+ 11
2×122+ 12–1 = 2×122 + 11
2×132 + 10


…
2×232
2×242 – 1 = 242 + 23×24 + 23
252 + 23×25 + 22
…
472 + 23×47
482 + 23×48 – 1 = 482 + 22×48 + 47
492 + 22×49 + 46
…
952 + 22×95
962 + 22×96–1 = 962 + 21×96 + 95
972 + 21×97 + 94
…
1912 + 21×191
1922 + 21×192–1 = 1922 + 20×192 + 191
1932 + 20×193 + 190
…
3832+20×383
3842+20×384–1 = 3842+19×384+383
3852+19×385+382
…
7672+19×767
7682+19×768–1 = 7682+18×768+767
7692+18×769+766
…
15352+18×1535
15362+18×1536–1 = 15362+17×1536+1535
15372+17×1537+1534
…
…
…
       Эта последовательность доходит до числа из 121 210 695 цифр (для сравнения
заметим, что 1000000! содержит около 5 с половиной миллионов цифр), но потом числа
только уменьшаются (так как уже не содержат в наследственном представлении
основания) вплоть до 0. Gk(4) впервые достигает 0 для k=3(2402653211-1) ≈ 10121210695.
       Набросок доказательства теоремы Гудстейна
       Будем использовать трансфинитные ординалы.7 Пусть, как обычно, ω обозначает
ординал, равный порядковому типу множества натуральных чисел; а ординал ε0
                           ω
обозначает sup(ω , ω ω , ω ω ,...) .
      Для любого натурального числа n и любого основания b пусть Bb(n) обозначает
выражение, полученное из наследственного представления числа n по основанию b, после
синтаксической замены b на ординал ω. Например, так как наследственное представление
               2 +1                ω +1
266 есть 2 2 + 22 + 2, то B2(266) = ω ω + ωω + ω.
       Очевидно, Bb(n) есть ординал, меньший ε0 и представленный в виде
«экспоненциального полинома» относительно ω (канторова нормальная форма).
       Имеем следующие свойства (для любых натуральных n и m и любого основания
b>1):
       1. Bb(n)=0 ⇔ n=0;

7
    См., например, [18].


       2. m < n ⇔ Bb(m) < Bb(n);
       3. Bb(n) = Bb+1(Fb(n)) (поскольку в правой части основание b в наследственном
          представление n сначала заменяется на b+1, а потом b+1 заменяется на ω).
       Зафиксируем n>0 и пусть g0, g1, g2, … – последовательность Гудстейна для данного
числа n, т.е. gk = Gk(n) при k=0,1,2,… Определим теперь соответствующую
последовательность ординалов a0, a1, a2, … по правилу ak = Bk+2(gk) при k=0,1,2,… Пусть
для всех k=0,1,2,… выполнено gk > 0. Придем к противоречию, и тем самым теорема будет
доказана.
       Сравним ak и ak+1. Имеем gk+1 = Fk+2(gk)-1 (здесь как раз используется
предположение, что последовательность Гудстейна не содержит 0), поэтому

       ak+1 = Bk+3(gk+1) = Bk+3(Fk+2(gk)-1) < Bk+3(Fk+2(gk)) = (по свойству (3)) Bk+2(gk) = ak.

Проиллюстрируем предыдущее неравенство на примере:
                                     2 +1                                   ω +1
Пусть n=266. Тогда g0 = 266 = 2 2           + 22 + 2, и a0 = B2(g0) = ω ω          + ωω + ω.Также имеем g1
    3+1                             ω +1
= 33  + 33 + 2, и a1 = B3(g1) = ω ω + ωω + 2. Очевидно, a1< a0.
      Таким образом, получили бесконечную убывающую последовательность
ординалов a0 > a1> > a2 > a3 > … , что невозможно.
      Гудстейн доказал теорему в 1944 году, используя трансфинитную индукцию [3]. В
1982 году Л. Кирби и Дж. Парис получили результат о том, что теорема Гудстейна
формально недоказуема в рамках аксиоматической системы элементарной арифметики
[4].


5 Сложность вычислений
      Применение математики во многих приложениях требует, как правило,
использования различных алгоритмов. Для решения многих задач не трудно придумать
комбинаторные алгоритмы, сводящиеся к полному перебору вариантов. Но здесь вступает
в силу различие между математикой и информатикой: в информатике недостаточно
высказать утверждение о существовании некоторого объекта в теории и даже
недостаточно найти конструктивное доказательство этого факта, т.е. алгоритм. Мы
должны учитывать ограничения, навязываемые нам миром, в котором мы живем:
необходимо, чтобы решение можно было вычислить, используя объем памяти и время,
приемлемые для человека и компьютера.
      Если дана задача, как найти для её решения эффективный алгоритм? А если
алгоритм найден, как сравнить его с другими алгоритмами, решающими ту же задачу? Как
оценить его качество? Вопросы такого рода интересуют и программистов, и тех, кто
занимается теоретическим исследованием вычислений.
      Введем в первую очередь некоторые понятия, связанные с асимптотической
оценкой функций.

5.1 Асимптотические обозначения
      Введем в первую очередь обозначение, связанное с асимптотической оценкой
функций. Хотя во многих случаях эти обозначения используются неформально, полезно
начать с точных определений [13]. На протяжении этого раздела встречающиеся в тексте
функции отображают целые числа в действительные.

Θ–обозначение
Если f(n) и g(n) – некоторые функции, то запись f(n) = Θ(g(n)) означает, что найдутся
такие c1, c2 > 0 и такое n0, что 0 ≤ c1g(n) ≤ f(n) ≤ c2g(n) для всех n ≥ n0.
В этом случае говорят, что g(n) является асимптотически точной оценкой для f(n).

        Разумеется, это обозначение следует употреблять с осторожностью: Установив, что
f1(n) = Θ(g(n)) и f2(n) = Θ(g(n)), не следует заключать, что f1(n) = f2(n)!
        Определение Θ(g(n)) предполагает, что функции f(n) и g(n) асимптотически
неотрицательны, т.е. неотрицательны для достаточно больших значений n. Заметим, что
если f и g строго положительны, то можно исключить n0 из определения (изменив
константы c1 и c2 так, чтобы для малых n неравенство также выполнялось).
        Это отношение симметрично: если f(n) = Θ(g(n)), то g(n) = Θ(f(n)).
        Пример. Проверим, что (1/2)n2–3n = Θ(n2). Согласно определению надо указать
положительные константы c1, c2 и число n0 так, чтобы неравенства
                                       c1n2 ≤ n2/2 – 3n ≤ c2n2
выполнялось для всех n≥n0. Разделим на n2:
                                               1 3
                                           c1≤ − ≤ c2.
                                               2 n
Видно, что для выполнения второго неравенства достаточно положить c2 = ½. Первое
будет выполнено, если, например, n0 = 7 и c1 = 1/14.
        Другой пример использования формального определения: покажем, что 6n3 ≠ Θ(n2).
В самом деле, пусть найдутся такие c2 и n0, что 6n3 ≤ c2n2 для всех n≥n0. Но тогда n ≤ c2/6
для всех n≥n0 – что явно не так.
        Отыскивая асимптотически точную оценку для суммы, мы можем отбрасывать
члены меньшего порядка, которые при больших n становятся малыми по сравнению с
основным слагаемым. Заметим также, что коэффициент при старшем члене роли не играет


(он может повлиять только на выбор констант c1 и c2). Например, рассмотрим
квадратичную функцию f(n) = an2 + bn + c, где a, b и c – некоторые константы и a>0.
Отбрасывая члены младших порядков и коэффициент при старшем члене, находим, что
f(n) = Θ(n2). Чтобы убедиться в этом формально, можно положить c1 = a/4, c2 = 7a/4 и n0 =
2×max(|b|/a, | c | / a ). Вообще, для любого полинома p(n) степени d с положительным
старшим коэффициентом имеем p(n) = Θ(nd).
        Упомянем важный частный случай использования Θ-обозначений: Θ(1) обозначает
ограниченную функцию, отделенную от нуля некоторой положительной константой при
достаточно больших значениях аргумента.

O– и Ω-обозначения
      Запись f(n) = Θ(g(n)) включает в себя две оценки: верхнюю и нижнюю. Их можно
разделить.

Если f(n) и g(n) – некоторые функции, то
• запись f(n) = Ο(g(n)) означает, что найдётся такая константа c > 0 и такое n0, что
   f(n) ≤ cg(n) для всех n ≥ n0;
• запись f(n) = Ω(g(n)) означает, что найдётся такая константа c > 0 и такое n0, что
   0 ≤ cg(n) ≤ f(n)для всех n ≥ n0.

      Теорема 26.
1. Для любых двух функций f(n) и g(n) свойство f(n) = Θ(g(n)) выполнено тогда и только
   тогда, когда f(n) = Ο(g(n)) и f(n) = Ω(g(n)).
2. Для любых двух функций f(n) и g(n) свойство f(n) = Ο(g(n)) выполнено тогда и только
   тогда, когда g(n) = Ω(f(n)).

       Как мы видели, an2 + bn + c = Θ(n2) (при a>0). Поэтому an2 + bn + c = Ο(n2). Другой
пример: при a>0 можно записать an + b = Ο(n2) (положим c = a + |b| и n0 = 1). Заметим, что
в этом случае an + b ≠ Ω(n2) и an + b ≠ Θ(n2).
       Работая с символами Ο, Θ и Ω мы имеем дело с односторонними равенствами – эти
символы могут стоять только справа от знака =.

      Введенные нами определения обладают некоторыми свойствами транзитивности,
рефлексивности и симметричности.

                                      Транзитивность
                    f(n) = Θ(g(n)) и g(n) = Θ(h(n)) влечет f(n) = Θ(h(n)).
                    f(n) = Ο(g(n)) и g(n) = Ο(h(n)) влечет f(n) = Ο(h(n)).
                    f(n) = Ω(g(n)) и g(n) = Ω(h(n)) влечет f(n) = Ω(h(n)).

                                     Рефлексивность
                         f(n) = Θ(f(n)), f(n) = Ο(f(n)), f(n) = Ω(f(n))

                                      Симметричность
                               f(n) = Θ(g(n)) ⇔ g(n) = Θ(f(n))


Сравнение роста функций
Определение. Говорят, что функция g мажорирует функцию f, если f(n) = O(g(n)).

Символ O(g(n)) читается как «O большое от g(n)»; при этом говорят, что f(n) имеет

порядок O большое от g(n).



        Отношение «O большое» наиболее полезно для сравнения асимптотического роста
функции. Рассмотрим это отношение для конкретных функций.
        Для положительных целых чисел r и s следующую теорему можно доказать
методом индукции. Справедливость утверждения теоремы для положительных
рациональных чисел r и s можно показать, не используя логарифмы.
        Теорема 27. Если r и s – действительные числа, r ≤ s и n > 1, тогда nr ≤ ns.
Следовательно, nr = O(ns).
        Доказательство. Функция ln(x) – возрастающая, поэтому a≤b тогда и только тогда,
когда ln(a) ≤ ln(b). Отсюда nr ≤ ns тогда и только тогда, когда ln(nr) ≤ ln(ns), что, в свою
очередь, выполняется тогда и только тогда, когда r ln(n) ≤ s ln(n), т.е. тогда и только тогда,
когда r ≤ s, поскольку ln(n) для n > 1 – величина положительная.
        Следующие теоремы показывают, что свойство функции иметь порядок O(g(n))
замкнуто относительно операций сложения и умножения на число.
        Теорема 28. Если f(n) = O(g(n)), то cf(n) = O(g(n)).
        Доказательство. По определению, |f(n)| ≤ k |g(n)| для некоторого действительного
числа k и всех n, больших или равных некоторому целому числу m. Поэтому
                                        |cf(n)| ≤ k|c| |g(n)|
и cf(n) = O(g(n)).
        Теорема 29. Если f(n) = O(g(n)) и h(n) = O(g(n)), то (f+h)(n) = O(g(n)).
        Доказательство. По определению, для некоторого постоянного k и некоторого
целого числа m1 имеем |f(n)| ≤ k |g(n)| для всех n > m1. Опять же по определению, для
некоторого постоянного l и некоторого целого числа m2 имеем |h(n)| ≤ l |g(n)| для всех n >
m2. Пусть m = max(m1, m2). Следовательно, для всех n > m
                                   |f(n)+h(n)| ≤ |f(n)|+|h(n)| ≤
                                       ≤ k |g(n)| + l |g(n)| =
                                           = (k + l)|g(n)|
и (f+g)(n) = O(g(n)).
        Теорема 30. Если f(n) = O(g(n)) и h(n) = O(e(n)), то (f×h)(n) = O(g×e)(n)).
        Доказательство. По определению, для некоторого постоянного k и некоторого
целого числа m1 имеем |f(n)| ≤ k |g(n)| для всех n > m1. Опять же по определению, для
некоторого постоянного l и некоторого целого числа m2 имеем |h(n)| ≤ l |e(n)| для всех n >
m2. Пусть m = max(m1, m2). Следовательно, для всех n > m
                                   |f(n)×h(n)| = |f(n)|×|h(n)| ≤
                                        ≤ k |g(n)| l |e(n)| =
                                         = (k l)|g(n)×e(n)|
и (f×g)(n) = O(g×e)(n)).
        Следующая теорема устанавливает мажоранту для полинома.
        Теорема 31. Если p(n) = aknk + ak-1nk-1 + … + a1n + a0, то p(n)=O(nk).
        Доказательство.

                           |p(n)| ≤ |aknk + ak-1nk-1 + … + a1n + a0| ≤
                     (в силу неравенства треугольника: |A+B|≤ |A|+|B|)


                           ≤ |aknk| + |ak-1nk-1| + … + |a1n| + |a0| =
                           = |ak| nk + |ak-1| nk-1 + … + |a1|n + |a0| ≤
                                         (по теореме 1)
                          ≤ |ak| nk + |ak-1| nk + … + |a1| nk + |a0| nk =
                              = (|ak| + |ak-1| + … + |a1| + |a0|) nk
и p(n)=O(nk).

       Теорема 32. Для целых чисел a и b, больших единицы, loga(n) = O(logb(n)).
                                                                        log b (n)
       Доказательство. Следует непосредственно из равенства log a (n) =           .
                                                                        log a (b)
       Теорема 33. Пусть n – неотрицательное целое число. Тогда n < 2n и, следовательно,
n = O(2n).
        Доказательство. Воспользуемся индукцией, имея для n = 0, 0 < 20 = 1. Допустим,
что k < 2k, тогда
                                   k+1 ≤ k+k ≤ 2k + 2k = 2k+1
и, по индукции, n < 2n.
        Пусть R – отношение на множестве функций, определенное как fRg, если f(n) =
O(g(n)). Очевидно, отношение R рефлексивно. Приведенная ниже теорема утверждает, что
это отношение также и транзитивно. Доказательство теоремы предоставляется читателю.
        Теорема 34. Если f(n) = O(g(n)) и g(n) = O(h(n)), то f(n) = O(h(n)).
        Следующая теорема дает ответ на вопрос о том, какие функции могут выступать в
роли мажорант для других функций.
        Теорема 35. Для целых чисел a, больших единицы, loga(n) = O(n).
        Доказательство. Согласно теореме 33, имеет место неравенство n < 2n. Поэтому
log2(n) < log2(2n) = n и log2(n) = O(n). Поскольку по теореме 32 имеем loga(n) = O(log2(n)),
то по теореме 34 получаем loga(n) = O(n).
        Доказательство сформулированных ниже теорем предоставляем читателям.
        Теорема 36. Пусть n – неотрицательное целое число, тогда n! < nn и,
следовательно, n! = O(nn).
        Теорема 37. Пусть a > 1 и n – неотрицательное целое число, тогда loga(n!) ≤ n
loga(n) и, следовательно, loga(n!) = O(n loga(n)).
        Пример 1. Определим число арифметических операций, необходимых для
сложения двух матриц.
        Пусть матрицы имеют размеры m×k. Тогда алгоритм сложения матриц A + B = C
можно описать на Паскале следующим образом:

for i:=1 to m do
     for j:= 1 to k do
           C[i,j]:=A[i,j] + B[i,j];

Как видим, сложение выполняется для каждого i и каждого j. Поскольку i принимает m
значений, а j принимает k значений, то выполняется mk операций сложения. Пусть n =
max (m, k). Тогда число выполняемых арифметических операций имеет порядок O(n2).
      Пример 2. Определим число арифметических операций, необходимых для
умножения двух матриц.
      Пусть матрицы A и B имеют размеры m×p и p×k, соответственно. Тогда алгоритм
умножения матриц A × B = C можно описать на Паскале следующим образом:

for i:=1 to m do
     for j:= 1 to k do
        begin


           C[i,j]:=0;
           for s:= 1 to p do
              C[i,j]:= C[i,j]+A[i,s]* B[s,j];
           end;

Поскольку s принимает значения от 1 до p, то выполняется p операций сложения и p
операций умножения. Величина s изменяется от 1 до p для каждого i и каждого j, поэтому
s пробегает значения от 1 до p mk раз. Таким образом, выполняется mkp операций
сложения и столько же операций умножения. Следовательно, всего выполняется 2mkp
операций. Пусть n = max(m,k,p). Тогда число выполняемых арифметических операций
имеет порядок O(n3).
        Пример 3. Сравним количество операций, которое требуется для
непосредственного вычисления значения многочлена традиционным способом и по схеме
Горнера.
        Пусть требуется вычислить p(c), где p(x) = anxn + an–1xn–1 + … + a1x + a0. Если p(c)
вычисляется непосредственно, то для подсчета ck требуется выполнить k–1 операций
умножения. Еще одна операция нужна для умножения на ak, так что вычисление akxk
требует k операций умножения. Таким образом, нужно выполнить 1 + 2 + …+ n = n(n-1)/2
умножений. Для того чтобы найти сумму n+1 слагаемых, требуется выполнить n
сложений, так что общее число арифметических операций равно n(n-1)/2 + n и имеет
порядок O(n2).
        При вычислении полинома a4x4 + a3x3 + a2x2 + a1x + a0 по схеме Горнера, мы
переписываем полином в виде x(x(x(a4x+ a3) + a2) + a1) + a0 и замечаем, что выражение
включает четыре операции умножения и четыре операции сложения. Очевидно, в общем
случае p(x) = x(x( … (x(anx+an–1) + an–2) + … a2) + a1) + a0 включает n операций сложения и
n операций умножения. Таким образом, общее число арифметических операций равно 2n
и имеет порядок O(n).
        Задача. Расположите следующие функции в порядке увеличения скорости роста
(каждая функция есть O(следующая)), не исключено, что некоторые функции имеют
одинаковую скорость:
                                 ln(ln n)                  (2 n )                                          ln n
2n, (1+n)!, ln (n!), en, n 2n, n          , 1, n (ln n), 2        , (trunc(ln n))!, ln n, n2, ln (ln n), 2      ,
                  (21+ n)
n!, e, 4 ln n , 2         , (ln n)2, n, ln n , 2 ln n , (3/2)n, n3, (ln n) ln n , 2 ln n .


5.2 Алгоритмы и их сложность
       Класс однородных вычислительных задач мы будем называть проблемой (также
используется понятие массовая задача или абстрактная задача). Индивидуальные
случаи проблемы Q мы будем называть частными случаями проблемы Q. Мы можем,
например, говорить о проблеме умножения матриц. Частные случаи этой проблемы суть
пары матриц, которые нужно перемножить.
      Более формально, мы принимаем следующую абстрактную модель вычислительной
задачи. Абстрактная задача есть произвольное бинарное отношение Q между элементами
двух множеств – множества условий (или входных данных) I и множества решений S.
Например, в задаче умножения матриц входными данными являются две конкретные
матрицы – сомножители, а матрица – произведение является решением задачи. В задаче
SHORTEST-PATH (поиска кратчайшего пути между двумя заданными вершинами
некоторого неориентированного графа G = (V,E)) условием (элементом I) является тройка,
состоящая из графа и двух вершин, а решением (элементом S) – последовательность
вершин, составляющих требуемый путь в графе. При этом один элемент множества I


может находиться в отношении Q с несколькими элементами множества S (если
кратчайших путей между данными вершинами несколько).
      Нам бы хотелось связать с каждым частным случаем проблемы некоторое число,
называемое его размером, которое выражало бы меру количества входных данных.
Например, размером задачи умножения матриц может быть наибольший размер матриц-
сомножителей. Размером задачи о графах может быть число ребер данного графа.
      Решение задачи на компьютере можно осуществлять с помощью различных
алгоритмов. Прежде чем подавать на вход алгоритма исходные данные (то есть элемент
множества I), надо договориться о том, как они представляются «в понятном для
компьютера виде»; мы будем считать, что исходные данные закодированы
последовательностью битов. Формально говоря, представлением элементов некоторого
множества M называется отображение e из M во множество битовых строк. Например,
натуральные числа 0, 1, 2, 3, … обычно представляют битовыми строками 0, 1, 10, 11,
100, … (при этом, например, e(17) = 10001).
      Фиксировав представление данных, мы превращаем абстрактную задачу в
строковую, для которой входным данным является битовая строка, представляющая
исходное данное абстрактной задачи. Естественно считать размером строковой задачи
длину строки.

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

       В качестве временной оценки работы алгоритма вместо общего числа шагов мы
можем подсчитывать число шагов некоторого вида, таких как арифметические операции
при алгебраических вычислениях, число сравнений при сортировке или число обращений
к памяти.
       Можно было подумать, что колоссальный рост скорости вычислений, вызванный
появлением нынешнего поколения компьютеров, уменьшит значение эффективных
алгоритмом. Однако происходит в точности противоположное. Так как компьютеры
работают все быстрее и мы можем решать все большие задачи, именно сложность
алгоритма определяет то увеличение размера задачи, которое можно достичь с
увеличением скорости машины.
       Следуя [8], рассмотрим это более подробно. Допустим, у нас есть пять алгоритмов
A1–A5 со следующими временными сложностями:

      Алгоритм                                   Асимптотическая            временная
                                           сложность
      A1                                         Ο(n)
      A2                                         Ο(n log n)
      A3                                         Ο(n2)
      A4                                         Ο(n3)
      A5                                         Ο(2n)

      Пусть единицей времени будет одна миллисекунда и мультипликативные
константы в точных оценках временной сложности во всех алгоритмах равны 1. Тогда
алгоритм A1 может обработать за одну секунду вход размера 1000, в то время как A5 –
вход размера не более 9. В таблице 1 приведены размеры задач, которые можно решить за
одну секунду, одну минуту и один час каждым из этих пяти алгоритмов.


      Таблица 1. Границы размеров задач, определяемые скоростью роста сложности.
      Алгоритм          Асимптотическая          Максимальный размер задачи
                  временная сложность
                                                 1с           1 мин         1ч
      A1                Ο(n)                     1000          6×104          3,6×106
      A2                Ο(n log n)               140           4893           2,0×105
      A3                Ο(n2)                    31            244            1897
      A4                Ο(n3)                    10            39             153
      A5                Ο(2n)                    9             15             21

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

      Таблица 2. Эффект десятикратного ускорения
      Алгоритм         Асимптотическая          Максимальный размер задачи
                 временная сложность
                                                До ускорения       После
                                                             ускорения
      A1               Ο(n)                     S1                 10 S1
      A2               Ο(n log n)               S2                 Примерно 10 S2
                                                             для больших S2
                           2
      A3               Ο(n )                    S3                 3,16 S3
                           3
      A4               Ο(n )                    S4                 2,15 S4
                           n
      A5               Ο(2 )                    S5                 S5 + 3,3

       Заметим, что для алгоритма A5 десятикратное увеличение скорости увеличивает
размер задачи, которую можно решить, только на три, тогда как для алгоритма A3 размер
задачи более чем утраивается.
       Вместо эффекта увеличения скорости рассмотрим теперь эффект применения более
действенного алгоритма. Вернемся к таблице 1. Если в качестве основы для сравнения
взять 1 мин, то, заменяя алгоритм A4 алгоритмом A3, можно решить задачу в 6 раз
большую, а заменяя A4 на A2, можно решить задачу, большую в 125 раз. Эти результаты
производят гораздо большее впечатление, чем двукратное улучшение, достигаемое за счет
десятикратного увеличения скорости. Если в качестве основы для сравнения взять 1 ч, то
различие оказывается еще значительнее. Отсюда мы заключаем, что асимптотическая
скорость алгоритма служит важной мерой качественности алгоритма, причем такой
мерой, которая обещает стать еще важнее при последующем увеличении скорости
вычислений.
       Несмотря на то, что основное внимание здесь уделяется порядку роста величин,
надо понимать, что больший порядок сложности алгоритма может иметь меньшую
мультипликативную постоянную, чем малый порядок роста сложности другого алгоритма.
В таком случае алгоритм с быстро растущей сложностью может оказать предпочтительнее
для задач с малым размером – возможно, даже для всех задач, которые нас интересуют.

5.3 Сложность задач
      Сложность задачи – это асимптотическая временная сложность наилучшего
алгоритма, известного для ее решения.



    
Яндекс цитирования Яндекс.Метрика