Что быстрее растет факториал или степень

Вопрос по Главе 7. Задача про скорость роста функций

Расположите следующие 4 функции в порядке увеличения скорости роста (каждая функция есть O(следующая)), не исключено, что некоторые функции имеют одинаковую скорость
1) f1(n) = n!;
2) f2(n) = n2;
3) f3(n) = ln n ;
4) f4(n) = n(ln n).

А поясните, пожалуйста, почему Вы так считаете? Спасибо

1. Любой полилогарифм растет быстрее любого полинома. Значит, ln n=O(n). Следовательно, ln n=O(n (ln n)), т.к. n (ln n) растёт ещё быстрее, чем n.

2. Из ln n=O(n) также следует, что n(ln n)=O(n^2).

3. Факториал по скорости роста обгоняет даже показательную функцию, а любая показательная функция растёт быстрее полинома. Значит, n^2=O(n!). Можно ещё следующим образом показать, что факториал «больше» полинома. Чем выше степень полинома, тем он быстрее растёт. Например, n^2=O(n^3), n^3=O(n^5) и т.д. Представим факториал в виде произведения: n!=n*(n-1)*(n-2)*. *1. Если раскрыть первые 3 скобки, мы уже получим функцию, «не меньшую» чем n^3. Следовательно, т.к. n^2=O(n^3), то n^2=O(n!).

Ольга, но ведь n * (ln n) растёт в n раз быстрее, чем ln n.

Кроме того, где сравнение функций ln n и n * (ln n) с функцией n!?

Т.к. n^2=O(n!) и n*ln n=O(n^2), то n*ln n=O(n!).

Т.к. n*ln n=O(n!) и ln n=O(n*ln n), то ln n=O(n!).

Отношение «расти быстрее» транзитивно, поэтому сравнивать функции, которые «меньше» n^2, с факториалом особого смысла нет.

По поводу первого замечания: n * (ln n) действительно растет быстрее, чем ln n. Только я не поняла, к чему данное замечание относилось. Поясните, пожалуйста.

Значит, в Вашем первом ответе опечатка,

А по условиям задачи мы умеем следующее:

Следовательно, в Вашем ответе функция ln n растёт быстрее, чем n(ln n).

А про факториал, поправьте пожалуйста, если не прав, я читал, что это самая быстро растущая функция.

В моём ответе всё верно. В задании просят расположить функции в порядке увеличения скорости роста, т.е. ln n, n*ln n, n^2, n!, или f3, f4, f2, f1.

Поправка: в данном случае речь идёт о множестве не действительных чисел, а натуральных.

Другое дело, что скорость роста n! не слишком хороша для сравнения, и не очень понятно, где ее можно использовать. Удобнее пользоваться показательной функцией (экспонентой).

Извините, для какого сравнения не слишком хороша скорость роста факториала?

Тут я ошибся, переклинило и я решал обратную задачу, вот и всё. выше про это уже извинялся.

EugenO, не согласен, мы же смотрим не значения в точках, а скорость роста функции.

Или же, поясните подробнее, в чём именно на Ваш взгляд выражено это не удобство в сравнении.

Для меня удобство экспоненты в том, что она очень хороша для анализа. Она легко представима в виде a^x, элементарно дифференцируема (скорость роста) и интегрируема, причем многократно, связана со вторым замечательным пределом, кроме того, интуитивно (для меня) понятна, я ее график много раз рисовал в детстве и с удовольствием ассоциирую с всевозможными процессами, происходящими в реальной жизни, поэтому вижу естественным применение в асимптотике. В то же время не смогу указать ни одного естественного инерционного процесса, который изменялся бы «со скоростью выше экспоненциальной». Кстати, известна Stirling’s approximation для оценки факториала, а оценки экспоненты через факториал что-то не припомню (наверное, в ней смысла нет).

