मैं तुलना करने के लिए सरल एल्गोरिदम लिख रहा हूं कि दो वैक्टर ए 1 और ए 2 पूर्णांक एनाग्राम हैं (वे अलग-अलग ऑर्डर में समान तत्व होते हैं)। उदाहरण के लिए {2,3,1} और {3,2,1} आरेख हैं, {1,2,2} और {2,1,1} नहीं हैं।एल्गोरिदम बनाम सैद्धांतिक चलने वाले समय कार्यों के प्रयोगात्मक चलने वाले समय की तुलना
यहाँ मेरी एल्गोरिथ्म है (यह बहुत आसान है):
1. for (i = 1; i <= a1.length; i++)
1.1. j = i
1.2. while (a1[i] != a2[j])
1.2.1. if (j >= a1.length)
1.2.1.1. return false
1.2.2. j++
1.3. tmp = a2[j]
1.4. a2[j] = a2[i]
1.5. a2[i] = tmp
2. return true
दो विपर्यय की तुलना का प्रतिनिधित्व: 
समय चल रहा है के समारोह पर विचार वेक्टर पर निर्भर आकार टी (एन) जब वे कर रहे हैं की सुविधा देता है दो परिस्थितियों में एनाग्राम: पेसिमिस्टिक और औसत।
- निराशावादी
होता है वैक्टर डुप्लिकेट तत्व नहीं कब और वैक्टर रिवर्स आदेश में हैं।
सी 3 में बहुलता, सी 4 और C6 हैं:
तो pesimistic प्रसारण समय के लिए अंतिम समारोह है: 
समीकरण (3) लिखा जा सकता है एक सरल रूप में: 
- औसत
होता है वैक्टर डुप्लिकेट तत्व नहीं कब और वैक्टर यादृच्छिक आदेश में हैं। यहां गंभीर धारणा यह है कि: औसतन हम ए 1 से क्रमशः ए 1 से संबंधित तत्व पाते हैं (2/सी 3, सी 4 और सी 6 में जे/2)।
सी 3 में बहुलता, सी 4 और C6 हैं: 
अंतिम समारोह है: 
सरल रूप में लिखा: 
यहाँ मेरी अंतिम निष्कर्ष और सवाल यह है: समीकरण में
b2 (8) (4) 
मैं अधिकार के साथ हूँ समीकरण में a2 दो बार से छोटा होता है (9)?
मैंने सोचा था कि वेक्टर आकार के समारोह में एल्गोरिथ्म का चलने का समय की साजिश रचने जो कर सकते हैं सबूत समीकरण (9), लेकिन यह नहीं बताया गया है: 
भूखंड हम देख सकते हैं कि अनुपात a2/b2 1.11 है पर, में पसंद नहीं समीकरण (9) कहां है 2. उपरोक्त साजिश में अनुपात भविष्यवाणी से बहुत दूर है। वह क्यों है?
@StackFlowed यह एक प्रश्न जैसा प्रतीत होता है। एक बहुत अच्छी तरह लिखित एक। – chbaker0
@Everettss मुझे लगता है कि आपकी समस्या आपकी धारणा है: "औसतन हम ए 1 से क्रमशः ए 1 से संबंधित तत्व पाते हैं।" यह धारणा कहां से आती है? – chbaker0
@mebob मैंने इस धारणा को अच्छी तरह से ज्ञात पुस्तक में एल्गोरिदम/थॉमस एच। कॉर्मन परिचय http://www.ime.usp.br/~geiser/courses/MAC5711%20-%20An%C3% A1lise% 20de% 20Algoritmos/परिचय% 20to% 20 एल्गोरिदम% 20 (प्रशिक्षक का% 20 मैनुअल) .pdf आप इसे पेज 11 पर और 18 पृष्ठ पर एक ही धारणा पर पा सकते हैं: "⇒ औसतन, जबकि लूप को सॉर्ट किए गए माध्यम से आधा रास्ते देखना पड़ता है subarray ए [1। जे - 1] यह तय करने के लिए कि कुंजी कहां छोड़ें। ⇒ tj = j/2। " मैं इसे प्रयोगात्मक रूप से भी मापता हूं। यह आधे रास्ते में है। मैंने इसका उल्लेख नहीं किया: मैं प्रत्येक बिंदु को 100 बार साजिश पर मापता हूं। – Everettss