Программирование питания: O (1 ^ N), O (N ^ 1), O (2 ^ N), O (N ^ 2) все в одном

65

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

  1. Когда программа запускается в своем первоначальном виде, она должна иметь постоянную сложность. То есть сложность должна быть Θ (1) или, что то же самое, Θ (1 ^ N) .

  2. Когда программа перевернута и запущена, она должна иметь линейную сложность. То есть сложность должна быть Θ (N) или, что то же самое, Θ (N ^ 1) .
    (Это имеет смысл, так N^1как 1^Nнаоборот.)

  3. Когда программа в два раза , т.е. сцеплены к себе, и работать она должна иметь экспоненциальную сложность, а именно 2 N . То есть сложность должна быть Θ (2 ^ N) .
    (Это имеет смысл, поскольку 2в 2^Nдва раза больше, чем 1в 1^N.)

  4. Когда программа удвоилась и обратная и запустить его должен иметь полиномиальный сложности, в частности 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, является само число N (что, кстати, не является обычным понятием размера ввода: это будет обрабатывать вход N как размер журнала N). Таким образом, существует только один случай для каждого N, который является одновременно лучшим, худшим и средним случаем.
ShreevatsaR
5
Похоже, что вы отклонились от обычных определений сложности. Мы всегда определяем временную сложность алгоритма как функцию размера его входных данных . В случае, когда входное значение является числом, размер входного значения представляет собой логарифм base-2 этого числа. Таким образом, программа n = input(); for i in xrange(n): passимеет экспоненциальную сложность, потому что она принимает 2 ** kшаги, где k = log_2(n)находится размер ввода. Вы должны уточнить, так ли это на самом деле, поскольку это резко меняет требования.
wchargin

Ответы:

36

Python 3 , 102 байта

try:l=eval(input());k=1#)]0[*k**l(tnirp
except:k=2#2=k:tpecxe
print(k**l*[0])#1=k;))(tupni(lave=l:yrt

Попробуйте онлайн!

Это O (1 ^ n), так как это то, что делает программа:

  • оценить вход
  • создать массив [0]
  • распечатай это

Перевернутый:


try:l=eval(input());k=1#)]0[*l**k(tnirp
except:k=2#2=k:tpecxe
print(l**k*[0])#1=k;))(tupni(lave=l:yrt

Попробуйте онлайн!

Это O (n ^ 1), так как это то, что делает программа:

  • оценить вход
  • создать массив [0] * input (0 повторяется столько же раз, сколько и input)
  • распечатай это

Вдвое:

try:l=eval(input());k=1#)]0[*k**l(tnirp
except:k=2#2=k:tpecxe
print(k**l*[0])#1=k;))(tupni(lave=l:yrt
try:l=eval(input());k=1#)]0[*k**l(tnirp
except:k=2#2=k:tpecxe
print(k**l*[0])#1=k;))(tupni(lave=l:yrt

Попробуйте онлайн!

Это O (2 ^ n), так как это то, что делает программа:

  • оценить вход
  • создать массив [0]
  • распечатай это
  • попробуйте оценить вход
  • провал
  • создать массив [0] * (2 ^ input) (0 повторяется столько раз, сколько 2 ^ input)
  • распечатай это

Вдвое и наоборот:


try:l=eval(input());k=1#)]0[*l**k(tnirp
except:k=2#2=k:tpecxe
print(l**k*[0])#1=k;))(tupni(lave=l:yrt
try:l=eval(input());k=1#)]0[*l**k(tnirp
except:k=2#2=k:tpecxe
print(l**k*[0])#1=k;))(tupni(lave=l:yrt

Попробуйте онлайн!

Это O (n ^ 2), так как это то, что делает программа:

  • оценить вход
  • создать массив [0] * input (0 повторяется столько же раз, сколько и input)
  • распечатай это
  • попробуйте оценить вход
  • провал
  • создайте массив [0] * (input ^ 2) (0 повторяется столько раз, сколько введено в квадрате)
  • распечатай это
Дрянная Монахиня
источник
Почему он не зависает в ожидании взаимодействия с пользователем при нескольких вызовах input()?
Джонатан Аллан
1
Это лазейка, что "конец передачи" передается в конце передачи?
Утренняя монахиня
1
Вы можете это объяснить?
Мозговой
1
Re: аргумент «конец файла», вы смотрите на вещи задом наперед. Когда вы используете терминал, запросы на ввод зависают, потому что с ним что-то связано; Ctrl-D может быть отправлен для явной отправки без ввода. Если вход подключен к пустому файлу (как это делает TIO, если вы оставляете поле ввода пустым), или если он подключен к файлу, в котором все входные данные были прочитаны, нет необходимости в запросе на ввод для выполнения каких-либо действий; он уже знает, что нет ввода. В UNIX / Linux «конец файла» и «нет доступного ввода» неразличимы для обычных файлов.
3
В первом случае kвход lявляется одним и тем же, так что вы все еще вычисляете 1**k, верно? Что должно занять O(log(k))время, несмотря на тот факт, что вы, я и все заранее знаем, что это одно?
Ричард Раст
18