Хотелось бы узнать, зачем при анализе сложности алгоритмов Вы дифференцируете, интегрируете (причем многократно) экспоненту, как используете второй замечательный предел и формулу Стирлинга. Я не отрицаю, что, возможно, в теории сложности вычислений без этого нельзя обойтись. К сожалению, в данной области у меня очень скромный опыт((. А Вы, наверное, в этом вопросе отлично разбираетесь (может, даже на профессиональном уровне!). Поэтому очень интересно посмотреть, как применяет математический, комплексный и функциональный анализы в асимптотике настоящий специалист. Приведите, пожалуйста, пример.

Источник

Является ли факториал самой быстрорастущей формулой?

Дан файл, содержащий строки. Если третья строка не является самой длинной или самой короткой, то скопировать в новый
Я сделал половину, но здесь почему то max и min он выводит нули, следовательно он не может считать.

Является ли формулой следующее выражение?
Добрые люди помогите решить пару задачек: 1. Исходя из определения логической.

Является ли данное выражение формулой
Помогите, пожалуйста, установить, является ли данное выражение формулой, а если да, то определить.

Проверить, что выражение является формулой
Ребят подскажите пожалуйста. ∃x∀yA(x,y)&B(x,y) ; от чего оттолкнутся? А&B является.

Решение

Igor, строго обоснования это не даст,но увидеть закономерность можно.

Добавлено через 39 секунд
Зотов_из_ОСА, чем вам не подходит вариант,который я предложил в первом сообщении?

Решение

контекст есть, но я его дословно не помню. Своими словами: самая быстрорастущая функция среди функций имеющих широкое применение.
Гамма функция, двойная экспонента и им подобные применяются при необходимости.
Например зачем обычному студенту вообще знать о существовании таких чисел
, которые даже суперкомпьютер обработать не в состоянии.
Если кто-то считает что я не прав, скажите пожалуйста в каком Универе проходят такие вещи. В ЮФУ до такой степени не заморачиваютя.
GpHUO7uk, вы о такой знаете или вычитали специально для комментария.
Товарищ модератор Catstail ваш пост заставил задуматься и создать новую тему.

Добавлено через 3 часа 17 минут
я подумал и решил ее не создавать. вопрос был относительно факториала и и то в рамках функций учебной программы. Дальнейшее придумывание «самых быстрорастущих функций» считаю неуместным.

Установить, является ли данное выражение формулой
Нужна ваша помощь. Необходимо установить, является ли данное выражение формулой Если да, то.

Является ли данная строка символов пропозициональной формулой?
Задание №1. Написать программу для реализации следующего алгоритма определения является ли данная.

Доказать, что данное выражение является формулой
Пользуясь определением формулы исчисления высказываний проверить является ли данное выражение.

Определить, является ли данная строка символов пропозициональной формулой
РЕБЯТ ПОМОГИТЕ МНЕ ПОЖАЛУЙСТА КТО МОЖЕТ НАПИСАТЬ ПРОГРАММУ.ОЧЕНЬ СРОЧНО НАДО.Я ПРОБОВАЛА НАПИСАТЬ.

Источник

Какая функция растет быстрее, экспоненциальная или факториальная?

Какая функция растет быстрее, экспоненциальная (например, 2^n, n^n, e^n и т.д.) или факториальная (n!)? Ps: Я только что где-то прочитал, что n! растет быстрее, чем 2^n.

n! в конечном итоге растет быстрее, чем экспонента с постоянным основанием (2^n и e^n), но n^n растет быстрее, чем n!, поскольку основание растет по мере увеличения n.

Каждый член после первого в n^n больше, поэтому n^n будет расти быстрее.

Что касается других случаев, читайте дальше:

Мы используем формулу Стирлинга и основные манипуляции с логарифмами:

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

Позвольте’ы использовать простой и скучный функции отдела, чтобы объяснить свойство деления.

Как увеличивает, оценка этого выражения также увеличивается. А уменьшается б, в оценке этого выражения также уменьшается.

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

В нашем случае, мы хотим знать, является ли экспоненциальных функций будет расти быстрее, чем факториалы, или наоборот. У нас есть два случая, постоянной переменной экспонента и факториал переменной, а переменной степени против переменной факториал.

Графики этих инструментов с desmos (никаких связей, он’s просто хороший инструмент), показывает нам это:

График постоянная в переменной степени, против переменной факториал

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

График переменной к переменной степенью, против переменной факториал

Хотя он первоначально, кажется, медленнее, она начинает стремительно расти после ссылки, поэтому можно сделать вывод, что экспоненциальный должна быть возрастающей быстрее, чем факториал.

Источник

Пример 8

Исследовать ряд на сходимость

Используем признак Лейбница:
1) Ряд является знакочередующимся.

2)

