Застрявший в нотации O
Я сравниваю два алгоритма, Prim и Kruskal.
Я понимаю фундаментальное понятие временной сложности и когда два работают лучше всего (редкие/плотные графики)
Я нашел это в Интернете, но я изо всех сил пытаюсь преобразовать его в английский язык.
dense graph: Prim = O(N2)
Kruskal = O(N2*log(N))
sparse graph: Prim = O(N2)
Kruskal = O(N log(N))
Это - что-то вроде съемки общим планом, но кто-либо мог объяснить, что продолжается здесь?
6 ответов
Prim - это O (N ^ 2), где N - количество вершин.
Kruskal - это O (E log E), где E - количество ребер. «E log E» получается из хорошего алгоритма сортировки ребер. Затем вы можете обработать его за линейное время E.
В плотном графе E ~ N ^ 2. Итак, Крускал будет O (N ^ 2 log N ^ 2), что просто O (N ^ 2 log N).
Краскал чувствителен к количеству ребер (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)) .
Хорошо, поехали. 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 (намного меньше, чем и его можно игнорировать), должны позволить вам понять эти упрощения.
Теперь, что касается исходных выражений и того, откуда они были получены, вы: Мне нужно проверить страницу, с которой вы их получили. Но я'
Идея состоит в том, что в плотном графе количество ребер равно O (N ^ 2), а в разреженных графах количество ребер равно O (N). Итак, они берут O (E \ lg E) и расширяют его с помощью этого приближения к E, чтобы напрямую сравнить его со временем работы O (N ^ 2) Прима.
По сути, это показывает, что у Краскала есть лучше для разреженных графов, а Прима лучше для плотных.
Два алгоритма имеют большой O, определенный для разных входов (узлов и ребер). Таким образом, они конвертируют одно в другое, чтобы сравнить их.
N - количество узлов в графе, E - количество ребер.
для плотного графа имеется O (N ^ 2) ребер
для разреженного графа имеется O (N) ребер.
константы, конечно, нерелевантны для big-O, поэтому c выпадает
Первое: n - количество вершин.
Prim - это O (n ^ 2), поэтому часть достаточно проста.
Kruskal - это 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).