OCaml：將元素添加到數組中的列表中

我正在OCaml中製作一個基本程序，其中使用了圖形。我定義的曲線爲：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）

我是對嗎？如果我是，我是否有辦法保持這種線性？

我不明白「a」是什麼。只是內容？或者是在圖表中添加一些信息？ – Lhooq

是的，我實際上是在線性時間內求解2-CNF-QBF，我的頂點是litterals，並且從a到b有一個邊，並且從b到a，如果我有一個子句（a或b） - 其中a和b也是輸尿管 - –

好的。無論如何，我保留它;-) – Lhooq

讓我們來看看你做什麼（我更願意把它改寫以更可讀的方式;-)）：

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

對於a -> b您通過添加b相應榜單邊緣添加到您的陣列中的每個邊緣到a。得到一個數組的內容是O（1），並添加元素的列表是O（1）也因此，如果我們恢復你做了什麼

它看起來像這樣的線性方式。當您必須查找是否連接了兩個頂點時，問題就會出現。 ;-)

2016-06-13 00:25:51 Lhooq

將數組的內容設置爲「x」是恆定的？它不需要O（x）？ –

@Anatole Dahan：標準數據結構（即列表，數組等）被優化，因此對元素的訪問是O（1），設置這個元素也是如此。 – RichouHunter

@RichouHunter創建和訪問任意元素是O（1）在數組中，但在列表中，訪問第i個元素將在O（i）中完成。 ;-) – Lhooq

回答