Здравствуйте,
в книге Седжвика "Фундаментальные алгоритмы на Java" есть такое упражнение:
Для каких значений N справедливо 10*N*lg(N) > 2*(N^2) ?
Что-то никак не пойму как это решать
Удалось свести к такому неравенству:
N^5 > 2^N
но не понятно что дальше?
Просветите, пожалуйста, как же его все-таки решить.
Здравствуйте, Аноним, Вы писали:
...
А>Удалось свести к такому неравенству:
А>N^5 > 2^N
А>но не понятно что дальше?
...
Можно графики построить.
f(N)=N^5 и f(N)= 2^N — возрастающие функции.
Здравствуйте, ABar, Вы писали:
AB>Здравствуйте, Аноним, Вы писали:
AB>...
А>>Удалось свести к такому неравенству:
А>>N^5 > 2^N
А>>но не понятно что дальше?
AB>...
AB>Можно графики построить.
AB>f(N)=N^5 и f(N)= 2^N — возрастающие функции.
То есть аналитически оно не решается?
P.S. Забыл сказать, lg — двоичный логарифм.
Здравствуйте, Аноним, Вы писали:
А>в книге Седжвика "Фундаментальные алгоритмы на Java" есть такое упражнение:
А>А>Для каких значений N справедливо 10*N*lg(N) > 2*(N^2) ?
Аналитически это, конечно, не решается. Но нужно понимать смысл этих выражений. Скорее всего исходный вопрос был про то, когда одна сортировка (возможно heapsort, или qsort в среднем) оказывается медленнее другой сортировки (пузырька, простых вставок, простого выбора или еще чего-то похожего квадратичного). В часности, N здесь число натуральное. Ну а учитывая, что правая часть растет быстрее левой, ответом будет множество {0, ... M}. M легко найти хоть бы и прямым подбором
Здравствуйте, Mab, Вы писали:
Mab>Аналитически это, конечно, не решается. Но нужно понимать смысл этих выражений. Скорее всего исходный вопрос был про то...
Исходный вопрос был именно таким.
Не больше и не меньше.
Я то думал, что оно как-то аналитически решается...
Ладно, спасибо Mab и ABar, все ясно.
тут чиста математичекская задача и вооще более общий случай a^b><b^a, решать можно например при помощи анализа производных ф-ций x^y и y^x — абстрагируйся, подумай (матан кажеться 2го курса или 10й класс школ с углубленным изучением математики)
думай.!.!.!
