Большая O-нотация для алгоритма, который содержит сокращающийся список внутри цикла Loop - PullRequest
Новая
       43

Большая O-нотация для алгоритма, который содержит сокращающийся список внутри цикла Loop

0 голосов
/ 31 мая 2018

Я пытался оценить наихудший сценарий для алгоритма, который выглядит следующим образом ( оценочная сложность в комментариях - моя, в которой V - это число вершин, а E - это число ребер вgraph ): 

while(nodes.size()!=0) { // O(V) in which nodes is a LinkedList
     Vertex u = Collections.min(nodes); // O(V)
     nodes.remove(u); // O(1)
     for(Map.Entry<Vertex, Integer> adjacency : u.adj.entrySet()) { // O(E)
         // Some O(1) Statement

         if(nodes.contains(v)) { // O(V)
            // Some O(1) Statement
         }
     }
}

Мой вопрос очень прост: после каждого раунда в цикле while, nodes LinkedList будет становиться все меньше и меньше.В конце концов, операции Collections.min() и nodes.contains() будут занимать меньше времени в каждом раунде.

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

В противном случае, не могли бы вы объяснить сюжет о том, как определить правильную сложность в приведенном выше сценарии?

Ответы [ 3 ]

0 голосов
/ 31 мая 2018

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

Когда значение V изменяется, введите другую переменную v, что является значением для одной конкретной итерации.Тогда сложность каждой итерации равна v+(E*v).Общая сложность равна сумме каждой итерации: 

sum(v = 1...V) v+(E*v)
= 1+1E + 2+2E + 3+3E + ... + V+VE                 - Expand the sum
= (1 + 2 + 3 + ... + V) + (1 + 2 + 3 + ... + V)E  - Regroup terms
= (V^2 + V)/2 + (V^2 + V)E/2                      - Sum of arithmetic series
= (V^2 + V + EV^2 + EV)/2                         - Addition of fractions
= O(EV^2)                                         - EV^2 greater than all other terms
0 голосов
/ 31 мая 2018

nodes.contains имеет сложность времени в худшем случае в Θ(V), цикл for выполняется несколько раз в Θ(E) и поэтому имеет сложность времени в худшем случае в Θ(V*E), Collections.min имеет худший случайвременная сложность в Θ(V), поэтому тело цикла while имеет наихудшую временную сложность в Θ(V+V*E), но V+V*E само по себе Θ(V*E) (см. позже), поэтому тело цикла while имеет худший случайвременная сложность в Θ(V*E).Цикл while выполняется V раз.Таким образом, наихудший случай выполнения алгоритма - Θ(V^2*E).

Упрощение там - замена Θ(V+V*E) на Θ(V*E) - приемлемо, потому что мы смотрим на общий случайV>1.То есть V*E всегда будет большим числом, чем V, поэтому мы можем поглотить V в ограниченно-постоянный коэффициент.Также было бы правильно сказать, что наихудшее время произнесено в Θ(V^2+E*V^2), но никто бы не использовал его, поскольку упрощенная форма более полезна.

Кстати, для интуиции вы можете вообщеигнорируйте эффект «использования» контейнеров во время алгоритма, например, с сортировкой вставок, имеющей все меньше и меньше элементов для просмотра, или этим алгоритмом, имеющим все меньше и меньше узлов для сканирования.Эти эффекты превращаются в постоянные факторы и исчезают.Только когда вы удаляете интересное число элементов каждый раз, например, с помощью алгоритма быстрого выбора или двоичного поиска, такие вещи начинают влиять на асимптотическое время выполнения.

0 голосов
/ 31 мая 2018

Да, они выглядят правильно.И сложив их вместе, вы получите время O(V*(V+E)).(Исправление, O((1+E)*V^2) - я пропустил O(V) внутри O(E) внутреннего цикла.)

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

...