Как рассчитать эффект увеличения скорости процессора, когда T (N) = O (2 ^ n)?

Question

Мне был представлен следующий сценарий: алгоритм A - это O (2 ^ n). Я могу либо выбрать процессор в 10 раз быстрее, либо выбрать алгоритм B, который равен O (n ^ 2). Очевидно, я бы выбрал алгоритм B, но мне нужно обосновать это математически, а не только рассуждениями.

Мне сказали, что алгоритм B позволяет мне решить проблему, которая в 2 ^ n / n ^ 2 раза больше. Это я понимаю Пока все хорошо.

Но далее говорится, что более быстрый процессор позволяет мне решить проблему (n + log 10) раз больше (приблизительно n + 3).

Как они получают (n + log 10) из (2 ^ n / 10)?

Answer 1

Время, необходимое для решения проблемы, - это объем работы, деленный на скорость процессора, которая может быть выражена как (2 ^ n) / скорость для первого алгоритма.Умножьте скорость на 10, и это (2 ^ n) / (10 * speed).То, что они на самом деле подразумевают под «позволяет решить проблему на более крупную», означает «позволяет решить эту большую проблему в ОДНОМ СУММЕ ВРЕМЕНИ».

Итак, (2 ^ n) / скорость = (2 ^ (n + больше)) / (скорость 10 *).Решите алгебраически для большего, и в итоге вы получите больше = лог скорости 10.