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

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) в этом алгоритме очевиден, я спрашиваю, потому что у нас может быть более сложный алгоритм на предстоящем экзамене, и на случай, если я не смогу вычислить «жесткую» границу, я мог бы составить очень большой значение, и оно все равно должно быть правильным, верно?


performance algorithm big-o pseudocode
person Snowman    schedule 31.10.2010    source источник
comment
То, что ответ технически правильный, не означает, что это хорошая работа или она полезна. Больше TA и Profs оценивают на основе вторых двух, а не первого критерия. Если это свидетельствует о вашем мыслительном процессе или личности, то, похоже, вам следует бросить программу CS и поступить на юридический факультет.   -  person Thomas M. DuBuisson    schedule 01.11.2010
comment
Я привел свои доводы, не надо быть ослом..   -  person Snowman    schedule 01.11.2010
comment
Никаких попыток быть ослом (возможно, это естественно?). На самом деле стоит серьезно задуматься. Кроме того, один из моих профессионалов давал парню +5 баллов каждый раз, когда он видел, что в финале написано «Я не знаю», потому что он так устал от людей, пытающихся пройти через BS. Профессионалы (и ассистенты) тоже люди.   -  person Thomas M. DuBuisson    schedule 01.11.2010
comment
Я просто говорю, что если выяснится, что я не знаю, я лучше напишу O(n^n) или O(n!), чем не знаю... в импровизации нет ничего плохого...   -  person Snowman    schedule 01.11.2010
comment
Эй, ребята, SO для помощи друг другу, а не для оскорблений.   -  person Mike Dunlavey    schedule 03.11.2010

Ответы (6)


arrow_upward
2
arrow_downward

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

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

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

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

person sepp2k    schedule 31.10.2010

arrow_upward
2
arrow_downward

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

(Спросить Big Theta было бы более сложным вопросом. Я бы играл хорошо :)

person Ishtar    schedule 31.10.2010
comment
Так будет ли BigTheta строгим ответом? Является ли n^2 единственным приемлемым ответом для BigTheta? Если нет, то что еще работает? Я не совсем понимаю концепцию BigTheta - person Snowman; 01.11.2010
comment
BigTheta — это нижняя и верхняя границы. Это строгий ответ: правильный ответ только один (в данном случае n^2). С BigO существует бесконечное количество правильных ответов. - person fabiofili2pi; 01.11.2010
comment
@Fabio F.: На самом деле, я считаю, что даже с Θ все равно существует бесконечное количество правильных ответов: Θ(n²), Θ(n²+1), Θ(n²+2), Θ(2n²), Θ(23n²+42) и так далее. - person Jörg W Mittag; 01.11.2010
comment
@ Jörg W Mittag: только если вы скажете, что 1 + 1 имеет бесконечное решение: 2, 2,0, 2,00, 2,000: P - то есть только разные обозначения для представления одной и той же концепции. - person fabiofili2pi; 01.11.2010

arrow_upward
1
arrow_downward

No.

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

person Martijn    schedule 31.10.2010
comment
Так зачем использовать BigO, если он может быть универсальным? Не лучше ли задать вопрос, что такое BigTheta, что такое n^2, что является точным числом, а не просто максимальным? Или, может быть, я не понимаю BigTheta.. - person Snowman; 01.11.2010
comment
что обычно подразумевается под bigO (даже если это не то, что есть по определению): lim x->inf f(x)/g(x) > 0 && lim x->inf f(x)/g(x) <= 1 - person Martijn; 01.11.2010

arrow_upward
1
arrow_downward

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

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

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

person fabiofili2pi    schedule 31.10.2010

arrow_upward
0
arrow_downward

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

person Jerry Coffin    schedule 31.10.2010

arrow_upward
0
arrow_downward

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

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

person Mike Dunlavey    schedule 03.11.2010