Дополню. Простыми словами, это оценка времени работы алгоритма в зависимости от размера входных данных. Сложности n^n и n! — "плохие", потому что, очевидно, при росте n растут очень-очень быстро. Просто n — это довольно "хорошая" сложность, она растёт медленно. И, по поводу моего же комментария: n^n и n! — это сравнимые величины, растут буквально одинаково быстро и в оценках сложности считаются одним и тем же значением. А вот n^n и n — это небо и Земля. Там невооружённым взглядом видно, где что. А писать факториалы в конце предложения как-то странно, вот.
Нет, блядь, в этом и смысл! Только прошли понятие, надо срочно "искрометно" и "оригинально" пошутить! По стопам классики, которая "а и б сидели на трубе", мать их.
n! < n^n при n>1 Просто для больших n это не очень важно, ибо в любом случае дохуя. Смысл шутки в том, что кандидат вообще не врубается, о чём интервьюеры спорят.
Так в контексте O(n) работает арифметика бесконечно больших. А там нам плевать на малые значения. По сути, рассматривается только порядок скорости роста. n! = n*(n-1)*(n-2)*... всего n множителей. Если раскроем скобочки, максимальная степень будет n^n. И ещё куча каких-то степеней n с показателем меньше n и каким-то коэффициентом. Вспоминаем, что это вообще биг О: O(n!) = O(n^n+a1*n^(n-1)+a2*n^(n-2)+...) = [n^n >> а1*n^(n-1) при больших n] = O(n^n)
вы не правы. во-первых при n стремящемся к бесконечности n!=o(n^n), что эквивалентно тому что n!/n^n стремится к нулю, говоря нестрого n^n "намного больше". во-вторых знак равенства в выражениях с O-нотацией означает не равенство, а принадлежность классу и не корректно ставить знак равенства между двумя классами, как это сделали вы. хотя не лишенной смысла записью было бы использование знака вложенности O(n!)⊂O(n^n) (обратное будет ложно) в-третьих в большинстве случаев под O(n) подразумевают θ(n), просто всем лень писать θ. и тогда даже утверждение θ(n!)⊂θ(n^n) будет ложно.
к сожалению, пикабу не дает вставить формулы текстом, прикреплю скрин. если говорить не строго, то a=O(b) значит что a растет также как b или медленнее, а a=θ(b) значит что a и b растут с сопоставимой скоростью.
Ващет, "при n стремящемся к бесконечности" вопрос разницы между n! , n^n, n^m и собственно n, теряет практический смысл.
Да, я знаю, что в некоторых разделах математики оперируют такими идеями, типа "0.8 бесконечности — меньше, чем бесконечность, умноженная на два", но на практике ∞+4, 6∞ и ∞/13 можно смело округлять до ∞, в решении практических задач это ни на что не повлияет.
вы на столько сильно неправы, что мне вместо комментария впору методичку прикладывать. постараюсь по самым основным тезисам: 1. сравнение при стремлении к пределу -- очень важная часть математики, это основы мат анализа, который проходится даже в старших классах некоторых школ и это используется во *всей* математике, в которой вообще затрагивается понятие пределов. 2. сравнивать бесконечности в приведенном смысле некорректно. корректно сравнивать выражения при стремлении переменных к бесконечности. 3. множители как раз важны, поскольку помогают вычислить, в простейшем случае, отношение двух стремящихся к бесконечности величин. 4. прибавление констант (а в общем случае просто незначащих частей) и правда часто можно игнорировать, а чтобы это делать правильно, как раз и придумана О-нотация, о которой речь.
Вы правы в общем, но не в частности. Вы рассматриваете ситуацию как раз с точки зрения тех разделов математики, у которых с понятием бесконечности "особые отношения". В работе инженера-практика, бесконечность — это просто бесконечность, то есть величина невообразимо огромная, которую точно измерить нельзя, да и незачем, ибо знание точного её размера никакого значимого эффекта на вычисления не даст.
Да, множители важны. Только в реальных практических приложениях вам никогда не понадобится вычислять их такими сложными путями, они, множители, либо очевидны, либо известны из экспериментальных данных.
нет особых отношений с бесконечностью. вся математика относится к бесконечностям одинаково.
В работе инженера-практика, бесконечность — это просто бесконечность, то есть величина невообразимо огромная
в работе инженера практика бесконечности не бывает вообще, поскольку это понятие абстрактное. а понятие пределов инженеру практику очень нужно для расчетов, потому что оно лежит в основе математического анализа, на котором основана вся математика, с помощью которой выводились физические законы, были выведены все формулы расчетов. то, как ваш калькулятор высчитывает синус -- и то связано с пределами, поскольку использует разложение в степенной ряд. если, конечно, этот инженер использует что-то кроме таблицы диаметров красных шариков.
IT-юмор
7.5K поста53.3K подписчиков
Правила сообщества
Не публикуем посты:
1) с большим количеством мата
2) с просьбами о помощи
3) не относящиеся к IT-юмору