доказательство сложности верхнего предела для алгоритма prima

Question

Я хотел бы знать, как вы можете доказать верхнюю границу временной сложности алгоритма Prim. Я знаю, что временная сложность алгоритма Прима равна O (| E | log | V |), где E - ребро, а V - вершина, но что это означает по верхней границе временной сложности?

Answer 1

но что это означает по верхней границе временной сложности?

Ваш вопрос, как правило, касается верхней границы любого алгоритма. Верхняя граница ограничивает наихудший случай, как «далеко вперед» f (x) может идти.

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

Это означает, что данный алгоритм не может выполнять хуже этой сложности, учитывая его набор входных данных.

Таким образом, используя двоичную кучу и смежность для графика и для упорядочивания ребер по массе, общая временная сложность составляет O(|E| log |V|).

Следовательно, f(x) = O(|E| log |V|).

Он ограничен ниже этой функции, если выражен в примечании Big-O.