Perl 5, 82 73 71 + 1 (для флага -n) = 72 байта

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

#x$=_$;
$x.=q;#say for(1..2**$_)#)_$..1(rof _$=+x$;;
eval $x;$x=~s/#//;

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

$x="#";
eval $x;
$x=~s/#//;

Вдвое:

#x$=_$;
$x.=q;#say for(1..2**$_)#)_$..1(rof _$=+x$;;
eval $x;$x=~s/#//;
#x$=_$;
$x.=q;#say for(1..2**$_)#)_$..1(rof _$=+x$;;
eval $x;$x=~s/#//;

Бит, который на самом деле занимает экспоненциальное время, является вторым значением: он оценивает команду say for(1..2**$_), в которой перечислены все числа от 1 до 2 ^ N, что явно занимает экспоненциальное время.

Перевернутый:

;//#/s~=x$;x$ lave
;;$x+=$_ for(1..$_)#)_$**2..1(rof yas#;q=.x$
;$_=$x#

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

$x+=$_ for(1..$_);
$_=$x;

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

В обратном порядке и в два раза:

;//#/s~=x$;x$ lave
;;$x+=$_ for(1..$_)#)_$**2..1(rof yas#;q=.x$
;$_=$x#
;//#/s~=x$;x$ lave
;;$x+=$_ for(1..$_)#)_$**2..1(rof yas#;q=.x$
;$_=$x#

Теперь это берет суммирование суммы ввода (и добавляет ее к суммированию ввода, но неважно). Так как это делает заказ N^2сложения, это занимает квадратичное время. Это в основном эквивалентно:

$x=0;
$x+=$_ for(1..$_);
$_=$x;
$x+=$_ for(1..$_);
$_=$x;

Вторая строка находит суммирование ввода, делая Nдополнения, в то время как четвертая делает summation(N)сложения, что есть O(N^2).

Крис
источник
Большой! Делать это на обычном языке было бы сложно! Это мой upvote!
Арджун
Отлично, это очень мило. Вы, вероятно, имели в виду $x.=q;##say...вместо $x.=q;#say...хотя (с двумя #вместо 1). (Это объясняет, почему вы насчитали 76 байтов вместо 75). Кроме того, вы должны посчитать -nфлаг в вашем byountount, так как ваша программа мало что делает без него.
Дада
@Dada Я случайно переставил команды evalи s///. Если вы делаете evalпервое, вам нужен только один #. Хороший улов!
Крис
@ Крис Правильно, это действительно работает. Возможно, вы сможете опустить последнее #: $x=~s/#//;перевернутые продукты ;//#/s~=x$, которые в вашем контексте ничего не делают, как это было бы с ведущими #. (Я не проверял это все же). Независимо от этого, есть +1!
Дада
@Dada Хороший улов еще раз!
Крис
17

На самом деле , 20 байтов

";(1╖╜ⁿr"ƒ"rⁿ@╜╖1(;"

Попробуйте онлайн!

Входные данные: 5

Выход:

