n = 100;
sum = 0;
for (i=0; i<n; i++)
for (j=0; j<n; j++) sum++;
| Колко бързо ще работи горната програма, т.е. какви са критериите по-които се определя бързината й? Това, което можем да направим експериментално е да проверим за колко време ще се изпълни и ще завърши работата си. За да изследваме по-общо нейното поведение е възможно да я изпълним за други стойности на n - нека резултатите от последното са обобщени в следната таблица: |
|
|
Сравняване на двете функции
f
(n)=
2n2
и
g(n)=
200n,
които показват времето за изпълнение на два дадени алгоритъма А1
и A2, в зависимост от
n.
Асимптотично алгоритъмът A2 е по-бърз и неговата сложност е линейна, докато тази на A1 е квадратична. |
|
Размер на входните данни
Нека е дадена задача, в която размерът на входните данни е определен от дадено цяло число 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):
Нарастване на най-често използваните функции:
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Определяне на сложност на алгоритъм:
- елементарна операция - не зависи от размера
на обработваните данни { 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; m/=10, d++);
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++;
Input File: B.IN
Output File: standard output
Program Source File: B.PAS or B.C or B.CPP or B.JAVA
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