Time complexity что это

Замечания

Необходимо подчеркнуть, что степень роста наихудшего времени выполнения — не единственный или самый важный критерий оценки алгоритмов и программ. Приведем несколько соображений, позволяющих посмотреть на критерий времени выполнения с других точек зрения:

1. Если создаваемая программа будет использована только несколько раз, тогда стоимость написания и отладки программы будет доминировать в общей стоимости программы, то есть фактическое время выполнения не окажет существенного влияния на общую стоимость. В этом случае следует предпочесть алгоритм, наиболее простой для реализации.
2. Если программа будет работать только с «малыми» входными данными, то степень роста времени выполнения будет иметь меньшее значение, чем константа, присутствующая в формуле времени выполнения [1] . Вместе с тем и понятие «малости» входных данных зависит от точного времени выполнения конкурирующих алгоритмов. Существуют алгоритмы, такие как алгоритм целочисленного умножения, асимптотически самые эффективные, но которые никогда не используют на практике даже для больших задач, так как их константы пропорциональности значительно превосходят подобные константы других, более простых и менее «эффективных» алгоритмов. Другой пример — фибоначчиевы кучи, несмотря на асимптотическую эффективность, с практической точки зрения программная сложность реализации и высокие значения констант в формулах времени работы делают их меннее привлекательными, чем обычные бинарные пирамиды[2] .

Если решение некоторой задачи для n-вершинного графа при одном алгоритме занимает время (число шагов) порядка n C , а при другом — порядка n+n!/C, где C — постоянное число, то согласно «полиномиальной идеологии» первый алгоритм практически эффективен, а второй — нет, хотя, например, при С=10 (10 10 ) дело обстоит как раз наоборот.

1. Эффективные, но сложные алгоритмы могут быть нежелательными, если готовые программы будут поддерживать лица, не участвующие в написании этих программ. Будем надеяться, что принципиальные моменты технологии создания эффективных алгоритмов широко известны, и достаточно сложные алгоритмы свободно применяются на практике. Однако необходимо предусмотреть возможность того, что эффективные, но «хитрые» алгоритмы не будут востребованы из-за их сложности и трудностей, возникающих при попытке в них разобраться.
2. Известно несколько примеров, когда эффективные алгоритмы требуют таких больших объемов машинной памяти (без возможности использования более медленных внешних средств хранения), что этот фактор сводит на нет преимущество «эффективности» алгоритма.
3. В численных алгоритмах точность и устойчивость алгоритмов не менее важны, чем их временная эффективность.

Классы сложности

Основная статья: Класс сложности

Класс сложности — это множество задач распознавания, для решения которых существуют алгоритмы, схожие по вычислительной сложности. Два важных представителя:

Класс P

Основная статья: Класс P

Класс P вмещает все те проблемы, решение которых считается «быстрым», то есть полиномиально зависящим от размера входа. Сюда относится сортировка, поиск во множестве, выяснение связности графов и многие другие.

Класс NP

Основная статья: класс NP

Класс NP содержит задачи, которые недетерминированная машина Тьюринга в состоянии решить за полиномиальное количество времени. Следует заметить, что недерминированная машина Тьюринга машина является лишь абстрактной моделью, в то время как современные компьютеры соответствуют детерминированной машине Тьюринга с ограниченной памятью. Таким образом, класс NP включает в себя класс P, а также некоторые проблемы, для решения которых известны лишь алгоритмы, экспоненциально зависящие от размера входа (т.е. неэффективные для больших входов). В класс NP входят многие знаменитые проблемы, такие как задача коммивояжёра, задача выполнимости булевых формул, факторизация и др.

Проблема равенства классов P и NP

Основная статья: Равенство классов P и NP

Вопрос о равенстве этих двух классов считается одной из самых сложных открытых проблем в области теоретической информатики. Математический институт Клэя включил эту проблему в список проблем тысячелетия, предложив награду размером в один миллион долларов США за её решение.

Знаменитые ученые

