Сложность времени для переноса графика

Question

Я хотел бы получить некоторую помощь для анализа временной сложности следующей функции.

Графы хранят все вершины в списке векторов. Каждая вершина имеет вектор, который хранит края вершин. Этот вектор называется соседи.

Graph 
Graph::transpose() const 
{ 
    Graph Graph_T; 

    for(auto& vertex : list) 
    { 
     Graph_T.insert_vertex(vertex -> get_name()); 
    } 

    for(auto& vertex : list) 
    { 
     for(auto& edges : vertex -> neighbours) 
     { 
     Graph_T.insert_edge(edges,vertex); 
     } 
    } 
    return Graph_T; 
} 

Первый за цикл, очевидно, V | , где | V | - число вершин.

Вторая петля также | V | но имеет третью петлю, расположенную внутри. Моя догадка заключается в том, что третья сложность времени цикла равна | E |, где | E | - количество ребер в графе.

Сумма: Сложность времени равна/theta (V + V + E) =/theta (E + V).

Является ли мой анализ правильным?

Answer 1

Я бы сказал, что O (| V |^2), поскольку существует двойной для: внешний выполняется | V | раз, а внутренняя - максимум | V | раз.