Алгоритъмът е добре дефинирана изчислителна процедура, която взима някаква стойност или набор от стойности, като вход, и връща друга стойност или набор от стойности, като изход. Тогава, алгоритъм е последователността от стъпки, които трансформират дадения вход в желания изход. Или по-просто казано, алгоритъм е процедура, която решава дадена задача. Още по-просто казано, алгоритъм е рецепта.
Даден алгоритъм е коректен, ако за всеки негов вход, той връща очаквания изход. Казваме, че коректния алгоритъм решава поставената изчислителна задача. Обратно, ако алгоритъм не е коректен, то съществува вход, за който алгоритъмът връща неочакван изход.
Причина за по-задълбоченото изследване и разработване на алгоритмите, е сортирането. Практическите приложения на алгоритмите са всеобхватни:
- Human Genome Project (Fast algorithms for large-scale genome alignment and comparison)
- Internet (Algorithms, Games, and the Internet)
- Crypto (5 Common Encryption Algorithms and the Unbreakables of the Future)
- Производство (Bin packing problem)
- Политика (A Bayesian Prediction Model for US Presidential Elections)
- Транспорт (Heuristics for the Traveling Salesman Problem)
В асимптотичния запис обикновено не се използват константи, тъй в много случаи константите могат да бъдат компенсирани от хардуера на машината, върху която се изпълнява алгоритъма. Функциите от друга страна пък се различават по порядък, така че колкото и да е голяма някоя константа на асимптотично по-бързата функция, рано или късно, тя ще започне по-ефективно изчисление от по-бавната. Също така, ние по-скоро се интересуваме от скоростта на нарастване, от което може да добием представа чрез асимптотичната нотация.
Описва горната граница на времевата функция на алгоритъма, т.е. най-лошият случай. Алгоритъм, който отпечатва елементите на един масив е със времева сложност O(n), но той също така е и със сложност O(n^2), O(n^3), O(2^n). Значи сложността на алгоритъм в O(f(n)) е не по-бързо нарастваща от f(n). Но тъй като на нас ни служи да знаем най-бавно нарастващата такава функция, то използваме нея, когато определяме горната граница на алгоритъма, в случая това ще бъде O(n).
Описва долната граница на времевата функция на алгоритъма, т.е. най-добрият случай. Отпечатването на елементите на един масив е с времева сложност Ω(n), но също така и с Ω(logn), и дори с Ω(1). Единственото, което знаем е, че сложността на алгоритъма e не по-бавно нарастваща от тези функции. Затова тук, по-скоро гледаме най-голямата такава граница, а и по принцип рядко се използва Ω нотацията.
Описва тези функции, които са комбинация и от Big Oh, и от Big Omega, т.е. сложността на даден алгоритъм нараства със скоростта на нарастване на дадената функция. Значи времевата функция описана от алгоритъма може да бъде заградена с константа по функцията, към чийто клас принадлежи. Може да бъде изграден канал с помощта на умножение с някакви константи, по-големи от нула, на тази функция, така че функцията на нарастване на вашия алгоритъм да се помести в изградения канал.
P (polynomial time) са всички задачи, които са решими за полиномиално време, т.е. функцията на асимтотичната им оценка е някакъв полином. NP (nondeterministic polynomial time) са всички задачи, чиито резултат може да бъде проверен за полиномиално време. Един от известните все още нерешени проблеми е, дали P ?= NP. Всяка година има поне по един научен труд твърдящ или че равенството е изпълнено, или обратното. NP-hard са група от задачи, до които всяка NP задача може да бъде сведена. Не всички задачи обаче от Np-hard групата са NP. NP-complete са задачите, които са в NP-hard и са NP и така нататък. :-)
- Know Thy Complexities!
- Complexity Cheatsheet
- ФМИ курс: Дизайн и Анализ на Алгоритми
- Quora: What would happen if someone proves P == NP or P != NP
- ACM Magazine: The Status of the P Versus NP Problem
- NP-hard Problems
- Намерете рекурсивен алгоритъм за намиране на n-тото число на Фибоначи и го имплементирайте. Анализирайте времевата сложност на алгоритъма.
- Ако горният алгоритъм не е със сложност O(n), помислете как може да стане.
- * Потърсете начин сложността да се смъкне до O(logn).