Apriori एल्गोरिदम की कम्प्यूटेशनल जटिलता निम्नलिखित कारकों से प्रभावित हो सकती है -
सपोर्ट थ्रेशोल्ड
सपोर्ट थ्रेशोल्ड को कम करने के परिणामस्वरूप उच्च आइटमसेट को लगातार घोषित किया जाता है। इसका एल्गोरिदम की कम्प्यूटेशनल जटिलता पर प्रतिकूल प्रभाव पड़ता है क्योंकि उच्च उम्मीदवार आइटमसेट उत्पन्न और गिने जाने चाहिए।
लगातार आइटमसेट का अधिकतम आकार भी कम सपोर्ट थ्रेशोल्ड के साथ सुधरता है। जैसे-जैसे लगातार आइटमसेट का अधिकतम आकार सुधरता है, एल्गोरिदम को डेटा सेट पर अधिक पास बनाने की आवश्यकता होगी।
आइटम की संख्या (आयामिता)
जैसे-जैसे कई आइटम की संख्या बढ़ती है, आइटम के सपोर्ट काउंट को सहेजने के लिए अधिक स्थान की आवश्यकता होगी। यदि कई लगातार आइटम भी डेटा की आयामिता के साथ बढ़ते हैं, तो गणना और I/O मूल्य उच्च उम्मीदवार आइटमसेट के कारण बढ़ेंगे जो एल्गोरिदम द्वारा उत्पन्न होते हैं।
लेनदेन की संख्या
क्योंकि Apriori एल्गोरिदम डेटासेट पर बार-बार पास बनाता है, इसका रन टाइम अधिक लेनदेन की संख्या के साथ बढ़ता है।
औसत लेनदेन चौड़ाई
घने डेटा सेट के लिए, औसत लेनदेन चौड़ाई अधिक हो सकती है। यह Apriori एल्गोरिदम की जटिलता को दो तरीकों से प्रभावित करता है जैसे कि लगातार आइटमसेट का अधिकतम आकार औसत लेनदेन चौड़ाई बढ़ने के साथ बढ़ता है। लेनदेन चौड़ाई बढ़ने पर, उच्च आइटमसेट लेनदेन में शामिल होते हैं। यह सपोर्ट काउंटिंग के दौरान लागू कई हैश ट्री ट्रैवर्सल की संख्या बढ़ाएगा।
लगातार 1-आइटमसेट की पीढ़ी
प्रत्येक लेनदेन के लिए, लेनदेन में मौजूद प्रत्येक आइटम के लिए सपोर्ट काउंट अपडेट करना आवश्यक है। यह देखते हुए कि w औसत लेनदेन चौड़ाई है, इस ऑपरेशन को O(Nw) समय की आवश्यकता होती है, जहां N लेनदेन की कुल संख्या है।
उम्मीदवार पीढ़ी
उम्मीदवार k-आइटमसेट बनाने के लिए, लगातार (k-1)-आइटमसेट के जोड़े को यह तय करने के लिए जोड़ा जाता है कि क्या उनके पास कम से कम k-2 आइटम समान हैं। प्रत्येक जोड़ ऑपरेशन को अधिकतम k-2 समानता तुलनाओं की आवश्यकता होती है। सर्वोत्तम स्थिति में, प्रत्येक जोड़ चरण एक व्यवहार्य उम्मीदवार k-आइटमसेट बनाता है।
सबसे खराब स्थिति में, एल्गोरिदम को पिछली पुनरावृत्ति में पाए गए लगातार (k-1)-आइटमसेट के प्रत्येक जोड़े को जोड़ना चाहिए। इसलिए, लगातार आइटमसेट को जोड़ने की पूरी लागत है
$$\mathrm{\sum_{k=2}^w (k-2)|C_k| < \text{Cost of merging} < \sum_{k=2}^w (k-2)|F_{k-1}|^2}$$
उम्मीदवार पीढ़ी के दौरान एक हैश ट्री भी बनाया जाता है ताकि उम्मीदवार आइटमसेट को सहेजा जा सके। ट्री की अधिकतम गहराई k होने के कारण, उम्मीदवार आइटमसेट के साथ हैश ट्री को भरने की लागत O(Σ k|C_k|) है।
उम्मीदवार प्रूनिंग के दौरान, यह जांचना आवश्यक है कि प्रत्येक उम्मीदवार k-आइटमसेट के k-2 उपसमुच्चय लगातार हैं। क्योंकि हैश ट्री में एक उम्मीदवार को देखने की लागत O(k) है, उम्मीदवार प्रूनिंग चरण को O(Σ k|C_k|) समय की आवश्यकता होती है।
