Автор оригинала: Eric Rowell Автор перевода: Тимур Гуев Эта статья рассказывает о времени выполнения и о расходе памяти большинства алгоритмов используемых в информатике. Поиск Сортировка Структуры данных Кучи Представление графов Пусть дан граф с |V| вершинами и |E| ребрами, тогда Нотация асимптотического роста График роста O — большое
Эта статья рассказывает о времени выполнения и о расходе памяти большинства алгоритмов используемых в информатике.
Поиск
Сортировка
Структуры данных
Кучи
Представление графов
Пусть дан граф с |V| вершинами и |E| ребрами, тогда
Нотация асимптотического роста
- (О — большое) — верхняя граница, в то время как (Омега — большое) — нижняя граница. Тета требует как (О — большое), так и (Омега — большое), поэтому она является точной оценкой (она должна быть ограничена как сверху, так и снизу). К примеру, алгоритм требующий Ω (n logn) требует не менее n logn времени, но верхняя граница не известна. Алгоритм требующий Θ (n logn) предпочтительнее потому, что он требует не менее n logn (Ω (n logn)) и не более чем n logn (O(n logn)).
- f(x)=Θ(g(n)) означает, что f растет так же как и g когда n стремится к бесконечности. Другими словами, скорость роста f(x) асимптотически пропорциональна скорости роста g(n).
- f(x)=O(g(n)). Здесь темпы роста не быстрее, чем g (n). O большое является наиболее полезной, поскольку представляет наихудший случай.