У овом упутству ћете научити шта су асимптотски записи. Такође, научићете о Биг-О нотацији, Тхета нотацији и Омега нотацији.
Ефикасност алгоритма зависи од количине времена, меморије и других ресурса потребних за извршавање алгоритма. Ефикасност се мери помоћу асимптотских нотација.
Алгоритам можда неће имати исте перформансе за различите типове улаза. Са повећањем величине улаза, перформансе ће се променити.
Проучавање промене перформанси алгоритма са променом редоследа улазне величине дефинисано је као асимптотска анализа.
Асимптотске нотације
Асимптотски записи су математички записи који се користе за описивање времена рада алгоритма када улаз тежи ка одређеној вредности или граничној вредности.
На пример: У мехурићастом сортирању, када је улазни низ већ сортиран, време које алгоритам узима је линеарно, тј. Најбољи случај.
Али, када је улазни низ у обрнутом стању, алгоритму је потребно максимално време (квадратно) за сортирање елемената, тј. Најгори случај.
Када улазни низ није ни сортиран ни обрнутим редоследом, потребно је просечно време. Ова трајања су означена асимптотским нотацијама.
Углавном постоје три асимптотске нотације:
- Ознака Биг-О
- Омега нотација
- Тхета нотација
Биг-О нотација (О-нотација)
Ознака Биг-О представља горњу границу времена рада алгоритма. Дакле, то даје најгорем случају сложеност алгоритма.
Биг-О даје горњу границу функције
О (г (н)) = (ф (н): постоје позитивне константе ц и н 0 такве да је 0 ≦ ф (н) ≦ цг (н) за све н ≧ н 0 )
Горњи израз се може описати као функција која f(n)припада скупу O(g(n))ако постоји позитивна константа cтаква да се налази између 0и cg(n), за довољно велику n.
За било коју вредност n, време извођења алгоритма не прелази време које пружа O(g(n)).
С обзиром да даје најгоре могуће време рада алгоритма, широко се користи за анализу алгоритма јер нас увек занима најгори сценарио.
Омега нотација (Ω-нотација)
Омега нотација представља доњу границу времена рада алгоритма. Дакле, пружа најбољу сложеност случаја алгоритма.
Омега даје доњу границу функције
Ω (г (н)) = (ф (н): постоје позитивне константе ц и н 0 такве да је 0 ≦ цг (н) ≦ ф (н) за све н ≧ н 0 )
Горњи израз се може описати као функција која f(n)припада скупу Ω(g(n))ако постоји позитивна константа cтаква да лежи горе cg(n), за довољно велику n.
За било коју вредност n, минимално време потребно алгоритму даје Омега Ω(g(n)).
Тхета нотација (Θ-нотација)
Тхета нотација обухвата функцију одозго и одоздо. С обзиром да представља горњу и доњу границу времена рада алгоритма, користи се за анализу сложености алгоритма у просечном случају.
Тхета ограничава функцију унутар фактора константи
За функцију g(n), Θ(g(n))дат је релацијом:
Θ (г (н)) = (ф (н): постоје позитивне константе ц 1 , ц 2 и н 0 такве да је 0 ≦ ц 1 г (н) ≦ ф (н) ≦ ц 2 г (н) за све н ≧ н 0 )
Горњи израз се може описати као функција која f(n)припада скупу Θ(g(n))ако постоје позитивне константе и таква да може бити стављена у "сендвич" између и , за довољно велики н.c1c2c1g(n)c2g(n)
Ако функција f(n)лежи било где између и за све , тада се каже да је асимптотски чврсто везана.c1g(n)c2g(n)n ≧ n0f(n)
