Time Analysis in Data Structure

Time Analysis in Data Structure – निम्न Algorithm द्वारा किसी Array के N Elements का जोड किया जा सकता है-

//====================================================
SUMMATION(LA, N)

Here LA is a Linear Array and N is the size of LA.

• SUM = 0, LB = 0, UB = N-1                          [ Initialization ]

• REPEAT STEP 3 WHILE I <= UB STEP I = I + 1

• SUM = SUM + LA[I]          [ Sum the Values of Array’s All Elements ]

• EXIT                                                       [ Finish ]

//========================================================================

जैसाकि हमने पहले बताया कि किसी भी Algorithm को Perform होने में कितना समय लगेगा ये ज्ञात करना काफी मुशिकल है। इसलिए हम Algorithm की Complexity को Data Items की Size के फलन के रूप में ही ज्ञात कर सकते हैं। Algorithm के Time को हम किसी Algorithm द्वारा Perform होने वाली Comparisons संख्‍या के आधार पर ज्ञात करते हैं।

कोई Algorithm Perform होते समय कुल कितने Operations करता है, उन्हीं Operations की संख्‍या को हम Algorithm के Perform होने के Time के रूप में मान लेते हैं। यानी जितने अधिक Operations Algorithm द्वारा Perform होते हैं उस Algorithm को Perform होने में उतना ही अधिक समय लगता है।

Time Algorithm में मानलो कि Data Item की संख्‍या n = 10 है तो यदि दसों संख्‍याओं को जोडने के लिए इस Algorithm में कुल 10 Operations होते हैं। इस स्थिति में इस Algorithm को Perform होने में कुल 10 Operation करने पडते हैं तो इस Algorithm की Complexity का फलन f(n) = n होगा।

यानी इस Algorithm को Perform होने में यदि Data Item की संख्‍या N है तो कुल Operation की संख्‍या भी N होगी और हर Operation में 1/N समय लगता है अत: कुल समय भी N ही लगेगा।

मानलो कि यदि Array के प्रथम Element को दूसरे Element से जोडने में एक सेकण्‍ड लगता है तो Data Item की संख्‍या 10 होने पर कुल दस बार जोड होगी और लगने वाला समय 10 सेकण्‍ड होगा।