• Стивен Кук
• Ричард Карп
• Леонид Левин
• Александр Разборов
• Эди Шеймир

См. также

• Класс сложности
• Алгоритм
• Аппроксимация
• Сведение (теория сложности вычислений)
• «O» большое и «o» малое

Ссылки

1. ↑Кормен, Томас Х.; Лейзерсон, Чарльз И.; Ривест, Рональд Л.; Штайн, Клифорд Алгоритмы: построение и анализ, 2-е издание = Introduction to Algorithms second edition. — М.: «Вильямс», 2005. — С. 71. — ISBN 5-8459-0857-4
2. ↑Кормен, Томас Х.; Лейзерсон, Чарльз И.; Ривест, Рональд Л.; Штайн, Клифорд Алгоритмы: построение и анализ, 2-е издание = Introduction to Algorithms second edition. — М.: «Вильямс», 2005. — С. 558 — 559. — ISBN 5-8459-0857-4
3. ↑А.А.Зыков Основы теории графов. — 3-е изд. — М.: Вузовская книга, 2004. — С. 10. — 664 с. — ISBN 5-9502-0057-8

• Курсы по теории вычислимости и сложности вычислений
• Юрий Лифшиц «Современные задачи теоретической информатики». Курс лекций по алгоритмам для NP-трудных задач.
• А. А. РазборовTheoretical Computer Science: взгляд математика // Компьютерра. — 2001. — № 2. (альтернативная ссылка)
• А. А. РазборовО сложности вычислений // Математическое просвещение. — МЦНМО, 1999. — № 3. — С. 127-141.

Wikimedia Foundation . 2010 .

Сколько стоят операции над list, set и dict в Python? Разбираемся с временной сложностью

Временная сложность алгоритма часто обозначается нотацией «О» большое. Разбираемся, что это и какова сложность операций над коллекциями в Python.

Автор перевода Иван Капцов

Программисту, работающему с данными, крайне важно выбирать правильные структуры данных для решения поставленной задачи, ведь выбор неправильного типа данных плохо влияет на производительность приложения. В этой статье объясняется нотация «О» большое и сложность ключевых операций структур данных в CPython.

Что означает нотация «O» большое?

В алгоритме выполняется ряд операций. Эти операции могут включать в себя итерацию по коллекции, копирование элемента или всей коллекции, добавление элемента в коллекцию, вставку элемента в начало или конец коллекции, удаление элемента или обновление элемента в коллекции.

«O» большое служит обозначением временной сложности операций алгоритма. Она показывает, сколько времени потребуется алгоритму для вычисления требуемой операции. Можно также измерить пространственную сложность (сколько места занимает алгоритм), но в этой статье мы сосредоточимся на временной.

Проще говоря, нотация «O» большое — это способ измерения производительности операции на основе размера ввода, известного как n.

Значения нотации «О» большое

На письме временная сложность алгоритма обозначается как O(n), где n — размер входной коллекции.

O(1)

Обозначение константной временной сложности. Независимо от размера коллекции, время, необходимое для выполнения операции, константно. Это обозначение константной временной сложности. Эти операции выполняются настолько быстро, насколько возможно. Например, операции, которые проверяют, есть ли внутри коллекции элементы, имеют сложность O(1).

O(log n)

Обозначение логарифмической временной сложности. В этом случае когда размер коллекции увеличивается, время, необходимое для выполнения операции, логарифмически увеличивается. Эту сложность имеют потенциально оптимизированные алгоритмы поиска.

O(n)

Обозначение линейной временной сложности. Время, необходимое для выполнения операции, прямо и линейно пропорционально количеству элементов в коллекции. Это обозначение линейной временной сложности. Это что-то среднее с точки зрения производительности. Например, если мы хотим суммировать все элементы в коллекции, нужно будет выполнить итерацию по коллекции. Следовательно, итерация коллекции является операцией O(n).

O(n log n)

