PHP फ़ंक्शंस जटिलता में निर्मित है (isAnagramOfPalindrome फ़ंक्शन)

Question

मैं पिछले 2 घंटों से गुगल रहा हूं, और मुझे फ़ंक्शंस समय और स्थान जटिलता में निर्मित PHP की एक सूची नहीं मिल रही है।

expected worst-case time complexity is O(N) 

expected worst-case space complexity is O(1) (not counting the storage required for input arguments). 

जहां एन इनपुट स्ट्रिंग लंबाई है: मैं निम्नलिखित अधिकतम स्वीकृत जटिलता के साथ हल करने के लिए isAnagramOfPalindrome समस्या है। यहां मेरा सबसे सरल समाधान है, लेकिन मुझे नहीं पता कि यह जटिलता सीमा के भीतर है या नहीं।

class Solution { 

    // Function to determine if the input string can make a palindrome by rearranging it 
    static public function isAnagramOfPalindrome($S) { 

     // here I am counting how many characters have odd number of occurrences 
     $odds = count(array_filter(count_chars($S, 1), function($var) { 
      return($var & 1); 
     })); 
     // If the string length is odd, then a palindrome would have 1 character with odd number occurrences 
     // If the string length is even, all characters should have even number of occurrences 
     return (int)($odds == (strlen($S) & 1)); 
    } 
} 

echo Solution :: isAnagramOfPalindrome($_POST['input']); 

किसी को भी इस तरह की जानकारी कहां मिल सकती है?

संपादित

मुझे पता चला array_filter हे (एन) जटिलता है, और count हे (1) जटिलता है। अब मुझे count_chars पर जानकारी प्राप्त करने की आवश्यकता है, लेकिन भविष्य की porblems के लिए एक पूर्ण सूची बहुत सुविधाजनक होगी।

संपादित 2

सामान्य रूप में स्थान और समय जटिलता पर कुछ शोध करने के बाद, मुझे पता चला इस कोड हे (एन) समय जटिलता और हे (1) अंतरिक्ष जटिलता है कि क्योंकि:

count_chars लूप एन बार (इनपुट स्ट्रिंग की पूरी लंबाई, इसे ओ (एन) की प्रारंभिक जटिलता देगा)। यह सीमित अधिकतम संख्या वाले फ़ील्ड (26 सटीक, विभिन्न वर्णों की संख्या) के साथ एक सरणी उत्पन्न कर रहा है, और फिर यह इस सरणी पर एक फ़िल्टर लागू कर रहा है, जिसका अर्थ है कि फ़िल्टर सबसे अधिक 26 गुना लूप करेगा। अनंतता की ओर इनपुट लंबाई को दबाते समय, यह पाश महत्वहीन होता है और इसे स्थिर के रूप में देखा जाता है। गणना इस जेनरेटेड निरंतर सरणी पर भी लागू होती है, और इसके अलावा, यह महत्वहीन है क्योंकि count फ़ंक्शन जटिलता ओ (1) है। इसलिए, एल्गोरिदम की समय जटिलता ओ (एन) है।

यह अंतरिक्ष जटिलता के साथ समान है। अंतरिक्ष जटिलता की गणना करते समय, हम इनपुट की गणना नहीं करते हैं, केवल प्रक्रिया में उत्पन्न वस्तुओं। ये ऑब्जेक्ट्स 26-तत्व सरणी और गिनती चर हैं, और दोनों को स्थिरांक के रूप में माना जाता है क्योंकि उनके आकार में इस बिंदु पर वृद्धि नहीं हो सकती है, इससे कोई फर्क नहीं पड़ता कि इनपुट कितना बड़ा है। तो हम कह सकते हैं कि एल्गोरिदम में ओ (1) की एक स्पेस जटिलता है।

वैसे भी, यह सूची अभी भी मूल्यवान होगी इसलिए हमें PHP स्रोत कोड के अंदर देखने की आवश्यकता नहीं है। :)

Answer 1

इस जानकारी को शामिल करने के लिए एक संभावित कारण यह है कि प्रति रिलीज को बदलने की संभावना है, क्योंकि सामान्य मामले के लिए सुधार/अनुकूलन किए जाते हैं।

पीएचपी सी पर बनाया गया है, कार्यों में से कुछ बस ग समकक्षों के आसपास रैपर हैं, उदाहरण के hypot एक गूगल खोज, man hypot पर एक नज़र, वह गणित के लिए डॉक्स में lib http://www.gnu.org/software/libc/manual/html_node/Exponents-and-Logarithms.html#Exponents-and-Logarithms

