عرض بسيط للتسجيلة

المؤلفMaghrabi, Saud M.A. [سعود محمد عبد الله مغربي]
تاريخ الإتاحة2009-11-25T15:14:36Z
تاريخ النشر2000
اسم المنشورQatar University Science Journal
الاقتباسQatar University Science Journal, 2000, Vol. 20, Pages 7-15.
معرّف المصادر الموحدhttp://hdl.handle.net/10576/9747
الملخصThere are two widely used random distributions on binary trees, namely the binary search tree distribution and the uniform distribution. By analyzing the performance of algorithms that manipulate binary trees generated at random, it is possible to assess the average case performance of the algorithm. This average case performance is often a more useful reflection of the algorithm's suitability than the worst-case performance. An algorithm may have a worst-case run time that is of exponential time complexity, but an average-case run time that is of polynomial time complexity. In such cases, one wishes to assess the performance of an algorithm on a 'typical' range of tree structures and thus relate properties of randomly generated trees, such as depth, to aspects affecting the algorithm's run-time. The purpose of this paper is to design and implement a random binary trees generation algorithm that considers the average case performance. The algorithm is differ from both the uniform distribution and the binary search tree distribution. Analysis of the behaviour of the algorithm is given.
اللغةen
الناشرQatar University
الموضوعMathematics
الرياضيات
العنوانA Random Binary Trees Generation Method
العنوان البديلطريقة لإنشاء الأشجار الثنائية بشكل عشوائي
النوعArticle
الصفحات7-15
رقم المجلد20
الملخص البديلهناك نوعان من التوزيعات العشوائية والتي تستخدم على نطاق واسع ، هما: توزيع شجرة البحث الثنائية، والتوزيع المتماثل . بتحليل أداة الخوارزميات (الطرق ) التي حلت مشكلة إنشاء الأشجار الثنائية بشكل عشوائي ، وجد أنه من المحتمل أن يُقَوَّمَ إنجاز الخوارزمية باستعمال متوسط حالة إنجازها . يعطي متوسط حالة إنجاز الخوارزمية في الغالب انعكاساً مفيداً لمدى ملاءمة الخوارزمية أكثر مما يعطيه أسوأ حالات إنجازها ، أسوأ حالات وقت التنفيذ لأي خوارزمية يمثل مدى التعقيد في هذا الوقت ، ولكن متوسط الحالة لوقت التنفيذ يمثل تعقيداً متعدد الحدود في وقت . من مثل هذه الحالات، إذا رغب أحدنا في أن يُقوّم أداء خوارزمية على مجموعة مثالية من الأشجار المنتظمة من حيث الخواص المستعملة بإنشاء الأشجار بشكل عشوائي ، ومن أمثلة هذه الخواص خاصية العمق ، وكذلك من حيث السمات المؤثرة في وقت تنفيذ الخوارزمية . إن الهدف من هذا البحث هو تصميم وتطبيق خوارزمية لإنشاء الأشجار الثنائية بشكل عشوائي بحيث يعتمد تَقْوِيم أداء هذه الخوارزمية على متوسط حالة وقت التنفيذ. وتختلف هذه الخوارزمية عن التوزيعين المذكورين أعلاه : التوزيع المتماثل ، وتوزيع شجرة البحث الثنائي ، ولقد تمت دراسة وتحليل خوارزمية هذا البحث .
dc.accessType Open Access


الملفات في هذه التسجيلة

Thumbnail

هذه التسجيلة تظهر في المجموعات التالية

عرض بسيط للتسجيلة