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

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

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

    Нека е дадена задача, в която размерът на входните данни е определен от дадено цяло число 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 (с точност до константен множител), т.е. съществуват константи c₁ > 0 и c₂ > 0 такава, че c₁F(n) <=  f (n) <= c₂F(n), за всички достатъчно големи стойности на n.

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

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

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

Нарастване на най-често използваните функции:

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

Примери:
/* Брой цифри на число */
// 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, ..., 2^k, ...  докато надмине 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/2^k) + k
получаваме за n = 2^k, че  T(n) = T(1) + log n, т.е. сложността на алгоритъма е O(log n).

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

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