Обозначение квазилинейной временной сложности. Скорость выполнения операции является квазилинейной функцией числа элементов в коллекции. Временная сложность оптимизированного алгоритма сортировки обычно равна O(n log n).

O(n^2)

Обозначение квадратичной временной сложности. Время, необходимое для выполнения операции, пропорционально квадрату элементов в коллекции.

O(n!)

Обозначение факториальной временной сложности. Каждая операция требует вычисления всех перестановок коллекции, следовательно требуемое время выполнения операции является факториалом размера входной коллекции. Это очень медленно.

Нотация «O» большое относительна. Она не зависит от машины, игнорирует константы и понятна широкой аудитории, включая математиков, технологов, специалистов по данным и т. д.

Благоприятные, средние и худшие случаи

При вычислении временной сложности операции можно получить сложность на основе благоприятного, среднего или худшего случая.

Благоприятный случай. Как следует из названия, это сценарий, когда структуры данных и элементы в коллекции вместе с параметрами находятся в оптимальном состоянии. Например, мы хотим найти элемент в коллекции. Если этот элемент оказывается первым элементом коллекции, то это лучший сценарий для операции.

Средний случай. Определяем сложность на основе распределения значений входных данных.

Худший случай. Структуры данных и элементы в коллекции вместе с параметрами находятся в наиболее неоптимальном состоянии. Например, худший случай для операции, которой требуется найти элемент в большой коллекции в виде списка — когда искомый элемент находится в самом конце, а алгоритм перебирает коллекцию с самого начала.

Коллекции Python и их временная сложность

Список (list)

Список является одной из самых важных структур данных в Python. Можно использовать списки для создания стека или очереди. Списки — это упорядоченные и изменяемые коллекции, которые можно обновлять по желанию.

Операции списка и их временная сложность

Вставка: O(n).
Получение элемента: O(1).
Удаление элемента: O(n).
Проход: O(n).
Получение длины: O(1).

Множество (set)

Множества также являются одними из наиболее используемых типов данных в Python. Множество представляет собой неупорядоченную коллекцию. Множество не допускает дублирования, и, следовательно, каждый элемент в множестве уникален. Множество поддерживает множество математических операций, таких как объединение, разность, пересечение и так далее.

Операции с множествами и их временная сложность

Проверить наличие элемента в множестве: O(1).
Отличие множества A от B: O(длина A).
Пересечение множеств A и B: O(минимальная длина A или B).
Объединение множеств A и B: O(N) , где N это длина (A) + длина (B).

Словарь (dict)

Словарь — это коллекция пар ключ-значение. Ключи в словаре уникальны, чтобы предотвратить коллизию элементов. Это чрезвычайно полезная структура данных.

Словари индексируются по ключам, которые могут быть строками, числами или даже кортежами со строками, числами или кортежами. Над словарём можно выполнить ряд операций, таких как сохранение значения для ключа, извлечение элемента на основе ключа, или итерация по элементам и так далее.

Операции со словарями и их временная сложность

Здесь мы считаем, что ключ используется для получения, установки или удаления элемента.

Получение элемента: O(1).
Установка элемента: O(1).
Удаление элемента: O(1).
Проход по словарю: O(n).

Вычислительная сложность машинного обучения. Базовые принципы

Чуть ранее, в статье временная сложность алгоритмов машинного обучения, я разбирал временную сложность некоторых алгоритмов из библиотеки scykit-learn. Настало время немного подробнее остановиться на том, как в принципе считается вычислительная сложность data science.

Вычислительная сложность (или асимптотическая сложность или производительность) — это свойство алгоритма. Она определяется функцией, которая показывает насколько ухудшается работа алгоритма с усложнением поставленной задачи.

Вот пять основных правил расчета вычислительной сложности:

