我有一個類似于加權有向圖的鄰接矩陣表示的類。假設圖有n頂點。下面是它的作業原理：
- 首先，分配 n 2個槽來保存整數（存盤在名為 的變數
graph中），以陣列的形式，n每個陣列都有n整數。 - 為邊分配權重，其中
graph[i][j]表示從 vertexi到 vertex的邊的權重j。 - 取消分配圖中所有未使用的插槽
示例代碼：
class DiGraph {
public:
Graph() {}
Graph(size_t n) {
graph.resize(n);
for (size_t i = 0; i < n; i ) {
graph[i] = new int[n]{-1};
}
}
void addEdge(int from, int to, int weight) {
graph[from][to] = weight;
}
int& getEdge(int from, int to) {
return *(graph[from] to);
}
void finalizeGraph() {
for (size_t i = 0; i < n; i ) {
for (size_t j = 0; j < n; j ) {
if (graph[i][j] == -1) {
delete &graph[i][j];
}
}
}
}
private:
vector<int*> graph;
};
現在我想實作一個演算法，它只應該在圖的現有邊上作業。換句話說，除了輸入圖中已經存在的邊之外，該演算法不應該創建新的邊。我想有效地使用記憶體，同時實作對兩個頂點之間任何邊的 O(1) 訪問。
上述圖實作的空間復雜度在邊數上是否有效線性？
uj5u.com熱心網友回復：
不，不是，除非您可以證明分配和取消分配邊緣的方式獨立于n，根據您的描述，這不太可能。
請記住，Big O符號考慮了演算法的最壞情況。由于您首先分配n^2插槽然后洗掉不存在的邊，因此在最壞情況下您的演算法運行時間是O(n^2)，而不是O(n)。換句話說，隨著n增長，您的演算法運行時間也會增長，O(n^2)因為您必須分配和取消分配不存在的邊。這是真的，除非您可以證明分配和取消分配邊的方式獨立于n.
為了在邊方面達到線性運行時，您需要一個不同的資料結構，其中邊的作業量為O(m)，其中 m 是邊的數量。
但是，您可以爭辯說，如果給出這樣的圖，即洗掉不存在的邊，那么O(1)假設您的資料結構支持它，則每個邊的訪問時間可以是 。
轉載請註明出處，本文鏈接：https://www.uj5u.com/gongcheng/421203.html
標籤：
上一篇：如何修復constchar*必須匹配先前的回傳型別錯誤？
下一篇：當send()在TCPC套接字中只發送一次時，recv()會讀取多次。難道我做錯了什么？我可以同步套接字通信嗎？