n * log n и n / log n от времени полинома

Я понимаю, что быстрее, чем и медленнее, чем . Мне трудно понять, как на самом деле сравнить и с где .Θ ( n log n ) Θ ( n / log n ) Θ ( n log n ) Θ ( n / log n ) Θ ( n f ) 0 < f < $\Theta(n)$$\Theta(n\log n)$$\Theta(n/\log n)$$\Theta(n \log n)$$\Theta(n/\log n)$$\Theta(n^f)$$0 < f < 1$

Например, как мы решаем против илиΘ ( п 2 / 3 ) Θ ( п 1 / 3$\Theta(n/\log n)$$\Theta(n^{2/3})$$\Theta(n^{1/3})$

Я хотел бы иметь некоторые направления в таких случаях. Спасибо.

Если вы просто нарисуете пару графиков, вы будете в хорошей форме. Wolfram Alpha - отличный ресурс для таких исследований:

Сгенерировано по этой ссылке . Обратите внимание, что на графике log (x) - это натуральный логарифм, поэтому уравнение одного графика выглядит немного забавно.

2 n 2 n n k k log n n k$\log n$ является обратным к . Так же, как растет быстрее, чем любой многочлен независимо от того, насколько велика конечная , будет расти медленнее, чем любые функции многочлена независимо от того, насколько мал ненулевой положительный .$2^n$$2^n$$n^k$$k$$\log n$$n^k$$k$

n k k < 1 n / log n n / n 1 - $n / \log n$ против , поскольку совпадает с: против$n^k$$k < 1$$n / \log n$$n / n^{1-k}$

как для больших , для и больших .n n / log n > n k k < 1 $n^{1-k} > \log n$$n$$n / \log n > n^k$$k < 1$$n$

Для многих алгоритмов иногда случается, что константы разные, в результате чего те или иные быстрее или медленнее для меньших размеров данных и не так хорошо упорядочены по алгоритмической сложности.

Сказав это, если мы только рассмотрим супер-большие размеры данных, т.е. который в конечном итоге выигрывает, то O(n^f)быстрее, чем O(n/log n)для 0 < f < 1.

Большая часть алгоритмической сложности состоит в том, чтобы определить, какой алгоритм в конечном итоге быстрее, поэтому достаточно знать, что O(n^f)он быстрее, чем O(n/log n)для 0 < f < 1.

Общее правило заключается в том, что умножение (или деление) на в log nконечном итоге будет незначительным по сравнению с умножением (или делением) n^fна любое f > 0.

Чтобы показать это более наглядно, давайте рассмотрим, что происходит при увеличении n.

   n       n / log n         n^(1/2)
   2        n/ 1              ?
   4        n/ 2             n/ 2
   8        n/ 3              ?
  16        n/ 4             n/ 4
  64        n/ 6             n/ 8
 256        n/ 8             n/16
1024        n/10             n/32

Обратите внимание, что уменьшается быстрее? Это n^fколонна.

Даже если значение fбыло ближе к 1, n^fстолбец будет начинаться медленнее, но при увеличении n вдвое скорость изменения знаменателя возрастает, тогда как знаменатель n/log nстолбца изменяется с постоянной скоростью.

Давайте нарисуем частный случай на графике

Источник: Вольфрам Альфа

Я выбрал O(n^k)такой, который kдовольно близко к 1 (в 0.9). Я также выбрал константы, чтобы изначально O(n^k)медленнее. Тем не менее, обратите внимание, что в конечном итоге он "выигрывает" в конце и занимает меньше времени, чем O(n/log n).

Просто подумайте о как о . Так что для вашего примера . Тогда легко сравнить рост$n^f$$\dfrac{n}{n^{1-f}}$$n^{2/3}=n/n^{1/3}$

Помните, что растет асимптотически медленнее, чем любой , для каждого .n ε ε > $\log n$$n^\varepsilon$$\varepsilon>0$

При сравнении времени выполнения всегда полезно сравнивать их, используя большие значения n. Для меня это помогает построить интуицию о том, какая функция медленнее

В вашем случае подумайте о n = 10 ^ 10 и a = .5

O(n/logn) = O(10^10/10) = O(10^9)
O(n^1/2) = O(10^10^.5) = O(10^5)

Следовательно, O (n ^ a) быстрее, чем O (n / logn), когда 0 <a <1, я использовал только одно значение, однако вы можете использовать несколько значений для построения интуиции о функции

Пусть обозначает «f растет асимптотически медленнее, чем g», тогда вы можете использовать следующее простое правило для полилогарифмического? функции:$f \prec g$

Порядок отношений между кортежами лексикографический. Т.е. и$(2, 10) < (3, 5)$$(2, 10) > (2, 5)$

Применительно к вашему примеру:

$\mathcal{O}(n/\log n) \Rightarrow (1, -1, 0)$

$\mathcal{O}(n^{2/3}) \Rightarrow (2/3, 0, 0)$

$\mathcal{O}(n^{1/3}) \Rightarrow (1/3, 0, 0)$

Вы могли бы сказать: полномочия n доминируют над полномочиями журнала, которые доминируют над полномочиями журнала.

Источник: Конкретная математика, с. 441