Как расположить функции в порядке увеличения скорости роста?

Question

[valent_in_habrahabr]

Answer 1

[throughtheether]

Предполагаю, порядок таков:
3 1 4 5 6 7 2
В частности, f1(n)=n^0.3 < f4(n)=n^0.5

Comments

[throughtheether]

Спасибо за ответ

Рад был помочь.

Это сложность алгоритмов

Скорее наоборот, в оценке сложности алгоритмов используются данные о росте функций с ростом аргументов. Я думаю, вам надо просто этот пример подробно разобрать. Разделите функции на категории: полиномиальные (n^const), логарифмические (log n), степенные (const^n), смешанные (n log n). Разберитесь, как сравнивать рост функций внутри категории и функций из разных категорий. Например, n^const растет медленнее, чем 2^n, независимо от константы. Иногда бывает полезно взять логарифм обеих функций и сравнить (log(n^const)=const*log n; log(2^n)=n log2, так как log n < n, то первая функци растет медленнее). Может быть полезно изучить графики функций не только в линейном, но и в логарифмическом масштабе (по обеим осям откладываем не само значение, а его логарифм).
Из книжек могу порекомендовать главу 3 книги Data Structures and
Algorithms in Python (Goodrich, Tamassia, Goldwasser), особенно упражнения к ней.

Если что-то осталось неясным - готов пояснить.

[throughtheether]

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

Как минимум, пригодятся начала комбинаторики (есть N предметов, сколько из них можно составить пар, групп по k, с повторами, без повторов, упорядоченных, неупорядоченных), теории вероятностей (пример: на отрезке произвольным образом выбирается точка; какова вероятность того, что отношение меньшего отрезка к большему составляет 1/3 или больше? - используется в рандомизированном quicksort).
Из курсов рекомендую Algorithms: Design and Analysis (Coursera, Stanford), ведет Tim Roughgarden. В нем присутствуют и лекции по теории.

[throughtheether]

Удачи в учебе!

Answer 2

[Андрей]

Предлагаю вариант
3 1 4 5 6 7 2

Answer 3

[Александр Таратин]

Вбейте функции в вольфрам, чтобы сравнить графики.

www.wolframalpha.com/input/?i=x+%3D+n%5E0.3%3B+x+%...

Answer 4

[Mrrl]

f4 - это sqrt(n) или sqrt(5)? А то в разных местах по-разному.
Если предположить, что sqrt(n), то в вашем ответе не на месте функция f1. Она растёт гораздо медленнее, чем вы думаете.

Comments

[h8nor]

Действительно, получается что скорость изменения функции f₄(n) = sqrt(5) равна нулю.
Есть аналогичное задание. Если считать верным задание на рисунке, мой вариант:
1 3 4 5 6 7 2
Смутило, что функция f₅(n) на некоторых отрезках убывает.