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

Question

Вопрос предполагает, что два алгоритма тратят T_A (n) = 0,0001n ^ 2 и T_B (n) = 50√n, микросекунды соответственно, для размера задачи n.Вопрос состоит в том, при каком размере входного алгоритма алгоритм A станет лучше, чем B. Как мне это найти?

Я нашел похожий вопрос с решением, которое я до конца не понимаю.Время выполнения алгоритмов из аналогичного вопроса: T_A = 0,1n ^ 2logn (база 2) и T_B = 2,5n ^ 2

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

2.5n^2 < 0.1n^2 log2 n
2.5 < 0.1 log2 n
25 < log2 n
2^25 < n

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

Answer 1

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

Для каких значений n это делает T_A <<code>T_B неравенство держать?Подставляя выражения T_A и T_B, вы получаете

Вы можете узнать, как можно решить неравенство такого рода с помощью ручки и бумагинапример, здесь , или решить это графически и алгебраически, используя движок для символической математики, такой как Wolfram Alpha .Если вы сделаете это, вы увидите, что T_A меньше, чем T_B, только если n меньше некоторого порогового значения.За пределами этого порога B «становится лучше, чем A», поскольку функция квадратного корня (например, T_B) увеличивается медленнее, чем квадратичная (например, T_A), при увеличении n.