न्यूनतम जटिलता

Question

के साथ एनाग्राम एल्गोरिदम मुझे हाल ही में एक एल्गोरिदम तैयार करने के लिए कहा गया था जो जांचता है कि दो तार एक-दूसरे के आरेख हैं या नहीं। मेरा लक्ष्य अंतरिक्ष और समय की जटिलता को कम करना था, इसलिए मैं इस एल्गोरिदम के साथ आया:

1. 26 तत्वों की एक सरणी बनाएं, प्रत्येक को शून्य से प्रारंभ किया गया है।
2. पहली स्ट्रिंग को पार करें और प्रत्येक वर्ण के लिए, उस वर्ण से संबंधित सरणी तत्व को बढ़ाएं।
3. दूसरी स्ट्रिंग को पार करें और प्रत्येक वर्ण के लिए, उस वर्ण से संबंधित सरणी तत्व को कम करें।
4. सरणी पर स्कैन करें। यदि सभी तत्व 0 हैं, तो दो तार आरेख हैं।

हालांकि, इस एल्गोरिदम की समय जटिलता ओ (एन) है और मैं कम जटिलता वाले एल्गोरिदम के साथ नहीं आ सकता। क्या किसी को पता है?

Answer 1

आपका एल्गोरिदम असम्बद्ध रूप से इष्टतम है। Ω (एन) समय से बेहतर किसी भी समस्या को हल करना संभव नहीं है। इसे देखने के लिए, मान लीजिए कि एक एल्गोरिदम ए मौजूद है जो ओ (एन) समय में समस्या को हल कर सकता है (ध्यान दें कि यह यहां n का छोटा है)। फिर किसी भी 1> और ईपीएसलॉन के लिए; > 0, कुछ एन ऐसा है कि आकार के किसी भी इनपुट के लिए कम से कम एन, एल्गोरिदम को अधिकांश और ईपीएसलॉन में समाप्त करना होगा; एन चरण। सेट और ईपीएसलॉन; = 1/3 और एल्गोरिदम के लिए किसी भी इनपुट पर विचार करें जो कि इस और ईपीएसलॉन के लिए उपर्युक्त एन के लिए कम से कम n है। चूंकि एल्गोरिदम दो तारों में वर्णों में से अधिकांश 1/3 देख सकता है, तो फ़ंक्शन में दो अलग-अलग इनपुट होना चाहिए, जो कि एनाग्राम की एक जोड़ी है और ऐसा नहीं है, जैसे कि एल्गोरिदम देखता है प्रत्येक इनपुट के पात्रों का एक ही सबसेट। फ़ंक्शन को प्रत्येक मामले में एक ही आउटपुट का उत्पादन करना होगा, और इस प्रकार कम से कम एक इनपुट पर गलत होगा। हम एक विरोधाभास तक पहुंच गए हैं, इसलिए ऐसा कोई एल्गोरिदम मौजूद नहीं होना चाहिए।

Answer 2

यह सुनिश्चित करने के लिए कि स्ट्रिंग्स एनाग्राम हैं जिन्हें आपको पूरे तारों की तुलना करने की आवश्यकता है - तो यह ओ (एन) से तेज़ कैसे हो सकता है?

Answer 3

आप संभवतः शुरुआती निकास के साथ औसत प्रदर्शन में सुधार कर सकते हैं। दूसरी स्ट्रिंग स्कैन करते समय, यदि आपके द्वारा कमी से पहले [char] 0 गिनती है, तो आपके पास कोई एनाग्राम नहीं है और आप स्कैनिंग रोक सकते हैं।

इसके अलावा, यदि तार 26 वर्णों से कम हैं, तो अंतिम चरण में, शून्य के लिए पहली स्ट्रिंग में केवल वर्णों की जांच करें।

यह बड़ा ओ नहीं बदलता है, लेकिन यह आपके डेटा के आधार पर प्रस्तावित समाधान के 2 एन +26 ओ से कम कुछ के लिए अपना औसत रनटाइम बदल सकता है।

Answer 4

int anagram (char a[], char b[]) { 

    char chars[26]; 
    int ana = 0; 
    int i =0; 

    for (i=0; i<26;i++) 
     chars[i] = 0; 


    if (strlen(a) != strlen(b)) 
     return -1; 

    i = 0; 
    while ((a[i] != '\0') || (b[i] != '\0')) { 
     chars[a[i] - 'a']++; 
     chars[b[i] - 'a']--; 
     i++; 
    } 

    for (i=0; i<26;i++) 
     ana += chars[i]; 

    return ana; 

} 


void main() { 

    char *a = "chimmy\0"; 
    char *b = "yimmch\0"; 

    printf ("Anagram result is %d.\n", anagram(a,b)); 


}