Подразделы

Другие разделы

Дата и время

24/12/2025 18:24:41

Авторизация

Математические основы анализа алгоритмов

Асимптотические обозначения Основные классы эффективности Индукция и инвариант Нижние границы эффективности Тривиальная нижняя граница Информационно-теоретическая нижняя граница

Основные классы эффективности

Класс|Название
--|--
1|Константа
`log n` |Логарифмическая
`sqrt n` | -
`n` | Линейная
`n log n`| -
`n sqrt n` | -
`n^2`| Квадратичная
`n^3`| Кубическая
`2^n`|Экспоненциальная
`n!` |Факториальная
`n^n`| -

--

Обычно значения постоянных множителей никто не
указывает. А это означает, что не исключена возможность, когда для входных данных
реального размера, алгоритм, относящийся к худшему классу эффективности,
будет работать быстрее, чем алгоритм, относящийся к лучшему классу
эффективности. Например, если время выполнения одного алгоритма изменяется по закону
`n^3`, а другого -- по закону `10^6 n^2`, кубический алгоритм будет работать быстрее при
условии, что `n` не превышает `10^6`.

---

##### Задания для практики

Расположите перечисленные ниже функции в соответствии с их порядком роста (от самого меньшего к самому большему).

`(n-2)!`, `5 "lg" (n+100)^{10}`, `2^{2n}`, `0.001n^4+3n^3+1`, `ln^2 n`, `root^3 n`,`3^n`

Назад

Подразделы

Другие разделы

Дата и время

Авторизация

Математические основы анализа алгоритмов

Основные классы эффективности