[理工] 資結 複雜度

[kiwidoit (噗嚕噗嚕)]

1,
undirected graph 用 adjacency List表示法，假設n=|V|,e=|E|
求 vertex vi 的 degree的time complexity.

我想問的是:一般都是寫O(length(list(i)))

可是我覺得length(list(i))最差應該等於e

所以應該要是O(e)才對啊 = =，那為什麼要用O(length(list(i)))

有誰可以告訴我為什麼嗎?

2,

接續上一題，求total edge number:O(n+e)

為什麼不是O(max(n,e))，把n跟e看成不同的複雜度

那複雜度不是應該相加取其大嗎，還是我觀念有錯 = =?

3,
Let G=[V,A] be a directed graph and A={(1,2),(2,3),(1,3)}.

Each pair (i,j) in A means that there is an arc from node i to node j.

Write an algorithm to count the in-degree and out degree of graph G.

解答:
for(i=1;i<=n)
{ indegree[i]=outdegree[i]=0; }

while(not EndOfInput)
{
  input(i,j);
  indegree[j]++;
  outdegree[i]++;
}

for(i=1;i<=n;i++)
{ output indegree[i], outdegree[i]; }

我的書上寫上面程式的複雜度是O(|V|+|E|)

跟前兩題一樣，為什麼不是O(max(|V|,|E|)) ?

4,
Given a binomial min-heap of n keys, what is the worst-case running time

of each of the following operations?

(1)Insert (2)Delete-minimum (3)Find-minimum (4) Meld (5) Decrease-key

我有問題的是(2)跟(5)，題目沒明確講要actual cost 還是 amortized cost，

這樣回答時是要寫actual cost還是amortized cost ?














--
※ 發信站: 批踢踢實業坊(ptt.cc) 
◆ From: 140.123.22.28
→ kiwidoit:有人會嗎= =?
推 gskman:第一題,這問題就像是一個n^2的程式,你可以說他是O(n^3),
→ gskman:也可以說是O(n^2),兩個都對,但是我們會選比較嚴謹的答案
→ gskman:2.3 如果你能寫出一個O(max(v,e))的algo就對,但是你沒寫出
→ gskman:如同三說的for迴圈是|V|,while是|E|,加起來就是O(|V|+|E|)
→ gskman:通常題目沒要求的給amortized cost就可以了...吧
→ kiwidoit:嗯!!我後來想想，是不是因為|V|跟|E|是沒有關聯的，所以
→ kiwidoit:不能相加取其大，因為如果一般題目裡面有一個是O(n^2)跟
→ kiwidoit:跟一個是O(n)，通常複雜度會選O(n^2)，而不是寫O(n^2+n)
→ kiwidoit:請問這樣想可以嗎@口@?
→ gskman:也不是說完全沒有關聯,只能說是兩個變數