Дело в том, что не существует стандартных обыденных приемов для решения подобных пределов. Куда стремится такой предел? К нулю, к бесконечности? Здесь важно, ЧТО на бесконечности растёт быстрее – числитель или знаменатель. Если числитель при растёт быстрее факториала, то . Если, на бесконечности факториал растёт быстрее числителя, то он, наоборот – «утянет» предел на ноль: . А может быть этот предел равен какому-нибудь отличному от нуля числу?

Попробуем записать несколько первых членов ряда:

Создается стойкое впечатление, что , но где гарантия, что при очень больших «эн» факториал не «обгонит» числитель и не утащит предел на ноль?

Обратимся к теории математического анализа, там давно всё доказано.

– Факториал растёт быстрее, чем любая показательная последовательность, иными словами: или . Да хоть миллион в степени «эн», это не меняет дела. Математики говорят, что факториал более высокого порядка роста, чем любая показательная последовательность.

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

– Факториал растёт быстрее, чем произведение любого количества показательных и степенных последовательностей (наш случай).

– Любая показательная последовательность растёт быстрее, чем любая степенная последовательность, например: , . Показательная последовательность более высокого порядка роста, чем любая степенная последовательность. Аналогично факториалу, показательная последовательность «перетягивает» произведение любого количества любых степенных последовательностей или многочленов:

Таким образом, второй пункт исследования (вы еще об этом помните? =)) можно записать так:
2) , так как более высокого порядка роста, чем .
Члены ряда убывают по модулю.

Вывод: ряд сходится.

Исследуем ряд на абсолютную сходимость:

А здесь уже работает старый добрый признак Даламбера:

Используем признак Даламбера:

Таким образом, ряд сходится.

Исследуемый ряд сходится абсолютно.

Разобранный пример можно решить другим способом.

Теорема: Если ряд сходится абсолютно, то он сходится и условно.

Наверное, вы уже заметили, что обратное неверно: если ряд сходится условно, то это еще не значит, что он сходится абсолютно.

Пример 8 «на бис» вторым способом.

Исследовать ряд на сходимость

Решение: Исследуем ряд на абсолютную сходимость:

Используем признак Даламбера:
…
только что печатал
…
Таким образом, ряд сходится.
По соответствующей теореме из абсолютной сходимости ряда следует и условная сходимость ряда.

Вывод: Исследуемый ряд сходится абсолютно.

Правда, при втором способе решения есть риск, что преподаватель оценит хитро… смекалку студента и забракует задание. А может и не забракует.

И напоследок пара примеров для самостоятельного решения. Один из той же оперы (перечитайте справку), но попроще. Другой для гурманов – на закрепление интегрального признака сходимости.

Источник

Алгоритмы быстрого вычисления факториала

Понятие факториала известно всем. Это функция, вычисляющая произведение последовательных натуральных чисел от 1 до N включительно: N! = 1 * 2 * 3 *… * N. Факториал — быстрорастущая функция, уже для небольших значений N значение N! имеет много значащих цифр.

Попробуем реализовать эту функцию на языке программирования. Очевидно, нам понадобиться язык, поддерживающий длинную арифметику. Я воспользуюсь C#, но с таким же успехом можно взять Java или Python.

