Временная сложность представления списка смежности?

Я прохожу по этой ссылке для представления списка смежности.

http://www.geeksforgeeks.org/graph-and-its-presentations/

У меня простое сомнение по поводу какой-то части кода:

// A utility function to print the adjacenncy list representation of graph
void printGraph(struct Graph* graph)
{
    int v;
    for (v = 0; v < graph->V; ++v)
    {
        struct AdjListNode* pCrawl = graph->array[v].head;
        printf("\n Adjacency list of vertex %d\n head ", v);
        while (pCrawl)
        {
            printf("-> %d", pCrawl->dest);
            pCrawl = pCrawl->next;
        }
        printf("\n");
    }
}

Поскольку здесь для каждого V цикла while выполняется повторение d раз, где d - степень каждой вершины.

Итак, я думаю, что временная сложность похожа на

d0 + d1 + d2 + d3 ....... +dV where di is the degree of each vertex.

Все это составляет O (E), но ссылка говорит, что временная сложность O (| V | + | E |)

Не уверен, в чем проблема с пониманием. Здесь нужна помощь


algorithm time-complexity adjacency-list breadth-first-search
person Garrick    schedule 08.07.2017    source источник
comment
Предположим, что у графа нет ребер. Сколько времени занимает алгоритм?   -  person user2357112 supports Monica    schedule 08.07.2017
comment
@ user2357112 Мы должны проверять или сканировать каждую вершину один раз, верно? Но это вложенный цикл, поэтому разве временная сложность не должна быть такой?   -  person Garrick    schedule 08.07.2017

Ответы (1)


arrow_upward
16
arrow_downward

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

  • The outer loop is executed O(|V|) regardless of the graph structure.
    • Even if we had no edges at all, for every iteration of the outer loop, we would have to do a constant number of operations (O(1))
    • Внутренний цикл выполняется один раз для каждого ребра, то есть O (deg (v)) раз, где deg (v) - степень текущего узла.
    • Таким образом, время выполнения одной итерации внешнего цикла составляет O (1 + deg (v)). Обратите внимание, что мы не можем пропустить 1, потому что deg (v) может быть 0, но нам все равно нужно проделать некоторую работу на этой итерации.
  • Суммируя все это, мы получаем время выполнения O (| V | * 1 + deg (v1) + deg (v2) + ...) = O (| V | + | E |).

Как упоминалось ранее, | E | может быть довольно маленьким, так что нам все равно придется учитывать работу, выполняемую исключительно во внешнем цикле. Таким образом, мы не можем просто удалить | V | срок.

person Tobias Ribizel    schedule 08.07.2017
comment
Если есть внешний цикл из n итераций, тогда сложность времени должна быть O (V * E), верно? что мне здесь не хватает? - person Midhunraj R Pillai; 29.12.2020
comment
Общее количество ребер E - это лишь очень пессимистическая верхняя граница объема работы, которую вы выполняете за одну итерацию цикла. Вы можете добиться большего, заметив, что мы рассматриваем только degree(v) исходящие ребра для каждой вершины v плюс некоторая дополнительная постоянная работа (чтение указателя головы для v). Сумма всех степеней в два раза превышает количество ребер. Таким образом, в целом нам требуется только постоянный объем работы для каждой вершины и ребра (как указано в последнем пункте списка). - person Tobias Ribizel; 29.12.2020
comment
хорошо, теперь все имеет смысл. Спасибо. - person Midhunraj R Pillai; 31.12.2020