Что является более эффективным 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 превышает миллион.