Итак, простейшая реализация (назовем ее наивной) получается прямо из определения факториала:

На моей машине эта реализация работает примерно 1,6 секунд для N=50 000.

Далее рассмотрим алгоритмы, которые работают намного быстрее наивной реализации.

Алгоритм вычисления деревом

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

Пусть нам нужно найти произведение последовательных чисел от L до R, обозначим его как P(L, R). Разделим интервал от L до R пополам и посчитаем P(L, R) как P(L, M) * P(M + 1, R), где M находится посередине между L и R, M = (L + R) / 2. Заметим, что множители будут примерно одинаковой длины. Аналогично разобьем P(L, M) и P(M + 1, R). Будем производить эту операцию, пока в каждом интервале останется не более двух множителей. Очевидно, что P(L, R) = L, если L и R равны, и P(L, R) = L * R, если L и R отличаются на единицу. Чтобы найти N! нужно посчитать P(2, N).

Посмотрим, как будет работать наш алгоритм для N=10, найдем P(2, 10):

P(2, 10)
P(2, 6) * P(7, 10)
( P(2, 4) * P(5, 6) ) * ( P(7, 8) * P(9, 10) )
( (P(2, 3) * P(4) ) * P(5, 6) ) * ( P(7, 8) * P(9, 10) )
( ( (2 * 3) * (4) ) * (5 * 6) ) * ( (7 * 8) * (9 * 10) )
( ( 6 * 4 ) * 30 ) * ( 56 * 90 )
( 24 * 30 ) * ( 5 040 )
720 * 5 040
3 628 800

Получается своеобразное дерево, где множители находятся в узлах, а результат получается в корне

Реализуем описанный алгоритм:

Для N=50 000 факториал вычисляется за 0,9 секунд, что почти вдвое быстрее, чем в наивной реализации.

Алгоритм вычисления факторизацией

Для наглядности посчитаем, сколько раз двойка содержится в 10! Двойку дает каждый второй множитель (2, 4, 6, 8 и 10), всего таких множителей 10 / 2 = 5. Каждый четвертый дает четверку (2 2 ), всего таких множителей 10 / 4 = 2 (4 и 8). Каждый восьмой дает восьмерку (2 3 ), такой множитель всего один 10 / 8 = 1 (8). Шестнадцать (2 4 ) и более уже не дает ни один множитель, значит, подсчет можно завершать. Суммируя, получим, что показатель степени при двойке в разложении 10! на простые множители будет равен 10 / 2 + 10 / 4 + 10 / 8 = 5 + 2 + 1 = 8.

Если действовать таким же образом, можно найти показатели при 3, 5 и 7 в разложении 10!, после чего остается только вычислить значение произведения:

10! = 2 8 * 3 4 * 5 2 * 7 1 = 3 628 800

Осталось найти простые числа от 2 до N, для этого можно использовать решето Эратосфена:

Эта реализация также тратит примерно 0,9 секунд на вычисление 50 000!

Как справедливо отметил pomme скорость вычисления факториала на 98% зависит от скорости умножения. Попробуем протестировать наши алгоритмы, реализовав их на C++ с использованием библиотеки GMP. Результаты тестирования приведены ниже, по ним получается что алгоритм умножения в C# имеет довольно странную асимптотику, поэтому оптимизация дает относительно небольшой выигрыш в C# и огромный в C++ с GMP. Однако этому вопросу вероятно стоит посвятить отдельную статью.

Все алгоритмы тестировались для N равном 1 000, 2 000, 5 000, 10 000, 20 000, 50 000 и 100 000 десятью итерациями. В таблице указано среднее значение времени работы в миллисекундах.

График с линейной шкалой

График с логарифмической шкалой

Идеи и алгоритмы из комментариев

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

Исходные коды реализованных алгоритмов приведены под спойлерами

Источник