#java #graph #adjacency-matrix
#java #График #Матрица смежности
Вопрос:
в java для создания МАТРИЦЫ СМЕЖНОСТИ требуется O (V * V) , но поскольку, когда мы создаем 2D логический массив в java, все начальные значения элементов равны false, и для каждого ребра, которое мы вводим, нам нужно обновить значения вершин до TRUE … поэтому временная сложность должна бытьO(E), где E — количество ребер!!! я где-то ошибаюсь??
Комментарии:
1. если ваше распределение выполняет инициализацию, оно считается линейным по количеству выделенных элементов, поэтому простое выделение
V*VэлементовO(V*V)2. но она автоматически инициализируется значением false, когда мы создаем 2d-массив …. так что, это тоже нужно учитывать во временной сложности???
3. как вы ожидаете, что он будет инициализирован автоматически ? с помощью темной магии? или с помощью цикла?