Подтвердить что ты не робот

Правильно ли проведен анализ FrogSort в субботу утром?

В недавнем комиксе комиксов завтрашнего утреннего завтрака, автор описывает алгоритм под названием Frog Sort для сортировки списка натуральных чисел. Алгоритм описан в комиксе, но для простоты я перепечатал его здесь:

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

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

В середине комикса учитель спрашивает студентов "Что такое максимальный номер шага?", который я интерпретирую как "какое максимальное количество шагов, необходимых для завершения этого алгоритма?"; то есть, какова продолжительность выполнения алгоритма? Затем ученик отвечает "log лягушка (боксы)."

Является ли это точный анализ времени выполнения этого алгоритма? Или автор ошибается?

4b9b3361

ОТВЕТЫ

Ответ 1

Этот анализ времени выполнения явно ошибочен; мы можем получить тривиальное время выполнения Q max(n_elements, largest_element) (поскольку мы делаем квадраты n_elements, а затем каждый ящик занимает столько времени, сколько должно быть пустым, как размер его содержимого). Алгоритм сортировки, который занял менее n времени, был бы... очень неожиданным.

Если вы хотите найти больше анализов в Интернете где-то, этот алгоритм эквивалентен сорту. Если вы не знакомы с этим нелепым алгоритмом, здесь он находится в bash:

#!/bin/bash

function sort() {
    for num in "[email protected]" ; do
        (
        sleep $num
        echo $num
        ) &
    done
    wait
}

sort 6 1 3 4

Ответ 2

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

Начнем с того, что нам нужно будет установить некоторые основные правила того, как лягушки едят мух. Я предполагаю, что все лягушки могут съесть мух с постоянной скоростью r. То есть, требуется, чтобы лягушка съела одну муху, 10r секунд для лягушки, чтобы съесть десять мух и т.д. Затем сделайте (разумное) предположение, что все лягушки едят параллельно. Мы также предположим, что для того, чтобы лягушка выскочила из пустой коробки, требуется время j.

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

Одна последняя деталь - допустим, что для записи числа требуется время w.

В этом случае время выполнения этого алгоритма задается следующим образом. Предположим, что наш список чисел для сортировки - это x 1, x 2,..., x n. В этом случае время, необходимое для установки всех ящиков, будет равно n (b + f) + y (& Sigma; x i). Причина этого в том, что нам нужно получить n ящиков и поместить одну лягушку в каждую коробку (следовательно, первый член), плюс y единиц времени для каждого из мух (отсюда и второй член).

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

Наконец, мы должны рассмотреть, сколько времени потребуется для всех лягушек. Поскольку все лягушки едят параллельно, все, что нам нужно заботиться, это лягушка, у которой больше мух, чтобы поесть. Эта лягушка будет иметь x max, мухи, чтобы съесть, где x max - максимальное число в списке входных данных. Таким образом, время, проведенное лягушками при их еде, определяется r x max. Факторинг в прыжке, сделанный финальной лягушкой, лягушки, все работающие параллельно, будут совместно заканчиваться в rx max + j time.

Это означает, что общее время для алгоритма определяется выражением

n (f + b) + y & Sigma; x i + nw + rx max + j.

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

n + & Sigma; (x i) + x max + 1

Отмечая, что x max & le; & Sigma; x i, мы получаем, что общая продолжительность выполнения этого алгоритма & Theta; (n + & Sigma; x i). Другими словами, время выполнения пропорционально как количеству сортируемых номеров, так и суммарному размеру сортируемых чисел.

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

Наконец, обратите внимание, что это очень плохой алгоритм сортировки. Алгоритм подсчета сортировки мог сортировать n натуральных чисел во времени O (n + U), где U - это максимальное значение, которое должно быть отсортировано, что асимптотически лучше, чем FrogSort. Алгоритм radix sort мог бы сделать это в O (n lg U) времени, что лучше для больших значений U. Затем снова для обоих алгоритмов требуются сложные механизмы, которые, вероятно, не существовало бы в настройке, описанной комиком.

