मुसीबत दिए गए एन 3-आयामी बिंदु जो {$ p_1, p_2, .., p_n $} हैं जहां $ p_i = (x_i, y_i, z_i) $। मुझे सूत्र का मूल्य मिलना है
कुछ दिए गए निरंतर पूर्णांक पी, क्यू, आर, एस के लिए सभी संख्याएं 1 और एम (= 100) के बीच हैं।
मुझे इस सूत्र के लिए गणना के लिए एक कुशल विधि की आवश्यकता है
$ O (n ^ 2) $ से बेहतर जटिलता को कम करने के बारे में कोई विचार दें
उत्तर:
जवाब के लिए 2 № 1यह मानते हुए कि सभी निर्देशांक 1 और 100 के बीच हैं, तो आप इसे निम्न के माध्यम से कर सकते हैं:
सभी बिंदुओं (3 * 100 * 100) संचालन के 3 डी हिस्टोग्राम की गणना करें।
3 अक्षों में से प्रत्येक के साथ हिस्टोग्राम के संकल्प की गणना करने के लिए एफएफटी का उपयोग करें
इसके परिणामस्वरूप 3 डी वैक्टरों का 3 डी हिस्टोग्राम होगा। फिर आप अपने वांछित मूल्य की गणना करने के लिए इस हिस्टोग्राम पर फिर से शुरू कर सकते हैं।
मुख्य बिंदु यह है कि एक संकल्प की गणनामूल्यों का हिस्टोग्राम उन मानों के जोड़ों के अंतर के हिस्टोग्राम की गणना करता है। इसका उपयोग समान मूल्यों के मूल्यों के हिस्टोग्राम की गणना करने के लिए भी किया जा सकता है।
जवाब के लिए 0 № 2
आपकी समस्या एक कण संभावित समस्या (उदाहरण के लिए इलेक्ट्रोडडायनामिक्स में आपके जैसा है) की तरह दिखती है, जहां आपको स्थान पर कुछ "संभावित" ढूंढना होगा (x_j, y_j) से सभी प्राथमिक योगदानों को जोड़कर i-th कणों।
इस वर्ग के लिए विशिष्ट तेज़ एल्गोरिदम विशिष्ट हैसमस्या फास्ट मल्टीपोल विधि है। इस खोजशब्द को देखो, लेकिन मुझे आपको चेतावनी देना चाहिए कि यह समझने या लागू करने के लिए आसान नहीं है। मजबूत गणित पृष्ठभूमि की जरूरत है।