स्रोत वास्तव में के लिए कोई बेहतर जानकारी https://github.com/lattera/glibc/blob/a2f34833b1042d5d8eeb263b4cf4caaea138c4ad/math/w_hypot.c (आधिकारिक नहीं, केवल लिंक करने में आसान)

उल्लेख नहीं है, यह केवल ग्लिबैक है, विंडोज़ का एक अलग कार्यान्वयन होगा।तो वहाँ भी ओएस प्रति एक अलग बड़ा हे कि PHP

एक और कारण हो सकता है क्योंकि यह सबसे डेवलपर्स भ्रमित हैं पर संकलित किया गया है हो सकता है। अधिकांश डेवलपर मैं बस "सर्वश्रेष्ठ" बड़ा हे

अधिकतम does not के साथ एक समारोह का चयन करेंगे पता है का मतलब हमेशा यह अपनी धीमी

http://www.sorting-algorithms.com/

कुछ कार्यों के साथ हो रहा क्या का एक अच्छा दृश्य प्रोप है , यानी बबल सॉर्ट एक "धीमा" प्रकार है, फिर भी यह लगभग क्रमबद्ध डेटा के लिए सबसे तेज़ है। त्वरित क्रम है जो कई उपयोग करेंगे, जो वास्तव में लगभग क्रमबद्ध डेटा के लिए बहुत धीमी है। बिग ओ सबसे खराब मामला है - PHP एक रिलीज के बीच निर्णय ले सकता है कि उन्हें किसी निश्चित स्थिति के लिए अनुकूलित करना चाहिए और इससे कार्य के बड़े ओ को बदल दिया जाएगा और दस्तावेज़ को दस्तावेज करने का कोई आसान तरीका नहीं है।

यहाँ एक आंशिक सूची (जो मुझे लगता है कि आप देखा है) है

List of Big-O for PHP functions

कौन सा अधिक आम पीएचपी कार्यों में से कुछ की सूची है।

इस विशेष उदाहरण के लिए ....

काफी आसान इसके कार्यों में बनाया का उपयोग किए बिना हल करने के लिए।

उदाहरण कोड

function isPalAnagram($string) { 
    $string = str_replace(" ", "", $string); 
    $len = strlen($string); 
    $oddCount = $len & 1; 
    $string = str_split($string); 
    while ($len > 0 && $oddCount >= 0) { 
    $current = reset($string); 
    $replace_count = 0; 
    foreach($string as $key => &$char) { 
     if ($char === $current){ 
     unset($string[$key]); 
     $len--; 
     $replace_count++; 
     continue; 
     } 
    } 
    $oddCount -= ($replace_count & 1); 
    } 

    return ($len - $oddCount) === 0; 

} 

तथ्य यह है कि एक से अधिक 1 अजीब गिनती नहीं किया जा सकता का उपयोग करके आप सरणी से जल्दी लौट सकते हैं।

I सोचें मेरा ओ (एन) समय भी है क्योंकि इसका सबसे बुरा मामला ओ (एन) है जहां तक ​​मैं कह सकता हूं।

टेस्ट

$a = microtime(true); 
for($i=1; $i<100000; $i++) { 
    testMethod("the quick brown fox jumped over the lazy dog"); 
    testMethod("aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa"); 
    testMethod("testest"); 
} 
printf("Took %s seconds, %s memory", microtime(true) - $a, memory_get_peak_usage(true)); 

टेस्ट वास्तव में पुराने हार्डवेयर

Took 64.125452041626 seconds, 262144 memory 

आपका रास्ता

Took 112.96145009995 seconds, 262144 memory 

का उपयोग करके चलाए मेरे रास्ते मैं काफी यकीन है कि मेरे रास्ते तेज तरीका नहीं है कर रहा हूँ या तो।

मैं वास्तव में PHP (उदाहरण के लिए जावा) के अलावा अन्य भाषाओं के लिए अधिक जानकारी नहीं देख सकता।

मैं जानता हूँ कि इस पोस्ट का एक बहुत के बारे में क्यों अपने वहाँ नहीं और थेरेस नहीं एक बहुत विश्वसनीय सूत्रों से ड्राइंग, मुझे आशा है कि प्रलेखन पृष्ठ में सूचीबद्ध अपनी एक आंशिक रूप से समझाया क्यों बड़ा हे नहीं है, हालांकि