Сколько ребер в плотном графе

Question

Я читал, что в плотном графе число ребер равно (n^2), и я не знаю, как. Если у меня есть граф и каждый узел соединен с другими всеми узлами, то число ребер будет равно ( (n-1) + (n-2) + (n-3) + ..... + 1)Итак, как ребра в плотном графе (n^2)

Answer 1

Это зависит от того, направлен ли ваш график.В неориентированном плотном графе число ребер равно (n · (n - 1) / 2) (что равно вашей серии).На ориентированном графе это число вдвое больше, поэтому просто (n · (n - 1)) .

Это не совсем (n²) , ноочень близко к этому.Вы можете сказать, что n² является верхней границей, поэтому, возможно, более уместно сказать O (n²) , если это имеет смысл в контексте.

Answer 2

Это Big O нотация , возможно, они имеют в виду сложность, когда вы выполняете обход графика.В большом обозначении O: O (n² / 2) = O (n²)