Имеют ли Nlog (logN), NlogN, Nlog (N ^ 2) эквивалентное время работы?

Question

Я думаю, что NlogN и Nlog (N ^ 2) эквивалентны, а Nlog (logN) имеет лучшую RT, чем NlogN и Nlog (N ^ 2).Кто-нибудь может подтвердить?

Answer 1

N*log(N^2) = 2N*log(N)

2N*log(N) эквивалентно N*log(N) (когда дело доходит до большой записи O, константа пропускается). NLog(logN) растет медленнее (имеет лучшую производительность при увеличении N).

Answer 2

Нет. Система обозначений Big O не имеет ничего общего с фактическим временем выполнения. O (n) может работать меньше, чем O (1) для данного значения n в зависимости от фактической реализации.

Big O запись о сравнении алгоритмов scale . То есть, когда n увеличивается, насколько они изменяются относительно друг друга.

Итак, пример:

function add100(x) {
    for (i = 0; i < 100; i++) {
        x++;
    }
    return x;
}

function twice(x) {
    tmp = x;
    for (i = 0; i < tmp; i++) {
        x++;
    }
    return x;
}

Я знаю, что эти функции могут быть уменьшены до x+100 и 2 * x соответственно, но в демонстрационных целях они просты и показывают, чего мы хотим. (и некоторые компиляторы могут на самом деле оптимизировать их, поэтому в зависимости от вашей среды разницы может не быть).

Теперь add100(x) имеет алгоритмическую сложность O(1). И double(x) имеет сложность O(n). Однако для значений x <100 <code>twice(x) будет быстрее, чем add100(x). Для произвольного ввода это не будет. Он также не будет масштабироваться, но он будет быстрее для некоторого диапазона ввода. Теперь это тривиальная реализация, и не все алгоритмы будут иметь более быстрый диапазон ввода, но он демонстрирует, что запись O() не влияет на фактическое время выполнения ...

Однако в данном конкретном случае это просто логарифм математика . Так Log(m^n) == n * Log(m), следовательно n log(n) == log(n^n). Итак, n log(n) != n log(n^2) ... Однако, поскольку константы отбрасываются в больших обозначениях O, n log (n^2) преобразуется в 2n log (n), что преобразуется в n log (n) ... Итак, n log(n) == n log(n^2) для обозначений Big O ...

Answer 3

Да, вы правы, если сравниваете в больших цифрах.Используя свойства логарифмов, log n ^ 2 == 2 * log n, поэтому они эквивалентны в больших O. Функция log log n растет строго медленнее, чем log n.

Answer 4

Поскольку log (n ^ 2) = 2log (n), n * log (n ^ 2) = 2n * log (n), что эквивалентно n * log (n).

Аlog (log (n))

Нужно просто доверять основным свойствам функции логарифма.