rⁿ@╜╖1(;
[0]
5

Перевернутый:

";(1╖╜@ⁿr"ƒ"rⁿ╜╖1(;"

Попробуйте онлайн!

Выход:

rⁿ╜╖1(;
[0, 1, 2, 3, 4]
5

Вдвое:

";(1╖╜ⁿr"ƒ"rⁿ@╜╖1(;"";(1╖╜ⁿr"ƒ"rⁿ@╜╖1(;"

Попробуйте онлайн!

Выход:

rⁿ@╜╖1(;
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31]
rⁿ@╜╖1(;
rⁿ@╜╖1(;
[0]

Вдвое и наоборот:

";(1╖╜@ⁿr"ƒ"rⁿ╜╖1(;"";(1╖╜@ⁿr"ƒ"rⁿ╜╖1(;"

Попробуйте онлайн!

Выход:

rⁿ╜╖1(;
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24]
rⁿ╜╖1(;
rⁿ╜╖1(;
[0, 1, 2, 3, 4]

Смысл

На самом деле это основанный на стеке язык.

  • abcэто программа, которая имеет сложность O (1 n ), а ее двойник имеет сложность O (2 n ).
  • defэто программа, которая имеет сложность O (n 1 ), а ее двойник имеет сложность O (n 2 ).

Тогда мое представление "abc"ƒ"fed", где ƒэто оценить. Таким образом, "fed"не будет оцениваться.

Генерация индивидуальной программы

Псевдокод первого компонента ;(1╖╜ⁿr:

register += 1 # register is default 0
print(range(register**input))

Псевдокод второго компонента ;(1╖╜ⁿ@r:

register += 1 # register is default 0
print(range(input**register))
Дрянная Монахиня
источник
Я никогда не думал, что это будет возможно! Отличная работа, сэр! +1
Арджун,
@Arjun Спасибо за вашу благодарность.
Утренняя монахиня
Это отлично и действительно принимает вызов, не используя комментарии IMO. Потрясающие!
ShreevatsaR
1
Ну, это на самом деле есть комментарии ... строки не оценены и являются NOPs ...
Leaky Nun
4

Желе , 20 байт

Отчасти вдохновлено решением Actual Leaky Nun .

Ведущие и конечные новые строки имеют большое значение.

Обычный:


⁵Ŀ⁵
R
R²
2*R
‘
⁵Ŀ⁵

Попробуйте онлайн!

Входные данные: 5

Выход:

610

Перевернутый:


⁵Ŀ⁵
‘
R*2
²R
R
⁵Ŀ⁵

Попробуйте онлайн!

Входные данные: 5

Выход:

[1, 2, 3, 4, 5]10

двойной


⁵Ŀ⁵
R
R²
2*R
‘
⁵Ŀ⁵

⁵Ŀ⁵
R
R²
2*R
‘
⁵Ŀ⁵

Попробуйте онлайн!

Входные данные: 5

Выход:

[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32]10

Вдвое и наоборот


⁵Ŀ⁵
‘
R*2
²R
R
⁵Ŀ⁵

⁵Ŀ⁵
‘
R*2
²R
R
⁵Ŀ⁵

Попробуйте онлайн!

Входные данные: 5

Выход:

[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25]10

объяснение

Ключ здесь 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 .

Бизнес Кот
источник
4

Befunge-98 , 50 байтов

Обычный

\+]#:\-1vk  !:;#
@k!:-1 .: ;#]#$ <;
[*:>@ 
&$< ^&;

Это, безусловно, самая простая программа из 4 - выполняются только следующие команды:

\+]
  !
  : @
&$< ^&;

Эта программа делает некоторые ненужные вещи перед тем, как нажать «поворот направо» ( ]) и стрелку. Затем он нажимает 2 команды «принять ввод». Поскольку на входе присутствует только 1 число и из-за того, как TIO обрабатывает &s, программа завершается через 60 секунд. Если есть 2 входа (и потому что я могу без добавления байтов), IP перейдет в функцию «завершения программы».

Попробуйте онлайн!

Перевернутый

;&^ <$&
 @>:*[
;< $#]#; :. 1-:!k@
#;:!  kv1-\:#]+\

Этот немного сложнее. соответствующие команды следующие:

;&^  $
  >:*[
;< $#]#; :. 1-:!k@
  :

что эквивалентно

;&^                   Takes input and sends the IP up. the ; is a no-op
  :                   Duplicates the input.
  >:*[                Duplicates and multiplies, so that the stack is [N, N^2
     $                Drops the top of the stack, so that the top is N
     ]#;              Turns right, into the loop
         :.           Prints, because we have space and it's nice to do
            1-        Subtracts 1 from N
              :!k@    If (N=0), end the program. This is repeated until N=0
;< $#]#;              This bit is skipped on a loop because of the ;s, which comment out things

Важной частью здесь является :. 1-:!k@немного. Это полезно, потому что, пока мы помещаем правильную сложность в стек перед тем, как выполнить ее в более короткие сроки, мы можем получить желаемую. Это будет использоваться в оставшихся 2 программах таким образом.

Попробуйте онлайн!

двойной

\+]#:\-1vk  !:;#
@k!:-1 .: ;#]#$ <;
[*:>@ 
&$< ^&;\+]#:\-1vk  !:;#
@k!:-1 .: ;#]#$ <;
[*:>@ 
&$< ^&;

И соответствующие команды:

\+]
  !
  :
&$< ^&;\+]#:\-1vk  !:;#
@k!:-1 .: ;#]#$ <;

Эта программа идет в 2 цикла. Во-первых, он следует тем же путем, что и обычная программа, которая помещает 1 и N в стек, но вместо перехода ко второму &, IP перепрыгивает комментарий в цикл, который выдвигает 2^N:

        vk!:    If N is 0, go to the next loop.
      -1        Subtract 1 from N
 +  :\          Pulls the 1 up to the top of the stack and doubles it
  ]#            A no-op
\               Pulls N-1 to the top again

Другие биты в строке 4 пропускаются с использованием ;s

После того, как (2 ^ N) помещено в стек, мы перемещаемся вниз по линии в вышеупомянутый цикл печати. Из-за первого цикла сложность времени равна Θ (N + 2 ^ N), но это уменьшает до Θ (2 ^ N).

Попробуйте онлайн!

Вдвое и наоборот

;&^ <$&
 @>:*[
;< $#]#; :. 1-:!k@
#;:!  kv1-\:#]+\;&^ <$&
 @>:*[
;< $#]#; :. 1-:!k@
#;:!  kv1-\:#]+\

Соответствующие команды:

;&^

;< $#]#; :. 1-:!k@

 @>:*[

  :

Это работает почти идентично обращенной программе, но N^2не извлекается из стека, потому что первая строка второй копии программы добавляется к последней строке первой, что означает, что команда drop ( $) никогда не выполняется Итак, мы идем в цикл печати с N^2верхней части стека.

Попробуйте онлайн!

MildlyMilquetoast
источник