6. Оценка и сложност на алгоритми [1.4]

    Три главни свойства на компютърен алгоритъм:
  • простота и елегантност;
  • коректност;
  • бързодействие.

  •     Нека разгледаме следния програмен фрагмент:

    n = 100;
    sum = 0;
    for (i=0; i<n; i++)
     for (j=0; j<n; j++) sum++;
     

    Колко бързо ще работи горната програма, т.е. какви са критериите по-които се определя бързината й? Това, което можем да направим експериментално е да проверим за колко време ще се изпълни и ще завърши работата си. За да изследваме по-общо нейното поведение е възможно да я изпълним за други стойности на n.

    Резултатите от последното са обобщени в следната таблица:
    Размер на входа
    n
    Време за изпълнение
    сек.
    10 10-6
    100 10-4
    1000 0.01
    104 1.071
    106 106.5
    108 10663.6
    От таблицата се вижда, че когато увеличаваме n 10 пъти, времето за изпълнение се увеличава 100 пъти.
    Времето за изпълнение е пророрционално на  f (n) = c1n2 + c2n+ c3, където c1, c2, c3 са константи, които могат лесно да се определят от дадената част от програмата.
     
    Сравняване на двете функции f (n)= 2n2 и g(n)= 200n, които показват времето за изпълнение на два дадени алгоритъма А1 и A2, в зависимост от n
     
     

    Асимптотично алгоритъмът A2 е по-бърз и неговата сложност е линейна, докато тази на A1 е квадратична.

    n f (n) g(n)
    1 2 200
    10 200 2000
    100 2.104 2.104
    1000 2.106 2.105
    104 2.108 2.106
    106 2.1012 2.108

     Размер на входните данни

        Нека е дадена задача, в която размерът на входните данни е определен от дадено цяло число n. Почти всички задачи, които ще разглеждаме, притежават това свойство. Ще поясним последното като разгледаме няколко примера:

    Пример 1.
    Да се сортира масив с n елемента.
    Размерът на входните данни се определя от броя n на елементите на масива .

    Пример 2.
    Да се намери най-големият общ делител на a и b.
    В този пример размерът на входните данни се определя от броя на двоичните цифри (битовете) на по-голямото от числата a и b.

    Пример 3.
    Да се намери покриващо дърво на граф.
    В този случай характеризираме размера на входа с две числа: брой на върховете и брой на ребрата.

    Асимптотична нотация

        Когато се интересуваме от сложността на алгоритъм най-често се интересуваме как ще работи при достатъчно голям размер n на входните данни. При формалното оценяване на сложността на алгоритмите ще се интересуваме от поведението им при n клонящо към безкрайност.

    1. O(F) определя множеството от всички функции  f, които нарастват не по-бързо от F, т.е. съществува константа c > 0 такава, че f (n) <= cF(n), за всички достатъчно големи стойности на n.

    2. Q (F) определя множеството от всички функции f, които нарастват толкова бързо, колкото и F (с точност до константен множител), т.е. съществуват константи c1 > 0 и c2 > 0 такава, че c1F(n) <=  f (n) <= c2F(n), за всички достатъчно големи стойности на n.

    3. W (F) определя множеството от всички функции f, които нарастват не по-бавно от F, т.е. съществува константа c > 0 такава, че f (n) >= cF(n), за всички достатъчно големи стойности на n.

    O(F): Свойства и примери

    Нотацията О(F) е най-често използваната при оценка на сложност на алгоритми и програми.
    По-важни свойства на O(F) (с ~ тук означаваме принадлежност):

  • рефлексивност: f ~ О( f );
  • транзитивност: ако f ~ О(g), g ~ О(h), то  f ~ О(h);
  • транспонирана симетрия:  ако f  ~ W (g), то g ~ O( f ) и обратно;
  • константите могат да бъдат игнорирани: за всяко k > 0, kF ~ О(F);
  • n, повдигнато в по-висока степен, нараства по-бързо: nr~ О(ns), за 0 < r < s.
  • нарастването на сума от функции се определя от най-бързо нарастващата от тях: f + g ~ max(O( f ), O(g));
  • ако f(n) е полином от степен d, то f ~ О(nd);
  • ако f нараства по-бързо от g, а g нараства по-бързо от h, то следва, че f нараства по-бързо от h.
  • Нарастване на най-често използваните функции:

    Функция / n
    1
    2
    10
    100
    1000
    5
    5
    5
    5
    5
    5
    log n
    0
    1
    3.32
    6.64
    9.96
    n
    1
    2
    10
    100
    1000
    n log n
    0
    2
    33.2
    664
    9996
    n2
    1
    4
    100
    104
    106
    n3
    1
    8
    1000
    106
    109
    2n
    2
    4
    1024
    1030
    10300
    n!
    1
    2
    3628800
    10157
    102567
    nn
    1
    4
    1010
    10200
    103000

    Определяне на сложност на алгоритъм:
    - елементарна операция - не зависи от размера на обработваните данни { O(1) };
    - последователност от оператори - определя се от асимтотично най-бавния { f + g О max(O( f ), O(g)) };
    - композиция на оператори - произведение от сложностите { f  g О O( f g) };
    - условни оператори - определя се от асимтотично най-бавния измежду условието и различните случаи;
    - цикли, вложени цикли - { O(n), O(np) }.

    Примери:
    /* Брой цифри на число */
    // digits.c
    #include <stdio.h>
    unsigned n=9800;
    int main(void)
    {  unsigned d, m=n;
      for (d=0; m>0; d++, m/=10);
      printf("numb of dig %u is %u\n",n,d);
      return 0;
    }

    /* Сума от цифрите на число */
    // sdigits.c
    #include <stdio.h>
    unsigned n=9800;
    int main(void)
    {  unsigned m, s=0;
      for (m=n; m>0; s+=m%10, m/=10);
      printf("sum of digits=%u\n", s);
      return 0;
    }

    /* Брой цифри на число */
    // ldigit.c
    #include <stdio.h>
    #include <math.h>
    unsigned n=9800;
    int main(void)
    {  printf("int(1+log10 (%u)) = %d\n", n, (int)(1+log10(n)));
      return 0;
    }

    Оценка на сложността на "Решето на Ератостен" и алгоритъма за намиране последователно на простите числа.
    Оценка на сложността на следните цикли:
    // 1
    for (i=0; i<n; i++)
     for (j=0; j<n, j==i; j++, sum++);
    // 2
    for (i=0; i<n; i++)
     for (j=0; j<n; j++) if (a[i]==a[j]) return;
    // 3
    for (i=0; i<n; i++)
     for (j=0; j<n; j++) if (a[i]!=a[j]) return;
    // 4
    for (i=0; i<n; i++)
     for (j=0; j<n; j++) if (a[i]==a[j]) return;
    // 5
    for (i=0; i<n; i++)
     for (j=0; j<i; j++) sum++;
    // 6
    for (i=0; i<n; i++)
     for (j=0; j<n*n; j++) sum++;
    // 7
    for (i=0; i<n; i++)
     for (j=0; j<i*i; j++) sum++;
    // 8
    for (i=0; i<n; i++)
     for (j=0; j<i*i; j++)
       for (k=0; k<j*j; k++) sum++;


    Логаритмична сложност.

        Да разгледаме цикъла:
    for (sum=0, i=0; i<n; i+=2) sum++;
    Променливата i приема стойности 1, 2, 4, ..., 2k, ...  докато надмине n. Цикълът се изпълнява [log n] пъти. Сложността е O(log n).

        Изчисляване на сложност при рекурсия.
    Пример: Двоично търсене - рекурсивен алгоритъм.
        Броим обръщенията към елементите на масива. В рекурсивната функция се разглежда средния елемент и се прави едно рекурсивно извикване с два пъти по-малък масив. Следователно, ако T(n) е функцията, която задава броя на обръщенията, то T(n) = T(n/2) + 1. От равенствата
                    T(n) = T(n/2) + 1 = T(n/4) + 2 = T(n/8) + 3 = ... = T(n/2k) + k
    получаваме за n = 2k, че  T(n) = T(1) + log n, т.е. сложността на алгоритъма е O(log n).

    Характеристични уравнения [1.4.9]
    Числа на Фибоначи
          T(n) = T(n - 2) + T(n - 1)

    Специални техники за анализ на алгоритми [1.4.10]
    - Измерване на времето за работа
    - Използване на барометър
    - Амортизационен анализ - зависимост от входните данни

    Най-добър случай, най-лош случай, обща сложност
    Проблеми при асимптотичната нотация [1.4.11]
    >
    Задача 6. Hidden Password

    Input File: B.IN
    Output File: standard output

    Some time the programmers have very strange ways to hide their passwords. See for example how Billy "Hacker" Geits hide his password. Billy chooses a string S composed of small Latin letters with length L. Then he makes all L - 1 one-letter left cyclic shifts of the string and takes as a password one prefix of the lexicographically first of the obtained strings (including S). For example let consider the string alabala. The cyclic one-letter left shifts (including the initial string) are:

        alabala
      labalaa
      abalaal
      balaala
      alaalab
      laalaba
      aalabal

    and lexicographically first of them is the string aalabal. The first letter of this string is in position 6 in the initial string (the positions in the string are counted from 0).

    Write a program that for given string S finds the start position of the smallest lexicographically one-letter left cyclic shift of this string. If the smallest lexicographically left shift appears more than once then the program have to output the smallest initial position.

    Your program has to be ready to solve more than one test case. The first line of the input file will contains only the number T of the test cases. Each of the following T lines will describe one test case – first the length L of the string (5 < L < 100000) and then, separated by one space, the string S itself.

    The output file have to contain exactly T lines with a single number each – the initial position found by your program.

    EXAMPLE

    Input                                      Output
    2                      1
    6 baabaa               6
    7 alabala