Сложность алгоритмов разных парадигм программирования

Question

Я знаю, что большинство языков программирования являются полными по Тьюрингу, но мне интересно, можно ли решить проблему с помощью алгоритма такой же сложности с любым языком программирования (и, в частности, с любой парадигмой программирования).

Toпоясните мой ответ на примере: есть ли проблема, которая может быть решена с помощью императивного алгоритма сложности x (скажем, O(n)), но не может быть решена с помощью функционального алгоритма такой же сложности (или наоборот)?

Редактировать: Сам алгоритм может быть другим. Вопрос заключается в сложности решения проблемы - с использованием любого подхода, доступного на языке.

Answer 1

В общем, нет, не все алгоритмы могут быть реализованы с одинаковым порядком сложности на всех языках.Это может быть тривиально доказано, например, с помощью гипотетического языка, который запрещает O (1) доступ к массиву.Тем не менее, нет никаких алгоритмов (насколько мне известно), которые не могли бы быть реализованы с оптимальным порядком сложности на функциональном языке.Анализ сложности псевдокода алгоритма делает определенные предположения о том, какие операции являются законными, и какие операции являются O (1).Если вы нарушите одно из этих предположений, вы можете изменить сложность реализации алгоритма, даже если язык Тьюринга завершен.Полнота по Тьюрингу не дает никаких гарантий относительно сложности любой операции.

Answer 2

Алгоритм имеет измеренное время выполнения, такое как O (n), как вы сказали, реализации алгоритма должны придерживаться того же времени выполнения, либо не реализуют алгоритм. Язык или реализация по определению не изменяют алгоритм и, следовательно, не изменяют асимптотическое время выполнения.

При этом некоторые языки и технологии могут упростить выражение алгоритма и обеспечить постоянное ускорение (или замедление) из-за того, как язык компилируется или выполняется.

Answer 3

Я думаю, что ваш первый абзац неправильный.И я думаю, что ваша правка не изменит это.

Если вы требуете, чтобы наблюдаемое поведение реализации соответствовало временной сложности алгоритма, то ...

При вычисленииСложность алгоритма делаются предположения о том, какие операции имеют постоянное время.Эти предположения - то, где вы собираетесь найти свои подсказки.

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

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

Разумные языки могут нарушить эти предположения, и иногда это необходимо, если они хотят иметь дело, скажем, с неизменными даннымиструктуры с общим состоянием, параллелизмом и т. д.

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

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

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

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

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

Answer 4

Я думаю, что в языке могут быть разные базовые операции, которые стоят O (1), например, математические операции (+, -, *, /) или доступ к переменной / массиву (a [i]), вызов функции и всеВы можете подумать.

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

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

Answer 5

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

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

Я до сих пор помню один пример много лет назад, написавший APL (на мэйнфрейме). Задача состояла в том, чтобы найти (и устранить) дубликаты в отсортированном массиве чисел. В то время большая часть программирования, которую я занимался, была на Фортране, с несколькими частями на Паскале (все еще самой последней и лучшей в то время) или на Бейсике. Я сделал то, что казалось очевидным: написал цикл, который прошел по массиву, сравнивая array[i] с array[i+1] и отслеживая пару индексов, копируя каждый уникальный элемент обратно на соответствующее количество мест, в зависимости от того, сколько элементов было уже было устранено.

Хотя это вполне сработало бы на языках, к которым я привык, это было едва ли не катастрофой в APL. Решение, которое работало намного лучше, основывалось больше на том, что было легко в APL, чем на вычислительной сложности. В частности, вы сравнили первый элемент массива с первым элементом массива после того, как он был «повернут» одним элементом. Затем вы либо сохранили массив как есть, либо удалили последний элемент. Повторяйте это, пока вы не пройдете весь массив (насколько я помню, обнаружен, когда первый элемент был меньше, чем первый элемент в повернутом массиве).

Разница была довольно простой: как и большинство реализаций APL (по крайней мере, в то время), эта была чисто интерпретатором. Отдельная операция (даже довольно сложная) была довольно быстрой, но интерпретация входного файла заняла довольно много времени. Улучшенная версия была намного короче и быстрее интерпретировалась (например, APL предоставляет элемент «вращать массив» как одну примитивную операцию, чтобы интерпретировать вместо цикла только один или два символа).

Answer 6

Если вы рассматриваете Brainfuck или саму машину Тьюринга, есть одна фундаментальная операция, которая занимает там O (n) время, хотя в большинстве других языков это можно сделать в O (1) - индексирование массив.

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