BigO привязан к какому-то псевдокоду

Question

AllDistinct(a1 , . . . , an )
if (n = 1)
return True
for i := n down to 2
   begin
   if (LinearSearch(a1 , . . . , ai−1 ; ai ) != 0)
     return False
   end
return True

Дайте биг-О ограничение времени работы AllDistinct.Для полной оценки вы должны показать работу или кратко объяснить свой ответ.

Таким образом, фактический ответ для этого в соответствии с решением для этой проблемы - O (n ^ 2).Однако, поскольку BigO - наихудшее время выполнения, могу ли я ответить O (n ^ 100000) и сойти с рук?Нет никакого способа, которым они могут снять очки за это, так как это технически правильный ответ, верно?Хотя более полезный O (n ^ 2) очевиден в этом алгоритме, я спрашиваю, потому что у нас может быть более сложный алгоритм на предстоящем экзамене, и в случае, если я не могу выяснить «жесткую» границу, я мог бы составить очень большойзначение и оно все равно должно быть правильным, верно?

Answer 1

Это было бы тривиальным ответом на вопрос.Хотя это правильно, это ничего вам не говорит и, следовательно, ничего не стоит.Дело не в том, правильно или неправильно, а в плохом и хорошем.Чем лучше ваш ответ, тем больше очков вы получите за это.Вопрос не говорит, что вы получите кредит на ужасную плохую оценку.Плохие ответы дают плохие оценки?

(Задать вопрос о большой тэте было бы сложнее.

Answer 2

Да, если функция в O(n^2), она также в O(n^1000).

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

Если вы все-таки решили пойти по этому пути, вам, вероятно, следует выбрать что-то вроде O(n^n) или O(Ackermann(n)), поскольку, например, экспоненциальные функции отсутствуют в O(n^1000).

Другая проблема заключается в том, что вас, вероятно, попросят подтвердить и границы. Это будет трудно сделать, если вы на самом деле не знаете время работы функции. «n^n действительно большой, поэтому время работы, вероятно, будет меньше, чем это», не является доказательством. Хотя, с другой стороны, если вам удастся правильно доказать, что функция в O(n^n), вы, вероятно, получите хотя бы частичный кредит.

Answer 3

Если профессор попросит у вас BigO об этом, вы можете ответить на любой BigO, который вы думаете, но вы должны доказать это, как говорится For full credit, you must show work or briefly explain your answer.

BigO не бесполезен.Для проблем легко получить грейтер с верхним пределом (BigO);например,
Проблема сортировки: у вас есть простая пузырьковая сортировка, и вы можете доказать, что это n ^ 2 (верно?), поэтому верхняя граница задачи сортировки равна n ^ 2 (потому что существует и алгоритм, который решает ее в это время, ноесли вы продолжите математику, вы увидите, что проблема имеет нижнюю границу log (n!)).Таким образом, n ^ 2 был хорошим ответом, пока вы не докажете, что это журнал (n!).Есть много проблем, которые мы знаем только о BigO, но не о нижней границе, поэтому она не бесполезна.

Если вы можете сказать, что программа останавливается, вы всегда можете вычислить BigO с некоторой математикой, но это не всегда легко (существует даже амортизируемая сложность) но это проще, чем проблемы LowerBound.Так что BigO не так важен в алгоритме, но он не бесполезен.
Важно то, что вы понимаете, что это значит ;затем, если вы можете получить любую BigO этой программы, вы можете написать ее на экзаменационной работе, которая является функцией от ученика до числа ... и удачи.

Answer 4

Нет.

Это может быть все умно и ха!Понял тебя!но это не идея.(и вы это знаете)

Answer 5

Я был проф.Профессионалы составляют экзаменационные вопросы, и у них могут быть ошибки.Это неприятно, когда вам нужно выбросить вопрос, потому что в нем есть ошибка, и люди могут дать тривиальные ответы.В этом случае ошибка « a big-O bound».Делать экзаменационные вопросы сложно, потому что вы не хотите ошибаться в том, чтобы говорить слишком много, как какое-то непроницаемое заявление адвоката, потому что это еще больше запутает людей.Делая это, надеюсь, вы узнаете что-то полезное.Если вы видите такой неоднозначный вопрос, проф будет признателен, если вы скажете что-то вроде: «Я полагаю, вы имеете в виду хорошо биг-о».

Answer 6

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