0
나는 다음과 같은 알고리즘의 큰-O를 계산하지만 난 혼란 스러워요 어떤 도움을 필요로하는 시도하고는 :빅 O/빅 - 오 표기법
Algorithm 1. DFS(G,n)
Input: G- the graph
n- the current node
1) Visit(n)
2) Mark(n)
3) For every edge nm (from n to m) in G do
4) If m is not marked then
5) Dfs(G,m)
6) End If
7) End For
Output: Depends on the purpose of the search...
난 무슨 말을 시작하지 않을 것이다 I (잘못) 해답을 계산했습니다. 아무도 나 좀 도와 줄래?
감사합니다.
편집 : 분명히 내 계산 O(n+m) 올바른지 ... 누군가가 이것을 확인할 수 있습니까?
편집 2 : 아니면 O(|n|+|m|)입니까?
Noo, 숙제라고 생각하면 계산 한 내용을 말해야하며 아무리 노력해도 증명하지 않으면 아무도 도움을주지 못합니다. –
나는 추론을 시작해야한다고 생각하며 도와 줄 것이다. 당황하지 말고, 시도한 것을 보여주는 것이 낫습니다. 그렇지 않으면 우리는 당신이 우리에게 당신을 위해 숙제를 해 줄 것이라고 가정 할 것입니다 :-). –
@ Justin 나는 이것이 실제로 수정이며 숙제가 아니라는 점을 지적하고자합니다. 그러므로 나는이 알고리즘의 Big-O를 스스로 선택하여 계산하려고 결정한 사람이다. 그러나 당신이 절대적으로 알아야한다면, 나는 그것을 O (n + m)로 계산했다. 보시다시피, O (x + y)를 결과로 가져 오는 Big-O를 보지 못했기 때문에 (거의 확실한) 잘못된 것입니다 ... @ Mark이 사실이 내 추론의 타당성을 입증하기를 바랍니다! :-D – MusTheDataGuy