Сложност на алгоритъм

[[BG][SSA]Troll]

В урока за векторите включих понятието сложност. То за някой от вас е познато, но за по новите - не. Затова реших да направя урок посветен изцяло на сложността на алгоритмите и нейното определяне. Имаме следната програма на езика c++.

Код: Трябва да си влязъл в системата, за да можеш да виждаш линковете

#include <iostream>
using namespace std;
int main()
{
int a,b;
cin>>a>>b;
cout<<"a+b= "<<a+b<<endl;
}

Тук виждате имаме 4 операции, но те са константен брой и не зависят от нищо. Затова игнорираме броят им и казваме, че алгоритъмът е със сложност O(1).
Ето още една програма, която въвежда n числа и намира минималното въведено число и сумата на всичките.

Код: Трябва да си влязъл в системата, за да можеш да виждаш линковете

#include <iostream>
#include <limits.h>
using namespace std;
int main()
{
int n;
cin>>n;
int sum=0;
int min=INT_MIN;
int a;
for(int i=0;i<n;i++)
{
cin>>a;
sum+=a;
if(min>a)
{
min=a;
}
}
cout<<sum<<" "<<min<<endl;
}

Тук както виждате се изпълняват 4 операции, които се изпълняват n пъти => 4*n операции, но понеже 4 е константа казваме, че сложността е O(n).
Ако имаме сложност от вида n^2 + n взимаме члена с най-високата степен и казваме, че сложността е O(n^2).

Да обобщим. За да определим сложността на алгоритъма пресмятаме колко операции извършва той, игнорираме константите и взимаме члена с най-високата степен.