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

Ответ 1

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

Ответ 2

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

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

Ответ 3

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

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

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

Ответ 4

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

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

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

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

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

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

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

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

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

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

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

Ответ 5

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

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

Ответ 6

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

Однако смотреть на отдельные языки и реализации - это совсем другая история. Игнорируя на данный момент примеры из Brainfuck и т.д., Есть еще некоторые довольно приличные примеры.

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

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

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