Определения

АЛГОРИТМ: Алгоритм — это конечное описание шагов, которое преобразует допустимый вход в выход.
ВРЕМЕННАЯ СЛОЖНОСТЬ: Временная сложность — это функция, которая оценивает количество элементарных операций алгоритма в зависимости от размера входа.
ЗАДАЧА АЛГОРИТМА: Задача алгоритма — это описание допустимых входов, требуемых выходов и условия, которое связывает каждый правильный выход с соответствующим входом.
ИНВАРИАНТ ЦИКЛА: Инвариант цикла — это утверждение, которое истинно перед началом цикла и остается истинным после каждой итерации.
МНОЖЕСТВО К статье: Множество в математическом анализе — это совокупность уникальных элементов, которые могут быть числами, символами или другими объектами.
НЕПЕРЕСЕКАЮЩИЕСЯ МНОЖЕСТВА К статье: Непересекающиеся множества — это множества, которые не имеют общих элементов.
О-МАЛОЕ: о-малое задает строгую верхнюю оценку: f(n) = o(g(n)), если отношение f(n) к g(n) стремится к нулю.
ОБЪЕДИНЕНИЕ МНОЖЕСТВ К статье: Объединение множеств — это множество, содержащее все элементы из обоих множеств.
ОМЕГА-МАЛОЕ: омега-малое задает строгую нижнюю оценку: f(n) = ω(g(n)), если отношение f(n) к g(n) стремится к бесконечности.
ПЕРЕСЕЧЕНИЕ МНОЖЕСТВ К статье: Пересечение множеств — это множество, содержащее только те элементы, которые принадлежат обоим множествам.
ПОДМНОЖЕСТВО К статье: Подмножество — это множество, все элементы которого также являются элементами другого множества.
ПОЛНАЯ КОРРЕКТНОСТЬ: Полная корректность означает частичную корректность вместе с терминальностью.
ПРОСТРАНСТВЕННАЯ СЛОЖНОСТЬ: Пространственная сложность — это функция, которая оценивает дополнительную память алгоритма в зависимости от размера входа.
ПУСТОЕ МНОЖЕСТВО К статье: Пустое множество — это множество, не содержащее ни одного элемента.
РАВЕНСТВО МНОЖЕСТВ К статье: Два множества равны, если они содержат одни и те же элементы.
РАЗНОСТЬ МНОЖЕСТВ К статье: Разность множеств A и B — это множество, содержащее элементы, которые принадлежат A, но не принадлежат B.
РЕКУРРЕНТНОЕ СООТНОШЕНИЕ: Рекуррентное соотношение — это формула, которая выражает стоимость задачи через стоимость меньших задач того же вида и работу вне этих подзадач.
СОБСТВЕННОЕ ПОДМНОЖЕСТВО К статье: Собственное подмножество — это подмножество, которое не равно исходному множеству, то есть содержит меньше элементов.
ТЕРМИНАЛЬНОСТЬ: Терминальность означает: алгоритм завершает работу на каждом допустимом входе.
ЧАСТИЧНАЯ КОРРЕКТНОСТЬ: Частичная корректность означает: если алгоритм завершился на допустимом входе, то его результат удовлетворяет постусловию задачи.
O-НОТАЦИЯ: O-нотация задает асимптотическую верхнюю оценку: f(n) = O(g(n)), если начиная с некоторого места f(n) не превосходит константу, умноженную на g(n).
Θ-НОТАЦИЯ: Θ-нотация задает точную асимптотическую оценку с точностью до констант: f(n) = Θ(g(n)), если одновременно f(n) = O(g(n)) и f(n) = Ω(g(n)).
Ω-НОТАЦИЯ: Ω-нотация задает асимптотическую нижнюю оценку: f(n) = Ω(g(n)), если начиная с некоторого места f(n) не меньше константы, умноженной на g(n).