76
GB
What is the cycle detection algorithm complexity for a wait-for graph with T transactions and E edges?
IN
टी लेनदेन और ई किनारों के साथ प्रतीक्षा-ग्राफ़ के लिए चक्र पहचान एल्गोरिदम जटिलता क्या है?
A
O(T squared) always
O(T वर्ग) सदैव
B
O(log T) with sorted transactions
क्रमबद्ध लेनदेन के साथ ओ (लॉग टी)।
C
O(T + E) using DFS-based cycle detection (Depth-First Search marks visited nodes and detects back edges indicating cycles in the directed graph)
ओ(टी + ई) डीएफएस-आधारित चक्र पहचान का उपयोग करते हुए (गहराई-पहली खोज विज़िट किए गए नोड्स को चिह्नित करती है और निर्देशित ग्राफ़ में चक्रों को इंगित करने वाले पीछे के किनारों का पता लगाती है)
D
O(T factorial) for complete detection
संपूर्ण पता लगाने के लिए O(T फैक्टोरियल)।
✅ Correct Answer:
💡 Explanation / व्याख्या
Explanation (English)
DFS-based cycle detection: O(V+E) where V=transactions, E=wait-for edges. Algorithm: DFS from each unvisited node. If DFS encounters a node currently being visited (in stack): cycle found. Total time: O(T+E). The challenge is when to run detection (too frequent = overhead; too infrequent = long waits).
व्याख्या (हिन्दी)
डीएफएस-आधारित चक्र का पता लगाना: ओ(वी+ई) जहां वी=लेन-देन, ई=किनारों की प्रतीक्षा करें। एल्गोरिथम: प्रत्येक अनविज़िट नोड से डीएफएस। यदि डीएफएस को वर्तमान में देखे जा रहे नोड का सामना करना पड़ता है (स्टैक में): चक्र मिला। कुल समय: O(T+E). चुनौती यह है कि कब पता लगाना है (बहुत बार-बार = ओवरहेड; बहुत कम = लंबी प्रतीक्षा)।