Сравнение временной сложности двух алгоритмов (неравенство)

Вопрос предполагает использование двух алгоритмов Т А ( н ) "=" 0,0001 н 2 , и Т Б ( н ) "=" 50 н , микросекунд соответственно, для размера задачи н . Вопрос заключается в том, при каком размере входных данных алгоритм А стать лучше, чем Б . Как мне это найти?

Я нашел аналогичный вопрос с решением, которое я не совсем понимаю. Время работы алгоритмов из аналогичного вопроса составляет Т А "=" 0,1 н 2 бревно 2 ⁡ н и Т Б "=" 2,5 н 2

Решается следующим образом:

2,5 н 2 < 0,1 н 2 бревно 2 ⁡ н
2,5 < 0,1 бревно 2 ⁡ н
25 < бревно 2 ⁡ н
2 25 < н

Следовательно, алгоритм Б лучше когда н больше, чем 2 25

Я понимаю концепцию необходимости использовать неравенство, чтобы доказать, что 0,0001 н 2 < 50 н , однако мне трудно понять, что делается в решении для примера и как применить его к вопросу...

Я думаю, что Ваш вопрос немного некорректен. Это из-за н 3 / 2 не может быть ограничено постоянной величиной, когда н → ∞ или по-другому, когда н достаточно велико, оно не может быть ограничено какой-либо константой.
@Kumar Я полагаю, что это возможно, хотя я чувствую, что более вероятно, что я сформулировал это иначе, чем то, что у меня есть, поэтому я повторю это дословно и, надеюсь, это может помочь прояснить ситуацию. «Алгоритмы A и B тратят ровно TA(n) = 0,0001n^2 и TB(n) = 50√𝑛 микросекунд соответственно на задачу размера n. Определите размер задачи n0, для которого «лучший» алгоритм начинает превзойти другой, предполагая, что n0 > 0».
Последнее утверждение вашего комментария должно быть вашим фактическим вопросом, а не комментарием. и все, что я сказал, дается как ответ @DavideFiocco.

Ответы (1)

Предположим, что два алгоритма решают одну и ту же задачу. В этом случае вы можете сказать, что алгоритм A лучше, чем B, если Т А < Т Б , потому что первый работает за более короткое время.

Для каких (положительных) значений n это Т А < Т Б неравенство сохраняется? Подставляя выражения Т А и Т Б Вы получаете

0,0001 н 2 < 50 н .

Вы можете узнать, как можно решить неравенство такого рода с помощью ручки и бумаги, например, здесь , или решить его графически и алгебраически, используя механизм для символьной математики, такой как Wolfram Alpha. Если вы сделаете это, вы увидите, что Т А меньше, чем Т Б только если n меньше некоторого порогового значения. За этим порогом алгоритм Б "становится лучше, чем А ", потому что функция квадратного корня (например, Т Б ( н ) ) растет медленнее, чем квадратичный (как Т А ( н ) ) по мере увеличения n.

@Varehen Рассмотрите возможность удаления того же вопроса, опубликованного на StackOverflow stackoverflow.com/questions/58019830/… :)
Сравнение временной сложности двух алгоритмов (неравенство)
СпросиСетьПолитика конфиденциальности1y, 0v