एल्गोरिदम की लागत

संक्रियाएँ गिनना

दूसरा प्रश्न

पाठ सही लूप की रचना और पुनरावर्तन ने यह सिद्ध करना सिखाया कि कोई एल्गोरिदम सही है: कि वह समाप्त होता है और उसका परिणाम पश्च-शर्त को पूरा करता है। परंतु पाठ संख्यात्मक एल्गोरिदम ने अभाज्यता के दो समान रूप से सही परीक्षण दिखाए, एक लगभग $n$ विभाजनों वाला और दूसरा लगभग $\sqrt{n}$ वाला, और पाठ पुनरावर्तन ने $F_{30}$ की गणना के दो सही तरीके दिखाए, एक $2\,692\,537$ कॉल वाला और दूसरा 29 जोड़ों वाला। यदि ऐसा है, तो चुनने के लिए सही होना पर्याप्त नहीं: दो सही एल्गोरिदमों में से एक क्षण भर में उत्तर दे सकता है और दूसरा तब तक समाप्त न हो कि उत्तर का महत्त्व ही न रहे। अतः किसी एल्गोरिदम से पूछा जाने वाला दूसरा प्रश्न यह है कि उसकी लागत कितनी है।

लागत घड़ी से भी मापी जा सकती है, और चौथा अनुभाग ऐसा करेगा। पर एक निष्पादन का समय मशीन पर, कंपाइलर पर, उसके विकल्पों पर और इस पर निर्भर करता है कि कंप्यूटर उसी समय और क्या कर रहा है; उससे किसी दूसरी मशीन पर एल्गोरिदम के बारे में कुछ भी नहीं निकलता। जो इनमें से किसी पर निर्भर नहीं करता, वह है एल्गोरिदम द्वारा उठाए गए चरणों की संख्या। इससे इस पाठ का पहला निर्णय निकलता है: लागत को गिनकर मापना, और घड़ी को गिनती की जाँच के लिए रखना।

आकार और प्रभावी संक्रिया

सारे चरण गिनना (हर जोड़, हर तुलना, इंडेक्स की हर वृद्धि, मेमोरी तक हर पहुँच) थकाऊ और व्यर्थ होगा, क्योंकि लगभग सभी एक मुख्य चरण के साथ एक निश्चित अनुपात में चलते हैं। अतः प्रभावी संक्रिया चुनी जाती है: वह जो, एक स्थिर गुणक को छोड़कर, किसी भी दूसरी संक्रिया से कम बार निष्पादित नहीं होती, और इसलिए सबका प्रतिनिधित्व करती है। वेक्टर के अवयवों के योग में वह जोड़ है; अधिकतम की खोज में, तुलना; अभाज्यता परीक्षण में, भाग। उसके निष्पादनों की संख्या इनपुट आकार के फलन के रूप में व्यक्त की जाती है, जिसे $n$ कहा जाता है: वेक्टर के अवयवों की संख्या, परखी जाने वाली संख्या, अंकों की संख्या।

एक सरल लूप जो $n$ अवयवों के वेक्टर को ट्रैवर्स करता है और हर अवयव पर निश्चित मात्रा में काम करता है, अपनी प्रभावी संक्रिया $n$ बार निष्पादित करता है। इसके विपरीत, किसी खाली न हो ऐसे वेक्टर का अधिकतम पहले अवयव को उम्मीदवार मानकर शुरू करता है और बाक़ी हर अवयव की उससे तुलना करता है: $n - 1$ तुलनाएँ। $n$ और $n - 1$ के बीच का अंतर वास्तविक है, पर, जैसा तीसरे अनुभाग में दिखेगा, जो मायने रखता है उसमें वह कुछ नहीं बदलता।

सबसे बुरी स्थिति

कुछ एल्गोरिदम एक ही आकार के डेटा पर हमेशा उतनी ही संक्रियाएँ नहीं करते। वेक्टर में किसी मान की खोज, उसे तब तक ट्रैवर्स करते हुए जब तक मान न मिले, एक ही तुलना करती है यदि मान पहले स्थान पर हो, और $n$ यदि वह न हो। उसकी लागत की बात करने के लिए दोनों में से एक स्थिति चुनी जाती है, और सामान्य चुनाव है सबसे बुरी स्थिति: आकार $n$ के सभी इनपुटों में संक्रियाओं की अधिकतम संख्या। कारण वही है जिससे अनुबंध उन सभी इनपुटों के लिए लिखा जाता है जो पूर्व-शर्त पूरी करते हैं: सबसे बुरी स्थिति एक गारंटी है, और सबसे अच्छी स्थिति एक आशा। इसलिए रैखिक खोज की लागत सबसे बुरी स्थिति में $n$ तुलनाएँ है, और जब यह पाठ बिना किसी और विशेषण के “लागत” कहता है, तो उसका आशय सबसे बुरी स्थिति की लागत से होता है।

नेस्टेड लूप

पाठ लूप ने दो नेस्टेड लूपों के चक्कर गिनना सिखाया। यदि भीतरी लूप हमेशा $m$ चक्कर लगाता है, बाहरी लूप के $n$ चक्करों में से हर एक के लिए, तो भीतरी शरीर $n \cdot m$ बार निष्पादित होता है। यदि भीतरी लूप बाहरी पर निर्भर है, तो पंक्ति-दर-पंक्ति जोड़ा जाता है। संग्रहों के साथ काम करते समय सबसे अधिक आने वाली स्थिति सभी युग्मों की है: हर अवयव की तुलना उसके बाद आने वाले हर अवयव से करना, जैसे यह खोजते समय कि किसी वेक्टर में दोहराव हैं या नहीं।

#include <print>​int main(){    for (int n{10}; n <= 10'000; n *= 10) {        long long comparisons{0};        for (int i{0}; i < n; ++i) {            for (int j{i + 1}; j < n; ++j) {                ++comparisons;            }        }        std::println("n = {:>6}: {:>10} तुलनाएँ; n(n - 1)/2 = {}",                     n, comparisons, static_cast<long long>(n) * (n - 1) / 2);    }}

n =     10:         45 तुलनाएँ; n(n - 1)/2 = 45n =    100:       4950 तुलनाएँ; n(n - 1)/2 = 4950n =   1000:     499500 तुलनाएँ; n(n - 1)/2 = 499500n =  10000:   49995000 तुलनाएँ; n(n - 1)/2 = 49995000

काउंटर उस तुलना का स्थान लेता है जो वास्तविक एल्गोरिदम करता। बाहरी लूप के चक्कर $i$ में, भीतरी लूप $i + 1$ से $n - 1$ तक जाता है और $n - 1 - i$ चक्कर लगाता है; इस प्रकार कुल योग $(n - 1) + (n - 2) + \cdots + 1 + 0$ है, पाठ लूप का योग:

आउटपुट हर आकार के लिए सूत्र की पुष्टि करता है। काउंटर long long है क्योंकि लगभग पैंसठ हज़ार के $n$ से युग्मों की संख्या int (इस प्लेटफ़ॉर्म पर 32 बिट का) के अधिकतम से अधिक हो जाती है, और सूत्र इसी कारण रूपांतरण के बाद गुणा करता है: द्विघाती एल्गोरिदम का काउंटर डेटा से बहुत पहले ओवरफ़्लो हो जाता है।

अभी से देख लें कि तीसरा अनुभाग किसका सामान्यीकरण करेगा: $n$ को 10 से गुणा करने पर तुलनाएँ लगभग 100 से गुणा हो जाती हैं। दस डेटा पर, 45 तुलनाएँ; दस हज़ार पर, लगभग पाँच करोड़।