Анализ сложности времени алгоритма (три вложенных цикла)

Вот код, который я реализовал в двух словах. Два внутренних цикла должны иметь сложность O(n2) where n=vertices. Я просто не могу понять общую сложность времени по внешнему циклу. Я думаю, что это будет O(E * n2) where E is the number of edges and n is the number of vertices.Анализ сложности времени алгоритма (три вложенных цикла)

int vertices; 

for(int Edges = 0; Edges < vertices-1 ; Edge++) 
{ 
    for (int i=0; i< vertices; i++) 
     for (int j=0; j<vertices; j++) 
     { 
      // TASKS 
     } 
}

Этот код предназначен для примитивного алгоритма. Я могу опубликовать весь код, если вы хотите. Спасибо :)

источник

2014-12-06 user3490561

Ahh !!! Что так типично!

В ваших внутренних циклах у вас есть переменные с именем i & j, поэтому вы легко поняли сложность.

Просто с добавлением переменной EDGE, которая совсем не отличается от других 2, вы запутались! Проверьте количество итераций !!!

Внешняя петля будет работать с VERTICES-1 итерациями.

Следовательно, сложность = (ВЕРТИКИ-1) * (ВЕРТИКИ) * (ВЕРТИКИ) = (ВЕРТИКИ^3) - (ВЕРТИКИ^2). Сложность

Программы будет O (Вершины^3) OR O (N^3), где п = вершины ...

источник

2014-12-06 11:58:11

не должен он O (E * n2), где E - число ребер, n - число вершин? Извините, сэр. Я новичок. – user3490561

@ user3490561- nO. Общее количество итераций будет определять сложность. Вы можете сказать, что он работает O (n^2 * E), но сам E сам повторяется от 0 до итераций VERTICES-1. И, пожалуйста, повторите мой ответ. Кроме того, я студент, как вы, а не сэр. Пожалуйста, будьте спокойны со мной. –

Вы имеете в виду, что константы выбрасываются, таким образом (ВЕРТИКИ-1) становится (ВЕРТИКАМИ). Соответственно, O (ВЕРТИКИ * ВЕРТИКИ * ВЕРТИКИ) = O (Вершины^3) – user3490561

Sigma нотация делает вещи ясно:

enter image description here

источник

2014-12-08 16:22:18

Спасибо, сэр ... очень ценим. – user3490561

Добро пожаловать. Однако, если вы не очень хорошо знакомы с суммированием, вы можете использовать этот инструмент: http://www.combineditorix.com/ –

Анализ сложности времени алгоритма (три вложенных цикла)

ответ

Смежные вопросы