Застрял с обозначением O

Question

Я сравниваю два алгоритма, Прима и Крускала.

Я понимаю основную концепцию сложности времени и когда две из них работают лучше (разреженные / плотные графики)

Я нашел это в Интернете, но я изо всех сил пытаюсь перевести его на английский.

dense graph:  Prim = O(N2)
              Kruskal = O(N2*log(N))

sparse graph: Prim = O(N2)
              Kruskal = O(N log(N))

Это довольно далеко, но кто-нибудь может объяснить, что здесь происходит?

Answer 1

Prim - O (N ^ 2), где N - количество вершин.

Крускал - это O (E log E), где E - количество ребер. «E log E» исходит из хорошего алгоритма сортировки ребер. Затем вы можете обработать его в линейном E времени.

В плотном графе E ~ N ^ 2. Таким образом, Крускал будет O (N ^ 2 log N ^ 2), что просто O (N ^ 2 log N).

Answer 2

ОК, здесь идет. O (N2) (2 = квадрат) означает, что скорость алгоритма для большого N изменяется как квадрат N, поэтому удвоение размера графика приведет к четырехкратному увеличению времени вычисления.

Строки Крускала просто упрощены и предполагают, что E = c * N2. c здесь, вероятно, есть константа, которую мы можем считать значительно меньшей, чем N, так как N становится большим. Вам необходимо знать следующие законы логарифмов: log(ab) = log a + log b и log(a^n) = n * log a. Эти два в сочетании с тем фактом, что log c << log N (намного меньше, и его можно игнорировать), должны помочь вам понять упрощения. </p>

Теперь, что касается исходных выражений и того, откуда они были получены, вам нужно проверить страницу, с которой вы их получили. Но я предполагаю, что если вы посмотрите на Прима и Крускала, то вы сможете понять происхождение, или, по крайней мере, если вы не сможете, если я объясню вам это, на самом деле не поможет вам в долгосрочной перспективе ...

Answer 3

Крускал чувствителен к числу ребер (E) в графе, а не к числу узлов. Однако на Prim влияет только количество узлов (N), равное O(N^2).

Это означает, что в плотных графах, где число ребер приближается к N ^ 2 (все соединенные узлы), коэффициент сложности O(E*log(E)) примерно равен O(N^2*log(N)).

C является константой для учета «почти» и не имеет значения в обозначениях O. Кроме того, log (N ^ 2) имеет тот же порядок величины, что и log (N), поскольку логарифм перевешивает степень 2 с существенным запасом (log(N^2) => 2*log(N), что в обозначениях O равно O(log(N))).

В разреженном графе E ближе к N, что дает вам O(N*log(N)).

Answer 4

Смысл в том, что в плотном графе число ребер равно O (N ^ 2), тогда как в разреженных графах число ребер равно O (N). Поэтому они берут O (E \ lg E) и расширяют его с помощью этого приближения E, чтобы сравнить его непосредственно со временем работы O Prim's (N ^ 2).

По сути, это показывает, что Крускала лучше для разреженных графов, а Прима лучше для плотных графов.

Answer 5

Для двух алгоритмов определено big-O для разных входов (узлов и ребер). Поэтому они конвертируют одно в другое, чтобы сравнить их.

N - количество узлов в графе E - количество ребер.

для плотного графа есть O (N ^ 2) ребер

для разреженного графа есть O (N) ребер.

константы, конечно, не важны для big-O, следовательно, c выпадает

Answer 6

Первое: n - количество вершин.

Prim - это O (n ^ 2), эта часть достаточно проста.

Крускал - это O (Elog (E)), где E - количество ребер. в плотном графе N выбирают 2 ребра, что примерно равно n ^ 2 (на самом деле это n (n-1) / 2, но кто считает?), значит, это примерно n ^ 2 log (n ^ 2) ), что составляет 2n ^ 2 log n, что составляет O (n ^ 2logn), что больше, чем O (n ^ 2)

В разреженном графе всего n ребер, поэтому у нас есть n log n, которое меньше O (n ^ 2).