В този урок ще научите какво представляват асимптотичните обозначения. Също така ще научите за нотация Big-O, нотация Theta и нотация Omega.
Ефективността на алгоритъма зависи от количеството време, съхранение и други ресурси, необходими за изпълнение на алгоритъма. Ефективността се измерва с помощта на асимптотични нотации.
Алгоритъмът може да няма еднаква производителност за различни видове входове. С увеличаването на размера на входа, производителността ще се промени.
Изследването на промяната в производителността на алгоритъма с промяната в реда на размера на входа се определя като асимптотичен анализ.
Асимптотични нотации
Асимптотичните нотации са математическите нотации, използвани за описване на времето за работа на алгоритъм, когато входът клони към определена стойност или ограничаваща стойност.
Например: При сортиране на балончета, когато входният масив вече е сортиран, времето, необходимо на алгоритъма, е линейно, т.е. най-добрият случай.
Но когато входният масив е в обратно състояние, алгоритъмът отнема максимално време (квадратично) за сортиране на елементите, т.е. най-лошия случай.
Когато входният масив не е нито сортиран, нито в обратен ред, тогава е необходимо средно време. Тези продължителности се означават с помощта на асимптотични нотации.
Има основно три асимптотични обозначения:
- Нотация Big-O
- Омега нотация
- Тита нотация
Big-O нотация (O-нотация)
Нотацията Big-O представлява горната граница на времето за работа на алгоритъма. По този начин дава сложност на алгоритъма в най-лошия случай.
Big-O дава горната граница на функция
O (g (n)) = (f (n): съществуват положителни константи c и n 0 такива, че 0 ≦ f (n) ≦ cg (n) за всички n ≧ n 0 )
Горният израз може да бъде описан като функция, f(n)принадлежаща към множеството, O(g(n))ако съществува положителна константа, cтакава, че да е между 0и cg(n), за достатъчно голяма n.
За всяка стойност на n, времето за работа на алгоритъм не пресича времето, предоставено от O(g(n)).
Тъй като дава време за работа на алгоритъма в най-лошия случай, той се използва широко за анализ на алгоритъм, тъй като винаги се интересуваме от най-лошия сценарий.
Омега нотация (Ω-нотация)
Омега нотация представлява долната граница на времето за работа на алгоритъм. По този начин той осигурява най-добрата сложност на алгоритъма.
Омега дава долната граница на функция
Ω (g (n)) = (f (n): съществуват положителни константи c и n 0 такива, че 0 ≦ cg (n) ≦ f (n) за всички n ≧ n 0 )
Горният израз може да бъде описан като функция, f(n)принадлежаща към множеството, Ω(g(n))ако съществува положителна константа, cтакава, че да е горе cg(n), за достатъчно голяма n.
За всяка стойност на n, минималното време, необходимо от алгоритъма, се дава от Omega Ω(g(n)).
Тита нотация (Θ-нотация)
Тита нотацията затваря функцията отгоре и отдолу. Тъй като представлява горната и долната граница на времето за работа на алгоритъм, той се използва за анализ на сложността на средния случай на алгоритъм.
Theta ограничава функцията в рамките на факторите на константите
За функция g(n), Θ(g(n))се дава от отношението:
Θ (g (n)) = (f (n): съществуват положителни константи c 1 , c 2 и n 0 такива, че 0 ≦ c 1 g (n) ≦ f (n) ≦ c 2 g (n) за всички n ≧ n 0 )
Горният израз може да бъде описан като функция, f(n)принадлежаща към множеството, Θ(g(n))ако съществуват положителни константи и такава, че да може да бъде поставена между и при достатъчно големи n.c1c2c1g(n)c2g(n)
Ако дадена функция f(n)лежи някъде между и за всички , тогава се казва, че е асимптотично тясно свързана.c1g(n)c2g(n)n ≧ n0f(n)
