Более быстрый доступ, чем браузер!
75 отношения: «O» большое и «o» малое, Elsevier, Introsort, K-мерное дерево, L-нотация, NP-полная задача, Springer Science+Business Media, Квантовый алгоритм, Квантовая машина Тьюринга, Класс BPP, Класс BQP, Класс EXPTIME, Класс NP, Класс сложности, Класс P, Класс RP, Класс ZPP, Конъюнктивная нормальная форма, Псевдополиномиальный алгоритм, Параллельный алгоритм, Параллельные вычислительные системы, Паросочетание, Пирамидальная сортировка, Полный перебор, Оптимизация (математика), Архитектура набора команд, Арифметика Пресбургера, Алгоритм, Алгоритм сортировки, Алгоритм Кармаркара, Алгоритм Гровера, Алгоритм Евклида, Алгоритмы быстрого возведения в степень, Аппроксимационный алгоритм, Наибольший общий делитель, Недетерминированная машина Тьюринга, Раскраска графов, Равенство классов P и NP, Рекуррентная формула, Строковый тип, Схрейвер, Александр, Система непересекающихся множеств, Сортировка слиянием, Сортировка пузырьком, Тест Агравала — Каяла — Саксены, Функция Аккермана, Факторизация целых чисел, Формула Стирлинга, Формальный язык, Элиминация кванторов, ..., Массив (программирование), Массив Монжа, Машина Тьюринга, Модель вычислений, Итерированный логарифм, Информатика, Задача разрешимости, Задача Штейнера о минимальном дереве, Задача выполнимости булевых формул, Задача коммивояжёра, Задача о порядке перемножения матриц, Задача о покрытии множества, Быстрая сортировка, Быстрое преобразование Фурье, Базис Грёбнера, Вычислительная сложность, Вероятностный алгоритм, Вероятностная машина Тьюринга, Граф (математика), Двоичный поиск, Двоичное дерево, Динамическое программирование, Линейное программирование, Ловас, Ласло, Логарифм. Развернуть индекс (25 больше) »
«O» большое и «o» малое
«O» большое и «o» малое (O и o) — математические обозначения для сравнения асимптотического поведения (асимптотики) функций.
Новый!!: Временная сложность алгоритма и «O» большое и «o» малое · Узнать больше »
Elsevier
Elsevier — один из четырёх крупнейших научных издательских домов мира, который ежегодно выпускает около четверти всех статей из издаваемых в мире научных журналов.
Новый!!: Временная сложность алгоритма и Elsevier · Узнать больше »
Introsort
Introsort или интроспективная сортировка — алгоритм сортировки, предложенный Дэвидом Мюссером в 1997 году.
Новый!!: Временная сложность алгоритма и Introsort · Узнать больше »
K-мерное дерево
right В информатике k-d дерево (k-d tree, сокращение от k-мерное дерево) — это структура данных с разбиением пространства для упорядочивания точек в k-мерном пространстве.
Новый!!: Временная сложность алгоритма и K-мерное дерево · Узнать больше »
L-нотация
L-нотация — это асимптотическая нотация, аналогичная О-нотации, записывается как L_n для n стремящимся к бесконечности.
Новый!!: Временная сложность алгоритма и L-нотация · Узнать больше »
NP-полная задача
NP-полная задача — в теории алгоритмов задача с ответом «да» или «нет» из класса NP, к которой можно свести любую другую задачу из этого класса за полиномиальное время (то есть при помощи операций, число которых не превышает некоторого полинома в зависимости от размера исходных данных).
Новый!!: Временная сложность алгоритма и NP-полная задача · Узнать больше »
Springer Science+Business Media
Springer Science+Business Media (до 1999 г. — Springer-Verlag) — международная издательская компания, специализирующаяся на издании академических журналов и книг по естественно-научным направлениям (теоретическая наука, медицина, экономика, инженерное дело, архитектура, строительство и транспорт).
Новый!!: Временная сложность алгоритма и Springer Science+Business Media · Узнать больше »
Квантовый алгоритм
Квантовый алгоритм — это алгоритм, предназначенный для выполнения на квантовом компьютере.
Новый!!: Временная сложность алгоритма и Квантовый алгоритм · Узнать больше »
Квантовая машина Тьюринга
Квантовая машина Тьюринга (Quantum Turing machine; иногда — универсальный квантовый компьютер) — абстрактная машина, используемая для моделирования квантового компьютера.
Новый!!: Временная сложность алгоритма и Квантовая машина Тьюринга · Узнать больше »
Класс BPP
В теории алгоритмов классом сложности BPP (от bounded-error, probabilistic, polynomial) называется класс предикатов, быстро (за полиномиальное время) вычислимых и дающих ответ с высокой вероятностью (причём, жертвуя временем, можно добиться сколь угодно высокой точности ответа).
Новый!!: Временная сложность алгоритма и Класс BPP · Узнать больше »
Класс BQP
Примерное положение BQP на карте классов NP, P, PSPACE. В теории алгоритмов классом сложности BQP (от bounded error quantum polynomial time) называется класс проблем разрешимости, которые могут быть решены квантовым компьютером за полиномиальное время (время работы над задачей полиномиально зависит от размера входных данных), обеспечив при этом вероятность получения верного ответа как минимум 2/3 для любого входа.
Новый!!: Временная сложность алгоритма и Класс BQP · Узнать больше »
Класс EXPTIME
В теории сложности вычислений, класс сложности EXPTIME (иногда называемый просто EXP) - это множество задач, решаемых с помощью детерминированной машины Тьюринга за время O(2p(n)), где p(n) это полиномиальная функция от n.
Новый!!: Временная сложность алгоритма и Класс EXPTIME · Узнать больше »
Класс NP
В теории алгоритмов классом NP (от non-deterministic polynomial) называют множество проблем разрешимости, решение которых возможно проверить на машине Тьюринга за время, не превосходящее полинома от размера входных данных, при наличии некоторых дополнительных сведений (так называемого сертификата решения).
Новый!!: Временная сложность алгоритма и Класс NP · Узнать больше »
Класс сложности
В теории алгоритмов классами сложности называются множества вычислительных задач, примерно одинаковых по сложности вычисления.
Новый!!: Временная сложность алгоритма и Класс сложности · Узнать больше »
Класс P
В теории алгоритмов классом P (от polynomial) называют множество задач, для которых существуют «быстрые» алгоритмы решения (время работы которых полиномиально зависит от размера входных данных).
Новый!!: Временная сложность алгоритма и Класс P · Узнать больше »
Класс RP
Будем считать, что язык L принадлежит классу RP («randomized polynomial class» — случайный полиномиальный), если он допускается вероятностной машиной Тьюринга M, для которой выполнены следующие условия.
Новый!!: Временная сложность алгоритма и Класс RP · Узнать больше »
Класс ZPP
В теории вычислительной сложности, ZPP (zero-error probabilistic polynomial time — безошибочный вероятностный полиномиальный) это такой класс задач, для которых существует вероятностная машина Тьюринга, удовлетворяющая нескольким свойствам.
Новый!!: Временная сложность алгоритма и Класс ZPP · Узнать больше »
Конъюнктивная нормальная форма
Конъюнкти́вная норма́льная фо́рма (КНФ) в булевой логике — нормальная форма, в которой булева формула имеет вид конъюнкции дизъюнкций литералов.
Новый!!: Временная сложность алгоритма и Конъюнктивная нормальная форма · Узнать больше »
Псевдополиномиальный алгоритм
Псевдополиномиальный алгоритм — полиномиальный алгоритм, проявляющий экспоненциальный характер только при очень больших значениях числовых параметров.
Новый!!: Временная сложность алгоритма и Псевдополиномиальный алгоритм · Узнать больше »
Параллельный алгоритм
В информатике параллельный алгоритм, противопоставляемый традиционным последовательным алгоритмам, — алгоритм, который может быть реализован по частям на множестве различных вычислительных устройств с последующим объединением полученных результатов и получением корректного результата.
Новый!!: Временная сложность алгоритма и Параллельный алгоритм · Узнать больше »
Параллельные вычислительные системы
Параллельные вычислительные системы — это физические компьютерные, а также программные системы, реализующие тем или иным способом параллельную обработку данных на многих вычислительных узлах.
Новый!!: Временная сложность алгоритма и Параллельные вычислительные системы · Узнать больше »
Паросочетание
В теории графов паросочетание или независимое множество рёбер в графе — это набор попарно несмежных рёбер.
Новый!!: Временная сложность алгоритма и Паросочетание · Узнать больше »
Пирамидальная сортировка
Анимированная схема алгоритма Пирамидальная сортировка (Heapsort, «Сортировка кучей») — алгоритм сортировки, работающий в худшем, в среднем и в лучшем случае (то есть гарантированно) за Θ(n log n) операций при сортировке n элементов.
Новый!!: Временная сложность алгоритма и Пирамидальная сортировка · Узнать больше »
Полный перебор
Полный перебор (или метод «грубой силы», brute force) — метод решения математических задач.
Новый!!: Временная сложность алгоритма и Полный перебор · Узнать больше »
Оптимизация (математика)
Оптимизация — в математике, информатике и исследовании операций задача нахождения экстремума (минимума или максимума) целевой функции в некоторой области конечномерного векторного пространства, ограниченной набором линейных и/или нелинейных равенств и/или неравенств.
Новый!!: Временная сложность алгоритма и Оптимизация (математика) · Узнать больше »
Архитектура набора команд
Схема, иллюстрирующая место уровней микроархитектуры, архитектуры набора команд и микрокода в многоуровневой структуре компьютера Архитектура набора команд (instruction set architecture, ISA) — часть архитектуры компьютера, определяющая программируемую часть ядра микропроцессора.
Новый!!: Временная сложность алгоритма и Архитектура набора команд · Узнать больше »
Арифметика Пресбургера
Арифметика Пресбургера — это теория первого порядка, описывающая натуральные числа со сложением, но в отличие от арифметики Пеано, исключающая высказывания относительно умножения.
Новый!!: Временная сложность алгоритма и Арифметика Пресбургера · Узнать больше »
Алгоритм
Алгори́тм — набор инструкций, описывающих порядок действий исполнителя для достижения некоторого результата.
Новый!!: Временная сложность алгоритма и Алгоритм · Узнать больше »
Алгоритм сортировки
Алгоритм сортировки — это алгоритм для упорядочивания элементов в списке.
Новый!!: Временная сложность алгоритма и Алгоритм сортировки · Узнать больше »
Алгоритм Кармаркара
Алгоритм Кармаркара — это алгоритм, представленный Нарендра Кармаркаром в 1984 для решения задач линейного программирования.
Новый!!: Временная сложность алгоритма и Алгоритм Кармаркара · Узнать больше »
Алгоритм Гровера
Алгоритм Гровера Алгоритм Гровера (Grover search algorithm, GSA) — квантовый алгоритм решения задачи перебора, то есть нахождения решения уравнения где f есть булева функция от n переменных.
Новый!!: Временная сложность алгоритма и Алгоритм Гровера · Узнать больше »
Алгоритм Евклида
Алгори́тм Евкли́да — эффективный алгоритм для нахождения наибольшего общего делителя двух целых чисел (или общей меры двух отрезков).
Новый!!: Временная сложность алгоритма и Алгоритм Евклида · Узнать больше »
Алгоритмы быстрого возведения в степень
Алгоритмы быстрого возведения в степень (дихотомический алгоритм возведения в степень, бинарный алгоритм возведения в степень) — алгоритмы, предназначенные для возведения числа x в натуральную степень n за меньшее число умножений, чем это требуется в определении степени.
Новый!!: Временная сложность алгоритма и Алгоритмы быстрого возведения в степень · Узнать больше »
Аппроксимационный алгоритм
В исследовании операций под аппроксимационным алгоритмом понимается алгоритм, использующийся для поиска приближённого решения оптимизационной задачи.
Новый!!: Временная сложность алгоритма и Аппроксимационный алгоритм · Узнать больше »
Наибольший общий делитель
Наибольшим общим делителем (НОД) для двух целых чисел m и n называется наибольший из их общих делителей.
Новый!!: Временная сложность алгоритма и Наибольший общий делитель · Узнать больше »
Недетерминированная машина Тьюринга
В теоретической информатике недетерминированная машина Тьюринга — машина Тьюринга, функция перехода которой представляет собой недетерминированный конечный автомат.
Новый!!: Временная сложность алгоритма и Недетерминированная машина Тьюринга · Узнать больше »
Раскраска графов
Корректная раскраска вершин графа наименьшим набором цветов — тремя. В теории графов раскраска графов является частным случаем.
Новый!!: Временная сложность алгоритма и Раскраска графов · Узнать больше »
Равенство классов P и NP
Вопрос о равенстве классов сложности ''P'' и ''NP'' (в русских источниках также известный как проблема перебора) — это одна из центральных открытых проблем теории алгоритмов уже более трёх десятилетий.
Новый!!: Временная сложность алгоритма и Равенство классов P и NP · Узнать больше »
Рекуррентная формула
Рекуррентная формула — формула вида a_n.
Новый!!: Временная сложность алгоритма и Рекуррентная формула · Узнать больше »
Строковый тип
В программировании, строковый тип (string «нить, вереница») — тип данных, значениями которого является произвольная последовательность (строка) символов алфавита.
Новый!!: Временная сложность алгоритма и Строковый тип · Узнать больше »
Схрейвер, Александр
Александр (Лекс) Схрейвер (род. 1948) — нидерландский математик, известный своими работами по комбинаторной оптимизации, совмещающей алгоритмику и комбинаторику.
Новый!!: Временная сложность алгоритма и Схрейвер, Александр · Узнать больше »
Система непересекающихся множеств
Система непересекающихся множеств (disjoint-set, или union–find data structure) — структура данных, которая позволяет администрировать множество элементов, разбитое на непересекающиеся подмножества.
Новый!!: Временная сложность алгоритма и Система непересекающихся множеств · Узнать больше »
Сортировка слиянием
Сортировка слиянием (merge sort) — алгоритм сортировки, который упорядочивает списки (или другие структуры данных, доступ к элементам которых можно получать только последовательно, например — потоки) в определённом порядке.
Новый!!: Временная сложность алгоритма и Сортировка слиянием · Узнать больше »
Сортировка пузырьком
Сортировка простыми обменами, сортиро́вка пузырько́м (bubble sort) — простой алгоритм сортировки.
Новый!!: Временная сложность алгоритма и Сортировка пузырьком · Узнать больше »
Тест Агравала — Каяла — Саксены
Тест Аграва́ла — Кая́ла — Саксе́ны (тест AKS) — единственный известный на данный момент универсальный (то есть применимый ко всем числам) полиномиальный, детерминированный и безусловный (то есть не зависящий от недоказанных гипотез) тест простоты чисел, основанный на обобщении малой теоремы Ферма на многочлены.
Новый!!: Временная сложность алгоритма и Тест Агравала — Каяла — Саксены · Узнать больше »
Функция Аккермана
Функция Аккермана — простой пример всюду определённой вычислимой функции, которая не является примитивно рекурсивной.
Новый!!: Временная сложность алгоритма и Функция Аккермана · Узнать больше »
Факторизация целых чисел
342x342px Факториза́цией натурального числа называется его разложение в произведение простых множителей.
Новый!!: Временная сложность алгоритма и Факторизация целых чисел · Узнать больше »
Формула Стирлинга
Отношение (ln ''n''!) к (''n'' ln ''n'' − ''n'') стремится к 1 с увеличением ''n''. В математике формула Стирлинга (также формула Муавра — Стирлинга) — формула для приближённого вычисления факториала и гамма-функции.
Новый!!: Временная сложность алгоритма и Формула Стирлинга · Узнать больше »
Формальный язык
Синтаксическое подразделение в рамках формальной системы. Формальный язык в математической логике и информатике — множество конечных слов (строк, цепочек) над конечным алфавитом.
Новый!!: Временная сложность алгоритма и Формальный язык · Узнать больше »
Элиминация кванторов
В математической логике элиминация кванторов — это процесс, порождающий по заданной логической формуле, другую, эквивалентную ей формулу, свободную от вхождений кванторов.
Новый!!: Временная сложность алгоритма и Элиминация кванторов · Узнать больше »
Массив (программирование)
Массив (в некоторых языках программирования также таблица, ряд, матрица) — структура данных в виде набора компонентов (элементов массива), расположенных в памяти непосредственно друг за другом, что позволяет обращаться к элементам по числовому индексу.
Новый!!: Временная сложность алгоритма и Массив (программирование) · Узнать больше »
Массив Монжа
В математике массивы Монжа или матрицы Монжа — это объекты, названные по имени открывателя, французского математика Гаспара Монжа.
Новый!!: Временная сложность алгоритма и Массив Монжа · Узнать больше »
Машина Тьюринга
Художественное представление машины Тьюринга Маши́на Тью́ринга (МТ) — абстрактный исполнитель (абстрактная вычислительная машина).
Новый!!: Временная сложность алгоритма и Машина Тьюринга · Узнать больше »
Модель вычислений
Теория вычислимости и теория сложности вычислений трактует модель вычисления (model of computation) не только как определение множества допустимых операций, использованных для вычисления, но также и относительных издержек их применения.
Новый!!: Временная сложность алгоритма и Модель вычислений · Узнать больше »
Итерированный логарифм
Десятичный \scriptstyle\lg* 4.
Новый!!: Временная сложность алгоритма и Итерированный логарифм · Узнать больше »
Информатика
Информа́тика (Informatique; Computer science) — наука о методах и процессах сбора, хранения, обработки, передачи, анализа и оценки информации с применением компьютерных технологий, обеспечивающих возможность её использования для принятия решений.
Новый!!: Временная сложность алгоритма и Информатика · Узнать больше »
Задача разрешимости
Задача разрешимости (проблема разрешимости) — вопрос, сформулированный в рамках какой-либо формальной системы, требующий ответа «да» или «нет», возможно, зависящего от значений некоторых входных параметров.
Новый!!: Временная сложность алгоритма и Задача разрешимости · Узнать больше »
Задача Штейнера о минимальном дереве
Минимальное дерево Штейнера для точек ''A'', ''B'' и ''C'', где ''S'' — точка Ферма треугольника ''ABC''. Задача Штейнера о минимальном дереве состоит в поиске кратчайшей сети, соединяющей заданный конечный набор точек плоскости.
Новый!!: Временная сложность алгоритма и Задача Штейнера о минимальном дереве · Узнать больше »
Задача выполнимости булевых формул
Зада́ча выполни́мости бу́левых фо́рмул (SAT или ВЫП) — важная для теории вычислительной сложности алгоритмическая задача.
Новый!!: Временная сложность алгоритма и Задача выполнимости булевых формул · Узнать больше »
Задача коммивояжёра
43589145600 вариантов. Задача коммивояжёра (Travelling salesman problem, сокращённо TSP) — одна из самых известных задач комбинаторной оптимизации, заключающаяся в поиске самого выгодного маршрута, проходящего через указанные города хотя бы по одному разу с последующим возвратом в исходный город.
Новый!!: Временная сложность алгоритма и Задача коммивояжёра · Узнать больше »
Задача о порядке перемножения матриц
Задача о порядке перемножения матриц — классическая задача динамического программирования, в которой дана последовательность матриц A_1, A_2, \dots, A_n и требуется минимизировать количество скалярных операций для вычисления их произведения.
Новый!!: Временная сложность алгоритма и Задача о порядке перемножения матриц · Узнать больше »
Задача о покрытии множества
Задача о покрытии множества является классическим вопросом информатики и теории сложности.
Новый!!: Временная сложность алгоритма и Задача о покрытии множества · Узнать больше »
Быстрая сортировка
Быстрая сортировка, сортировка Хоара (quicksort), часто называемая qsort (по имени в стандартной библиотеке языка Си) — широко известный алгоритм сортировки, разработанный английским информатиком Чарльзом Хоаром во время его работы в МГУ в 1960 году.
Новый!!: Временная сложность алгоритма и Быстрая сортировка · Узнать больше »
Быстрое преобразование Фурье
Быстрое преобразование Фурье (БПФ, FFT) — алгоритм быстрого вычисления дискретного преобразования Фурье (ДПФ).
Новый!!: Временная сложность алгоритма и Быстрое преобразование Фурье · Узнать больше »
Базис Грёбнера
Ба́зис Грёбнера — множество, которое порождает идеал заданного кольца многочленов, обладающее специальными свойствами.
Новый!!: Временная сложность алгоритма и Базис Грёбнера · Узнать больше »
Вычислительная сложность
Вычисли́тельная сло́жность — понятие в информатике и теории алгоритмов, обозначающее функцию зависимости объёма работы, которая выполняется некоторым алгоритмом, от размера входных данных.
Новый!!: Временная сложность алгоритма и Вычислительная сложность · Узнать больше »
Вероятностный алгоритм
Вероятностный алгоритм — алгоритм, предусматривающий обращение на определённых этапах своей работы к генератору случайных чисел с целью получения экономии во времени работы за счёт замены абсолютной достоверности результата достоверностью с некоторой вероятностью.
Новый!!: Временная сложность алгоритма и Вероятностный алгоритм · Узнать больше »
Вероятностная машина Тьюринга
Обобщение детерминированной машины Тьюринга, в которой, из любого состояния и значений на ленте, машина может совершить один из нескольких (можно считать, без ограничения общности — двух) возможных переходов, а выбор осуществляется вероятностным образом (подбрасыванием монетки) Вероятностная Машина Тьюринга похожа на недетерминированную машину Тьюринга, только вместо недетерминированного перехода машина выбирает один из вариантов с некоторой вероятностью.
Новый!!: Временная сложность алгоритма и Вероятностная машина Тьюринга · Узнать больше »
Граф (математика)
Неориентированный граф с шестью вершинами и семью рёбрами Граф — абстрактный математический объект, представляющий собой множество вершин графа и набор рёбер, то есть соединений между парами вершин.
Новый!!: Временная сложность алгоритма и Граф (математика) · Узнать больше »
Двоичный поиск
Двоичный (бинарный) поиск (также известен как метод деления пополам и дихотомия) — классический алгоритм поиска элемента в отсортированном массиве (векторе), использующий дробление массива на половины.
Новый!!: Временная сложность алгоритма и Двоичный поиск · Узнать больше »
Двоичное дерево
Двои́чное де́рево — иерархическая структура данных, в которой каждый узел имеет не более двух потомков (детей).
Новый!!: Временная сложность алгоритма и Двоичное дерево · Узнать больше »
Динамическое программирование
Динамическое программирование в теории управления и теории вычислительных систем — способ решения сложных задач путём разбиения их на более простые подзадачи.
Новый!!: Временная сложность алгоритма и Динамическое программирование · Узнать больше »
Линейное программирование
Линейное программирование — математическая дисциплина, посвящённая теории и методам решения экстремальных задач на множествах n-мерного векторного пространства, задаваемых системами линейных уравнений и неравенств.
Новый!!: Временная сложность алгоритма и Линейное программирование · Узнать больше »
Ловас, Ласло
Ласло Ловас (Lovász László,; род. 9 марта 1948) — венгерский, известный работами по комбинаторике, за которые он был награждён многими престижными премиями.
Новый!!: Временная сложность алгоритма и Ловас, Ласло · Узнать больше »
Логарифм
двоичного логарифма Логари́фм числа b по основанию a (от λόγος — «слово», «отношение» и ἀριθμός — «число») определяется как показатель степени, в которую надо возвести основание a, чтобы получить число b. Обозначение: \log_a b, произносится: «логарифм b по основанию a».
Новый!!: Временная сложность алгоритма и Логарифм · Узнать больше »
