Напишите программу (или функцию), которая демонстрирует четыре общих больших сложности времени, в зависимости от того, как она выполняется. В любой форме оно принимает положительное целое число N, которое, как вы можете предположить, меньше 2 31 .
Когда программа запускается в своем первоначальном виде, она должна иметь постоянную сложность. То есть сложность должна быть Θ (1) или, что то же самое, Θ (1 ^ N) .
Когда программа перевернута и запущена, она должна иметь линейную сложность. То есть сложность должна быть Θ (N) или, что то же самое, Θ (N ^ 1) .
(Это имеет смысл, такN^1
как1^N
наоборот.)Когда программа в два раза , т.е. сцеплены к себе, и работать она должна иметь экспоненциальную сложность, а именно 2 N . То есть сложность должна быть Θ (2 ^ N) .
(Это имеет смысл, поскольку2
в2^N
два раза больше, чем1
в1^N
.)Когда программа удвоилась и обратная и запустить его должен иметь полиномиальный сложности, в частности N 2 . То есть сложность должна быть Θ (N ^ 2) .
(Это имеет смысл, такN^2
как2^N
наоборот.)
Эти четыре случая - единственные, с которыми вам нужно разобраться.
Обратите внимание, что для точности я использую нотацию большого тета (no) вместо большого O, потому что время выполнения ваших программ должно быть ограничено как сверху, так и снизу требуемыми сложностями. В противном случае простое написание функции в O (1) удовлетворяет всем четырем точкам. Здесь не так уж важно понимать нюанс. Главным образом, если ваша программа выполняет k * f (N) операций для некоторой константы k, то это, вероятно, в Θ (f (N)).
пример
Если бы оригинальная программа была
ABCDE
затем запуск должен занять постоянное время. То есть, независимо от того, является ли вход N 1 или 2147483647 (2 31 -1), или любое другое значение между ними, оно должно завершиться примерно за то же время.
Обращенная версия программы
EDCBA
должно занимать линейное время в терминах N. То есть время, необходимое для завершения, должно быть примерно пропорционально N. Поэтому N = 1 занимает меньше всего времени, а N = 2147483647 - больше всего.
Удвоенная версия программы
ABCDEABCDE
должны принимать два-к-N раз , с точки зрения N. То есть, время, необходимое для завершения должна быть примерно пропорциональна 2 N . Таким образом, если N = 1 заканчивается примерно через секунду, N = 60 займет больше времени, чем возраст вселенной для завершения. (Нет, вам не нужно проверять это.)
Удвоенная и перевернутая версия программы
EDCBAEDCBA
должно занять время в квадрате в терминах N. То есть время, необходимое для завершения, должно быть примерно пропорционально N * N. Таким образом, если N = 1 заканчивается примерно через секунду, N = 60 потребовалось бы около часа для завершения.
подробности
Вам нужно показать или утверждать, что ваши программы работают в сложностях, о которых вы говорите. Предоставление некоторых временных данных является хорошей идеей, но также попытайтесь объяснить, почему теоретически сложность является правильной.
Хорошо, если на практике время, затрачиваемое вашими программами, не совсем отражает их сложность (или даже детерминированность). Например, вход N + 1 может иногда работать быстрее, чем N.
Среда, в которой вы запускаете свои программы, имеет значение. Вы можете сделать основные предположения о том, что популярные языки никогда не намеренно тратят время на алгоритмы, но, например, если вы знаете, что ваша конкретная версия Java реализует пузырьковую сортировку вместо более быстрого алгоритма сортировки , то вам следует принять это во внимание, если вы выполняете какую-либо сортировку ,
Для всех сложностей здесь предположим, что мы говорим о сценариях наихудшего случая , а не наилучшем или среднем случае.
Пространственная сложность программ не имеет значения, только временная сложность.
Программы могут выводить что угодно. Имеет значение только то, что они принимают положительное целое число N и имеют правильные временные сложности.
Комментарии и многострочные программы разрешены. (Вы можете предположить, что
\r\n
обратное -\r\n
для совместимости с Windows.)
Big O Напоминания
От самого быстрого до самого медленного O(1), O(N), O(N^2), O(2^N)
(порядок 1, 2, 4, 3 выше).
Более медленные условия всегда доминируют, например O(2^N + N^2 + N) = O(2^N)
.
O(k*f(N)) = O(f(N))
для постоянной к. Так O(2) = O(30) = O(1)
и O(2*N) = O(0.1*N) = O(N)
.
Помните O(N^2) != O(N^3)
и O(2^N) != O(3^N)
.
Аккуратный большой O шпаргалка.
счет
Это нормальный код гольфа. Самая короткая оригинальная программа (с постоянным временем) в байтах побеждает.
источник
n = input(); for i in xrange(n): pass
имеет экспоненциальную сложность, потому что она принимает2 ** k
шаги, гдеk = log_2(n)
находится размер ввода. Вы должны уточнить, так ли это на самом деле, поскольку это резко меняет требования.Ответы:
Python 3 , 102 байта
Попробуйте онлайн!
Это O (1 ^ n), так как это то, что делает программа:
Перевернутый:
Попробуйте онлайн!
Это O (n ^ 1), так как это то, что делает программа:
Вдвое:
Попробуйте онлайн!
Это O (2 ^ n), так как это то, что делает программа:
Вдвое и наоборот:
Попробуйте онлайн!
Это O (n ^ 2), так как это то, что делает программа:
источник
input()
?k
входl
является одним и тем же, так что вы все еще вычисляете1**k
, верно? Что должно занятьO(log(k))
время, несмотря на тот факт, что вы, я и все заранее знаем, что это одно?Perl 5,
827371 + 1 (для флага -n) = 72 байтаЯ уверен, что могу играть в это (намного) больше, но это время ложиться спать, я потратил достаточно времени на отладку, как есть, и в любом случае я горжусь тем, что у меня есть.
Сама программа не использует ввод, а просто оценивает строку, начинающуюся с комментария, а затем выполняет подстановку одной строки, так что это явно в постоянном времени. Это в основном эквивалентно:
Вдвое:
Бит, который на самом деле занимает экспоненциальное время, является вторым значением: он оценивает команду
say for(1..2**$_)
, в которой перечислены все числа от 1 до 2 ^ N, что явно занимает экспоненциальное время.Перевернутый:
Это (наивно) вычисляет суммирование входных данных, которое явно занимает линейное время (так как каждое добавление происходит в постоянном времени). Код, который фактически запускается, эквивалентен:
Последняя строка просто так, что когда эти команды повторяются, это займет квадратичное время.
В обратном порядке и в два раза:
Теперь это берет суммирование суммы ввода (и добавляет ее к суммированию ввода, но неважно). Так как это делает заказ
N^2
сложения, это занимает квадратичное время. Это в основном эквивалентно:Вторая строка находит суммирование ввода, делая
N
дополнения, в то время как четвертая делаетsummation(N)
сложения, что естьO(N^2)
.источник
$x.=q;##say...
вместо$x.=q;#say...
хотя (с двумя#
вместо 1). (Это объясняет, почему вы насчитали 76 байтов вместо 75). Кроме того, вы должны посчитать-n
флаг в вашем byountount, так как ваша программа мало что делает без него.eval
иs///
. Если вы делаетеeval
первое, вам нужен только один#
. Хороший улов!#
:$x=~s/#//;
перевернутые продукты;//#/s~=x$
, которые в вашем контексте ничего не делают, как это было бы с ведущими#
. (Я не проверял это все же). Независимо от этого, есть +1!На самом деле , 20 байтов
Попробуйте онлайн!
Входные данные:
5
Выход:
Перевернутый:
Попробуйте онлайн!
Выход:
Вдвое:
Попробуйте онлайн!
Выход:
Вдвое и наоборот:
Попробуйте онлайн!
Выход:
Смысл
На самом деле это основанный на стеке язык.
abc
это программа, которая имеет сложность O (1 n ), а ее двойник имеет сложность O (2 n ).def
это программа, которая имеет сложность O (n 1 ), а ее двойник имеет сложность O (n 2 ).Тогда мое представление
"abc"ƒ"fed"
, гдеƒ
это оценить. Таким образом,"fed"
не будет оцениваться.Генерация индивидуальной программы
Псевдокод первого компонента
;(1╖╜ⁿr
:Псевдокод второго компонента
;(1╖╜ⁿ@r
:источник
Желе , 20 байт
Отчасти вдохновлено решением Actual Leaky Nun .
Ведущие и конечные новые строки имеют большое значение.
Обычный:
Попробуйте онлайн!
Входные данные:
5
Выход:
Перевернутый:
Попробуйте онлайн!
Входные данные:
5
Выход:
двойной
Попробуйте онлайн!
Входные данные:
5
Выход:
Вдвое и наоборот
Попробуйте онлайн!
Входные данные:
5
Выход:
объяснение
Ключ здесь in
Ŀ
, что означает «вызывает ссылку в индексе n как монаду». Ссылки индексируются сверху вниз, начиная с 1, исключая основную ссылку (самую нижнюю).Ŀ
также является модульным, поэтому, если вы попытаетесь позвонить по ссылке номер 7 из 5 ссылок, вы на самом деле позвоните по ссылке 2.Ссылка, вызываемая в этой программе, всегда указывается в индексе 10 (
⁵
) независимо от того, какая это версия программы. Однако какая ссылка находится в индексе 10, зависит от версии.То,
⁵
что появляется после каждогоĿ
, есть, поэтому оно не ломается при обращении. Программа выдаст ошибку во время разбора, если номер не был ранееĿ
. Наличие⁵
после него - это неуместный нилад, который просто идет прямо к выводу.Оригинальная версия вызывает ссылку
‘
, которая вычисляет n + 1.Обращенная версия вызывает ссылку
R
, которая генерирует диапазон 1 .. n.Удвоенная версия вызывает ссылку
2*R
, которая вычисляет 2 n и генерирует диапазон 1 .. 2 n .Удвоенная и обращенная версия вызывает ссылку
²R
, которая вычисляет n 2 и генерирует диапазон 1 .. n 2 .источник
Befunge-98 , 50 байтов
Обычный
Это, безусловно, самая простая программа из 4 - выполняются только следующие команды:
Эта программа делает некоторые ненужные вещи перед тем, как нажать «поворот направо» (
]
) и стрелку. Затем он нажимает 2 команды «принять ввод». Поскольку на входе присутствует только 1 число и из-за того, как TIO обрабатывает&
s, программа завершается через 60 секунд. Если есть 2 входа (и потому что я могу без добавления байтов), IP перейдет в функцию «завершения программы».Попробуйте онлайн!
Перевернутый
Этот немного сложнее. соответствующие команды следующие:
что эквивалентно
Важной частью здесь является
:. 1-:!k@
немного. Это полезно, потому что, пока мы помещаем правильную сложность в стек перед тем, как выполнить ее в более короткие сроки, мы можем получить желаемую. Это будет использоваться в оставшихся 2 программах таким образом.Попробуйте онлайн!
двойной
И соответствующие команды:
Эта программа идет в 2 цикла. Во-первых, он следует тем же путем, что и обычная программа, которая помещает 1 и N в стек, но вместо перехода ко второму
&
, IP перепрыгивает комментарий в цикл, который выдвигает2^N
:Другие биты в строке 4 пропускаются с использованием
;
sПосле того, как (2 ^ N) помещено в стек, мы перемещаемся вниз по линии в вышеупомянутый цикл печати. Из-за первого цикла сложность времени равна Θ (N + 2 ^ N), но это уменьшает до Θ (2 ^ N).
Попробуйте онлайн!
Вдвое и наоборот
Соответствующие команды:
Это работает почти идентично обращенной программе, но
N^2
не извлекается из стека, потому что первая строка второй копии программы добавляется к последней строке первой, что означает, что команда drop ($
) никогда не выполняется Итак, мы идем в цикл печати сN^2
верхней части стека.Попробуйте онлайн!
источник