|
Тема |
Re: Сложност на метод - big O() [re: EroS] |
|
Автор | javafen (Нерегистриран) | |
Публикувано | 23.04.06 12:51 |
|
|
1) n=100;
2) sum=0;
3) for(i=0;i<n;i++)
4) for(j=0;j<n;j++)
5) sum++
А) Редове 1 и 2 има статична инициализация, която отнема константно време а
Б) Операциите i=0 и i++ както и за проверката i<n представлява константен брой инструкции към процесора, което означаваме с b, c и d
В) Времената необходими за операциите j=0,j<n и j++ означаваме с e,f и g
Г) Операцията на ред 5 също изисква константно време h
Taka общото време на работа на програмата, за произволна стойност на n:
a+b+n.c+n.d+n(e+n.f+n.g+n.h)=n2.(f+g+h)+n.(c+d+e)+a+b
тъй като a,b,c,d,e,f,g,h са константи
Полагаме: i=f+g+h
j=c+d+e
k=a+b
Taka алгоритъма се изпълнява за време i.n2+j.n+k
Константите i j k не са определящи за бързодеиствието на алгоритъма и можем да ги пренебрегнем. Можем дори да пренебрегнем и j.n +k и да оставим единствено тази част с най високата степен.Тя е най значимата характеристика за този алгоритъм, защото от нея в най-голяма степен зависи времето за изпълнение, тъй като нараства най- бързо когато се увеличаваразмера на входните данни
Оттук следва, че за сложността на този алгоритъм може да приемем n2 (чете се "n-квадрат") или ако приемем означението голямо "О" можем да кажем, че сложността е О(n2)
|
| |
|
|
|