OCaml: добавить элемент в список внутри массива

Question

Я делаю базовую программу в OCaml, в которой я использую графики. я определил график как:

type 'a graph = ('a * int list) array;; 

, где элементы в массиве являются вершинами, а элементы в списках является ребром от вершины. Мне нужно построить граф в O (| V | + | E |), который кажется законным. Итак, я сначала построил массив вершин с пустыми списками. Теперь я хочу добавить ребра.

Единственный способ, который я вышел с таким:

let addEdge a b g = g.(a)<-(fst g.(a), b::snd g.(a));; 

Я не совсем уверен в этом, но мне кажется, что это линейное по степени А в то время я это сделать , Это означало бы, что если одна из моих вершин соединена со всеми остальными вершинами, она возьмет меня O (n^2)

Я прав? Если да, то должен ли я сохранить эту линейность?

Answer 1

Давайте посмотрим, что вы делаете (я предпочитаю, чтобы переписать его в более читаемом образом ;-)):

let addEdge a b g = 
    let (c, al) = g.(a) in 
    g.(a) <- (c, b :: al);; 

Для каждого ребра a -> b вы добавляете этот край в массив, добавив b в список соответствующего до a. Получение содержимого массива является O (1) и добавления элемента в список является O (1) тоже так, если мы возобновим, что вы сделали

• O (| V |) для создания массива
• O (| E |) добавить края
• O (| V | + | E |) для создания и заполнения массива

Это выглядит как линейный способ делать. Проблема возникнет, когда вам нужно будет найти, связаны ли две вершины. ;-)