• если для математической функции \(f\) алгоритму необходимо выполнить действия \(f(N)\) раз, то для этого ему понадобится сделать \(O(f(N))\) шагов.
• если алгоритм выполняет одну операцию, состоящую из \(O(f(N))\) шагов, а затем вторую, состоящую из \(O(g(N))\) шагов, то общая производительность f и g суммируется \(O(f(N) + g(N))\)
• если алгоритму необходимо сделать \(O(f(N) + g(N))\) шагов и область значений N функции \(f(N)\) больше чем у \(g(N)\), то вычислительную сложность можно упростить до \(f(N)\)
• если алгоритму внутри каждого шага \(O(f(N))\) одной операции приходится выполнять еще \(O(g(N))\) шагов другой операции, то общая производительность составляет \(O(f(N)*g(N))\)
• постоянными множителями (константами) можно пренебречь: \(O(C*f(N))\) и \(O(f(C*N))\) можно записать как \(O(f(N))\)

Нотация «O» большое всего лишь указывает на то, что мы рассматриваем ситуацию, когда алгоритму для завершения необходимо потребить максимальное возможное количество (худший случай). В предыдущей статье рассматривался частный случай, входящий в обобщенное понятие вычислительной сложности — временная сложность алгоритмов МО. Грубо говоря, объем задачи алгоритма всегда связан с вычислительными ресурсами — временем (или количеством шагов) вычислений и пространством (или объемом памяти), необходимыми для завершения задачи. Поэтому в различной специальной литературе по машинному обучению, где рассматриваются частные случаи алгоритмов, можно встретить отсылки как к вычислительной сложности в целом так и к сложности по времени или по памятми.

На практике чаще всего встречаются следующие сложности:

• \(O(1)\) вне зависимости от сложности задачи время выполнения алгоритма постоянно
• \(O(\log(N))\) на каждом шаге алгоритма происходит деление количества рассматриваемых элементов на фиксированный коэффициент
• \(O(N)\) рост числа входов вызывает линейный рост производительности
• \(O(N*\log(N))\) алгоритм с логарифмической сложностью, на каждом шаге которого производится дополнительная операция с каждым элементом
• \(O(N^2)\) перебор всех данных, а затем повторный их перебор. Степень может быть другой, что, очевидно, влияет на сложность вычислений.
• \(O(2^N)\) экспоненциальная сложность и \(O(!N)\) факториальная сложность

Задачи со сложностью до \(O(N*\log(N))\) включительно решаемы. При грамотном управлении количеством входных данных решаемы и задачи со степенной сложностью. Экспоненциальные и факториальные сложности, в виду в целом большого входного объема данных, в МО неприменимы.

Ключевым вопросом в оценке сложности алгоритмов МО является их класс, определяющий требования ко времени и ресурсам памяти, применительно к некой абстрактной машине (часто рассматривается детерминированная машина, в частности, машина Тьюринга). Для детерминированных машин определены следующие классы:

• \(DTIME(f(N))\) задачи, которые машина решает за время \(f(N)\). Временная сложность таким образом будет составлять \(O(f(N))\)
• \(P\) задачи, с которыми машина справляется за полиномиальное время
• \(EXPTIME(EXP)\) задачи, с которыми машина справляется за экспоненциальное время

Для недетерминированных машин:

• \(NTIME(f(N))\) задачи, которые машина решает за время \(f(N)\). Временная сложность, таким образом будет, составлять \(O(f(N))\)
• \(NP\) задачи, с которыми машина справляется за полиномиальное время
• \(NEXPTIME(EXP)\) задачи, с которыми машина справляется за экспоненциальное время

Аналогичным образом задачи делятся в зависимости от потребляемого объема памяти.

Не вдаваясь в подроности, в общем случае \(P \subseteq NP\), экспоненциальные задачи, по сути, не считаемые, а задачей построения алгоритмов МО, в том числе, является их сведение к менее затратному классу. Задачи, которые входят в класс NP и к которым можно свести любые другие задачи этого класса за полиномиальное время называются NP-полными. NP-сложные задачи необязательно относятся к классу NP.

Время обучения для алгоритмов МО

