Почему операции в списке смежности O (| E | / | V |) $?

Question

Я готовлюсь к экзамену, который у меня скоро.Предоставленная мне диаграмма имеет следующие алгоритмические сложности, обобщенные для списка смежности для графа с N узлами и ребрами E.

• Найти ребро - O (E / N)

• Вставить ребро - O (E / N)

• Удалить ребро - O (E / N)

• Перечислите ребра для узла - O (E / N)

Я понимаю, что такое список смежности - мы храним вершины, смежные с каждой вершиной, используя массив списков.Но почему эти операции O (E / N)?Мне кажется, что если бы мы взяли график, на котором нарисовано каждое возможное ребро (например, у нас есть n (n - 1) / 2 ребер, если граф не направлен), то каждый список в массиве будет иметь N - 1записи для хранения любого другого узла

Это, на мой взгляд, было бы "наихудшим случаем", не так ли?Я не понимаю, как получается соотношение ребер к узлам.

Может кто-нибудь объяснить, пожалуйста?

Answer 1

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

Для того, что я мог понятьВы спрашиваете, почему в диаграмме указано, что операция - это O (E / N), когда хорошо известно, что наихудший случай - это O (N).Ну, здесь есть 2 проблемы:

1. Вы предполагаете, что большой O означает «ввод в худшем случае», но по определению мы не можем допустить это.
2. Диаграмма показывает только O (E / N), и, как прокомментировал @domen, текст должен быть более четким и указывать, какой вариант ввода он рассматривает.

Быстрый ответ здесьявляется то, что большой O может быть использован, чтобы «говорить» об обоих случаях.Это будет O (E / N), когда мы говорим о среднем входе , и это будет O (N), когда мы говорим о худшем входе.

Теперь давайте посмотримболее длинный ответ по каждому из перечисленных вопросов: согласно книге «Введение в алгоритмы» мы можем определить большой O как:

O (g (n)) = {f(n): существуют положительные константы c и n0, такие что 0 <= f (n) <= cg (n) для всех n> = n0}

Обратите внимание, что определение не говоритчто-нибудь о худшем случае, это просто говорит о том, что если у нас есть функция f (n) и мы можем предоставить константу c и a n0, такую, что 0 <= f (n) <= cg (n) для каждого n> = n0, тоf (n) находится в O (g (n)).Так что забудьте здесь о худшем случае, если мы можем предоставить функцию f (n), константу c и a n0, которая не нарушает вышеприведенное определение, тогда f (n) находится в O (n).
Здесь мыпросто говорить о верхней границе только для этого входного регистра, который может быть худшим входным параметром, средним входным значением или любым другим входным регистром.
Если алгоритм имеет «худший вход» = w (n) и «средний вход» =a (n) где существует c ', n'0 такое, что 0 <= w (n) <= c'g (n) для каждого n> = n'0 и существует c' ', n''0 такоечто 0 <= a (n) <= c''g (e / n) для каждого n> = n''0, то мы можем сказать, что алгоритм - это O (n) в худшем случае и O (e / n)) в среднем случае.

Если на графике не указано значение f (n), которое он рассматривает (наихудший или средний случай в качестве примера), то мы не можем ничего подтвердить, диаграмма должна быть более конкретной.
Обычное поведение здесь состоит в том, чтобы предполагать, что текст ссылается на наихудший случай ввода, и, вероятно, поэтому мы связываем Big O с наихудшим случаем, в то время как в большинстве случаев это предположениеиногда (как и в приведенной вами таблице) это неправильно.