बिग ओ नोटेशन को समझना - कोडिंग साक्षात्कार को क्रैक करना

Question

मुझे यह समझने में मदद की ज़रूरत है कि लेखक को बिग ओ अध्याय में समस्या 11 का जवाब कैसे मिला।

समस्या इस प्रकार है:

निम्नलिखित कोड प्रिंट लंबाई कश्मीर के सभी तार जहां क्रमबद्ध क्रम में वर्ण हैं। यह लंबाई के सभी तारों को उत्पन्न करके और फिर प्रत्येक को क्रमबद्ध करने की जांच करके ऐसा करता है। इसका रनटाइम क्या है?

public static int numChars = 26; 

public static void printSortedStrings(int remaining) { 
    printSortedStrings(remaining, ""); 
} 

public static void printSortedStrings(int remaining, String prefix) { 
    if (remaining == 0) { 
     if (isInOrder(prefix)) { 
      System.out.println(prefix); // Printing the string 
     } 
    } else { 
     for (int i = 0; i < numChars; i++) { 
      char c = ithLetter(i); 
      printSortedStrings(remaining - 1, prefix + c); 
     } 
    } 
} 

public static boolean isInOrder(String s) { 
    for (int i = 1; i < s.length(); i++) { 
     int prev = ithLetter(s.charAt(i - 1)); 
     int curr = ithLetter(s.charAt(i)); 
     if (prev > curr) { 
      return false; 
     } 
    } 
    return true; 
} 

public static char ithLetter(int i) { 
    return (char) (((int) 'a') + i); 
} 

public static void main(String[] args) { 
    printSortedStrings(2); 
} 

बुक जवाब:

हे (केसी ^{कश्मीर}), जहां कश्मीर स्ट्रिंग और ग की लंबाई है वर्णमाला में वर्णों की संख्या है। यह प्रत्येक स्ट्रिंग उत्पन्न करने के लिए ओ (सी ^के) लेता है। फिर, हमें यह जांचना होगा कि इनमें से प्रत्येक को क्रमबद्ध किया गया है, जो ओ (के) समय लेता है।

ध्यान दें कि स्ट्रिंग को प्रिंट करना ऊपर दिए गए उत्तर में ध्यान में नहीं रखा गया है, लेकिन मैंने अन्य समस्याओं में विपरीत देखा है।

आप रनटाइम में स्ट्रिंग को मुद्रित करते समय खाते में कब लेते हैं?

इस सही जवाब हे (कश्मीर ग ^{कश्मीर}) होगा?

इसके अलावा, यह भी सलाह देने में सक्षम होने पर कोई सलाह है कि इस कोड के रनटाइम में एक घातीय भाग बहुत सराहना की जाएगी। :)

Answer 1

संक्षेप में, नहीं। सही जवाब ओ (केसी ^के) पुस्तक में है।

यह जांचने के लिए कि क्या उसके पात्रों का आदेश दिया गया था, एक स्ट्रिंग पर जाने के बाद, ओ (के) ले जाएगा, प्रिंटिंग में केवल ओ (के) जोड़ना होगा - जो आपकी जटिलता को नहीं बदलेगा।

मान लें कि स्ट्रिंग का आदेश दिया गया है या नहीं, संचालन लेता है, और प्रिंटिंग b*k लेता है। फिर प्रत्येक स्ट्रिंग के लिए संचालन की कुल संख्या (a+b)*k पर है जो अभी भी ओ (के) है।

संपादित करें: अपने प्रश्न के दूसरे भाग के बारे में, कुछ निश्चित लंबाई के साथ सभी शब्दों पर जा रहा एक घातीय क्रम जटिलता का परिणाम देगा के बाद से वहाँ ग ^{कश्मीर} ऐसे शब्दों जहां c वर्णमाला के आकार है और k शब्द की लंबाई है।

Answer 2

स्ट्रिंग प्रिंटिंग k समय के लिए केवल एक अतिरिक्त अतिरिक्त है।

जांच की जा रही प्रत्येक स्ट्रिंग क्रमबद्ध किया जाता है कि क्या O(k) है और कहते हैं कि यह मुद्रण कुछ पूर्णांक d (एक निरंतर) के लिए O(dk) है। दो जोड़ना हमें O(k + dk) मिलता है, जिसे O(k(1 + d)) के रूप में लिखा जा सकता है। क्योंकि यह सिर्फ एक स्केलर है जिसे हम O(k + dk) = O(k) जानते हैं, इसलिए उत्तर नहीं बदलता है।

Answer 3

सामान्य रूप से निरंतर लंबाई स्ट्रिंग की छपाई निरंतर मानी जाती है, लेकिन यदि हम सटीक होना चाहते हैं तो मूल ऑपरेशन के रूप में एक वर्ण के प्रिंट पर विचार करें: इसका मतलब है कि एके लंबाई स्ट्रिंग को मुद्रित करने के लिए हमारे पास O(k) है ।

जब से हम हे है (ग ^{कश्मीर}) संभव तार और उनमें से प्रत्येक हम अगर यह सॉर्ट हो जाता है की जाँच करने के (ओ (के साथ)) और उन्हें (एक और हे (के)) मुद्रित करने के लिए है के लिए, कुल जटिलता ओ (सी ^के (के + के)) = ओ (2 सी ^के के) बन गया।

लेकिन निरंतर कारक के लिए एक फ़ंक्शन गुणा करने से इसकी जटिलता नहीं बदली है, और इसलिए उत्तर ओ (सी ^के के) रहता है।