Фактическое время работы алгоритма МО зависит от конкретной машины, на которой алгоритм реализован. В общем случае алгоритм обучения с учителем имеет доступ к множеству примеров, классу гипотез, функции потерь и обучающему набору, взятому из множества примеров. Четкого понятия размера входных данных для такого алгоритма не существует, т.к. если мы предъявляем алгоритму избыточное количество обучающих примеров, он может игнорировать лишние. Поэтому увеличение размера обучающего набора не ведет к тому, что проблема обучения становится более трудной. кроме того, алгоритм обучения может передавать часть вычислений выходной гипотезе, в случае, когда такая гипотеза определена как функция, сохраняющая обучающий набор. Для этого вводятся понятия времени обучения и времени предсказания. Будем рассматривать алгоритмы, чье время предсказания не превышает время обучения.

Вычислительная сложность алгоритма обучения определяется в два этапа:

• дана функция \(f : (0, 1)^2 \rightarrow \mathbb\), задача обучения \((Z, H, l)\) и алгоритм обучения \(A\). Алгоритм \(A\) решает задачу обучения за время \(O(f)\), если существует постоянное число \(c\) такое, что для любого распределения вероятности \(D\) на \(Z\) и входных параметров \(\epsilon, \delta \in (0, 1)\) справедливо следующее утверждение: если \(A\) имеет доступ к примерам, независимо выбранным из распределения \(D\), то, во-первых, \(A\) завершается, выполнив не более \(c f(\epsilon, \delta)\) операций, во-вторых, выход \(A\) обозначаемый как \(h\) можно применять для предсказания метки нового примера и при этом будет выполнено не более \(c f(\epsilon, \delta)\) операций и, в-третьих, выход \(A\) вероятно почти корректен, т.е. с вероятностью не ниже \(1 — \delta\) (для случайной выборки, которую получает \(A\)) \(>(>) \leq <\min_<\scriptscriptstyle h'\in H>>><(h'_<\scriptscriptstyle A>>) + \epsilon\)
• далее, рассматриваем последовательность проблем обучения \(<(>, >, >)^<\scriptscriptstyle<\infty>>_>\), где проблема \(n\) описывается областью примеров \(>\), классом гипотез \(>\) и функцией потерь \(>\). Если \(A\) спроектирован для проблем обучения такого вида и задана функция \(g : \mathbb x (0, 1)^2 \rightarrow \mathbb\), то считается, что время работы \(A\) на вышеупомянутой последовательности равно \(O(g)\), если для всех \(n\) \(A\) решает проблему \((>, >, >)\) за время \(O(>)\), где функция \(f : (0, 1)^2 \rightarrow \mathbb\) определяется выражением \(>(\epsilon, \delta) = >(n, \epsilon, \delta)\)

В таком случае можно сказать, что алгоритм \(A\) эффективен на последовательности \((>, >, >)\), если его время работы равно \(O(p(n, 1/\epsilon, 1/\delta))\) для некоторого полинома p. Очевидно, что вопрос об эффективном решении проблемы обучения зависит от того, как именно задача обучения представлена в виде последовательности конкретных проблем.

Более подробную информацию на эту тему можно найти в учебнике «Understanding Machine Learning», изданном в Cambridge University Press в 2014-ом году.

• Обозначения в анализе алгоритмов (30 Sep 2020)
• Вычислительная сложность машинного обучения. Базовые принципы (19 Oct 2019)
• Зависимость вычислений в scikit-learn от данных и модели (28 Sep 2019)
• Временная сложность алгоритмов машинного обучения (08 Sep 2019)

Особенности препроцессинга данных в scikit-learn

В статье кратко раскрываются некоторые вопросы подготовки данных с помощью scikit-learn. Замена пропусков Scikit-learn не поддерживает замену пропусков с разными.

Подготовка данных: кодирование категориальных признаков

В статье «[особенности препроцессинга данных в scikit-learn](>)» разбирались особенности кодирования признаков с помощью библиотеки scikit-learn. К сожалению.

Этот проект поддерживается KonstantinKlepikov