GATE CS Algorithms Questions in Hindi | विस्तृत समाधान के साथ हल की गई समस्याएं [Free PDF]

फ़्लॉइड वारशॉल एल्गोरिथ्म गतिशील प्रोग्रामिंग प्रतिमान पर आधारित है।

यह सभी युग्म सबसे छोटे पथ प्राप्त करता है:

प्रत्येक युग्म (i, j) के लिए विचार करें, दो संभावित स्थितियाँ हैं:

1) k, i से j तक के सबसे छोटे पथ में मध्यवर्ती शीर्ष नहीं है। हम dist[i][j] का मान यथावत रखते हैं।

2) k, i से j तक के सबसे छोटे पथ में एक मध्यवर्ती शीर्ष है। हम dist[i][j] के मान को dist[i][j] + dist[.k][j] के रूप में अपडेट करते हैं

यह आरेख इसे दिखाता है:

गतिशील प्रोग्रामिंग प्रतिमान का उपयोग करते हुए, हम कंप्यूटर सभी युग्म सबसे छोटी पथ समय जटिलता O(V3) है।

दिए गए मान हैं: 10 (एक स्थिर मान)

√n (एक चर n का वर्गमूल जो कोई भी मान ले सकता है) n (एक चर) log2n (लघुगणक)

$\frac{100}{n}$ (यह 100 को एक चर से विभाजित करता है)

जैसा कि हम जानते हैं कि स्पर्शोन्मुख जटिलता के मामले में स्थिरांक एक चर से छोटा होता है क्योंकि एक चर किसी भी मान को छोटा या बड़ा ले सकता है। लेकिन जब हम 10 की तुलना $\frac{100}{n}$ से करते हैं, क्योंकि 100 n से विभाज्य है और यदि n अनंत में जाता है तो यह मान शून्य हो जाएगा। तो, $\frac{100}{n}$ 10 से छोटा है।

log2n के मामले में वृद्धि दर लॉगरिदमिक है जो रैखिक वृद्धि से छोटा है।

√n और n के बीच तुलना। n के मामले में रैखिक वृद्धि, यह √n से बड़ी है।

तो, पूर्ण क्रम है: $\frac{100}{n}$ < 10 < log2 n < √n < n

वैकल्पिक विधि:

n = 21024 लेना

10, $2^{\frac{1024}{2}}$, $\frac{100}{2^{1024}}$, log2(21024), 21024

10, 2512, $\frac{100}{2^{1024}}$, 1024 × log22, 21024

10, 2512, $\frac{100}{2^{1024}}$, 1024, 21024

बढ़ते क्रम के संदर्भ में:

100/(2 ¹⁰²⁴ ) < 10 <1024 <2 ⁵¹² <2 ¹⁰²⁴