Надеюсь, это поможет!

Ответ 3

Это не ответ, но сам Зак получил удовольствие от этого. Это часть пасхального яйца на эзотерическом языке программирования cbrain, http://esolangs.org/wiki/Cbrain. Производная bf, скомпилированная с OpenCOBOL. Для того, чтобы быть вне лягушки, условное значение справедливой может быть установлено равным 2 вместо 1. frogSort в COBOL.

      *> ********************************************************
      *>  frogSort, called for help with 10-94, request for count
      *> ********************************************************
       identification division.
       program-id. frogsort.
       data division.
       working-storage section.
       01 opinion          usage binary-long.
       01 shared-value     pic 99.
          88 fair          value 1.
       01 caveman-count    pic x(12) value "[-]+++++++++".
       01 spacer           pic x(10) value spaces.

       linkage section.
       01 jars.
          05 flies        pic 9 occurs 21 times.

      *> ********************************************************
       procedure division using jars.
       start-here.
       move function length(jars) to shared-value
       display "Grog sort jars.  frogSort" end-display
       display "http://www.smbc-comics.com/?id=2831" end-display
       .

       forkyourself.
           call "fork" returning opinion end-call
           if opinion is zero then
               subtract 1 from shared-value
               if not fair then go forkyourself.
       .

       call "sleep" using by value flies(shared-value) end-call
       display
           "Jar: " function char(shared-value + 65) " reporting "
           caveman-count(1 : flies(shared-value) + 3) " flies,"
           spacer(1 : 10 - flies(shared-value))
           "that would be " flies(shared-value) " to you, futureman."
       end-display
       call "wait" using by value 0 end-call

       stop run returning 107.
       end program frogsort.

с пасхальным яйцом ногами с CALL "frogsort" ИСПОЛЬЗОВАНИЕ "012345678901234567890" END-CALL

$ ./cbrainrun 
10-12 Welcome to cbrain v0.42
cb: 1094
cb: help
Grog sort jars.  frogSort
http://www.smbc-comics.com/?id=2831
Jar: U reporting [-] flies,          that would be 0 to you, futureman.
Jar: K reporting [-] flies,          that would be 0 to you, futureman.
Jar: A reporting [-] flies,          that would be 0 to you, futureman.
Jar: L reporting [-]+ flies,         that would be 1 to you, futureman.
Jar: B reporting [-]+ flies,         that would be 1 to you, futureman.
Jar: M reporting [-]++ flies,        that would be 2 to you, futureman.
Jar: C reporting [-]++ flies,        that would be 2 to you, futureman.
Jar: N reporting [-]+++ flies,       that would be 3 to you, futureman.
Jar: D reporting [-]+++ flies,       that would be 3 to you, futureman.
Jar: O reporting [-]++++ flies,      that would be 4 to you, futureman.
Jar: E reporting [-]++++ flies,      that would be 4 to you, futureman.
Jar: P reporting [-]+++++ flies,     that would be 5 to you, futureman.
Jar: F reporting [-]+++++ flies,     that would be 5 to you, futureman.
Jar: Q reporting [-]++++++ flies,    that would be 6 to you, futureman.
Jar: G reporting [-]++++++ flies,    that would be 6 to you, futureman.
Jar: R reporting [-]+++++++ flies,   that would be 7 to you, futureman.
Jar: H reporting [-]+++++++ flies,   that would be 7 to you, futureman.
Jar: S reporting [-]++++++++ flies,  that would be 8 to you, futureman.
Jar: I reporting [-]++++++++ flies,  that would be 8 to you, futureman.
Jar: T reporting [-]+++++++++ flies, that would be 9 to you, futureman.
Jar: J reporting [-]+++++++++ flies, that would be 9 to you, futureman.