Что является более эффективным n^2 или n*lgn*lgn?

Question

Проблема, которая может быть решена с помощью нерекурсивного алгоритма в n^2 раз. Эту же проблему можно решить с помощью рекурсивного алгоритма в n lg(n) операции, чтобы разделить вход на две равные части и lg(n) операции, чтобы объединить два решения вместе. Какой алгоритм вы считаете более эффективным?

РЕДАКТИРОВАТЬ: Базовый случай: T(n) = 1, если n = 1.

Это означает, что nlgn lgn будет более эффективным, чем n^2, Правильно?

Answer 1

Возникает вопрос, сколько дополнительной работы должен выполнять ваш рекурсивный алгоритм по сравнению с "простым" O(n^2) версия. Например, может быть хорошей идеей проверить, скажем, n<32 в вашей рекурсивной реализации и использовании O(n^2) суб-алгоритм в этом случае. Но достаточно большой n, O(n*log(n)*log(n)) в конечном итоге будет быстрее, чем O(n^2),

Таблица для демонстрации разницы в росте (log является ли база 2):
n n^2 n*log(n) n*[log(n)]^2 1000*n*[log(n)]^2 32 1024 160 800 800 000 1024 ~10^6 ~10^4 ~10^5 ~10^8 10^4 ~10^8 ~10^5 ~2*10^6 ~2*10^9 10^5 ~10^10 ~2*10^6 ~3*10^7 ~3*10^10 10^6 ~10^12 ~2*10^7 ~4*10^8 ~4*10^11
Так что, в принципе, даже если у вас в 1000 раз больше операций для каждого "шага" вашего рекурсивного алгоритма, все равно получается быстрее, когда ваш n превышает миллион.