Jan 12, 2022 Ассимптотический анализ, краткий конспект: Классические меры сложности: Ссылка на задачу, где посчитана сложность Оценка меры сложности алгоритма поворота матрицы. Сделал оценку по рассмотренной задаче. Верхняя оценка сложности О-большое равна квадратичной зависимости О(n^3). Одним словом, для реальных данных алгоритм пришлось бы переделывать.
Jan 12, 2022
Ассимптотический анализ, краткий конспект:
- Понятия алгоритм, вычислительная (математическая) модель.
- Оценка сложности алгоритма:О-большое (верхняя оценка)
о-малое (средняя оценка)
Омега (нижняя оценка)
Тета (точная оценка сложности)
Классические меры сложности:
- О(1) - характерно для получения элемента по индексу. Супер.
- О(n) Норм
- O(log n) Норм
- O(n*log n) - удовлетворительная сложность
- O(n * n) и т.д. - - характерно для вложенных циклов. Неудовлетворительная сложность - всё переделать.
Ссылка на задачу, где посчитана сложность
Оценка меры сложности алгоритма поворота матрицы. Сделал оценку по рассмотренной задаче. Верхняя оценка сложности О-большое равна квадратичной зависимости О(n^3). Одним словом, для реальных данных алгоритм пришлось бы переделывать.