الگوریتم های جستجوی جدید و بهبود یافته و تجزیه و تحلیل دقیق پیچیدگی حالت متوسط آنها
ترجمه نشده

الگوریتم های جستجوی جدید و بهبود یافته و تجزیه و تحلیل دقیق پیچیدگی حالت متوسط آنها

عنوان فارسی مقاله: الگوریتم های جستجوی جدید و بهبود یافته و تجزیه و تحلیل دقیق پیچیدگی حالت متوسط آنها
عنوان انگلیسی مقاله: New and improved search algorithms and precise analysis of their average-case complexity
مجله/کنفرانس: سیستم های کامپیوتری نسل آینده – Future Generation Computer Systems
رشته های تحصیلی مرتبط:  مهندسی کامپیوتر
گرایش های تحصیلی مرتبط:  الگوریتم و محاسبات - مهندسی نرم افزار
کلمات کلیدی فارسی: جستجوی باینری، جستجوی سه جانبه، الگوریتم جستجو، پیچیدگی حالت متوسط
کلمات کلیدی انگلیسی: Binary search, Ternary search, Searching algorithm, Average-case complexity
نوع نگارش مقاله: مقاله پژوهشی (Research Article)
نمایه: Scopus – Master Journals – JCR
شناسه دیجیتال (DOI): https://doi.org/10.1016/j.future.2019.01.043
دانشگاه: Computer Engineering Department, Ankara University, 06830, Turkey
ناشر: الزویر - Elsevier
نوع ارائه مقاله: ژورنال
نوع مقاله: ISI
سال انتشار مقاله: 2019
شاخص H_index: 85 در سال 2019
شاخص SJR: 0.844 در سال 2017
شناسه ISSN: 0167-739X
شاخص Quartile (چارک): Q1 در سال 2017
فرمت مقاله انگلیسی: PDF
تعداد صفحات مقاله انگلیسی: 38
وضعیت ترجمه: ترجمه نشده است
قیمت مقاله انگلیسی: رایگان
آیا این مقاله بیس است: خیر
کد محصول: E11999
فهرست انگلیسی مطالب

Abstract
1. Introduction
2. Binary search and its two different implementations
3. The ternary search algorithm
4. Proposed improved ternary search (ITS) algorithm
5. The proposed binary–quaternary search algorithm
6. Implementation of ITS and BQS algorithms
7. Experimental results and comparisons
8. Conclusion
Acknowledgments
References

نمونه متن انگلیسی مقاله

Abstract


In this paper, we consider the searching problem over ordered sequences. It is well known that Binary Search (BS) algorithm solves this problem with very efficient complexity, namely with the complexity . The developments of the BS algorithm, such as Ternary Search (TS) algorithm do not improve the efficiency. The rapid increase in the amount of data has made the search problem more important than in the past. And this made it important to reduce average number of comparisons in cases where the asymptotic improvement is not achieved. In this paper, we identify and analyze an implementation issue of BS. Depending on the location of the conditional operators, we classify two different implementations for BS which are widely used in the literature. We call these two implementations weak and correct implementations. We calculate precise number of comparisons in average case for both implementations. Moreover, we transform the TS algorithm into an improved ternary search (ITS) algorithm. We also propose a new Binary–Quaternary Search (BQS) algorithm by using a novel dividing strategy. We prove that an average number of comparisons for both presented algorithms ITS and BQS is less than for the case of correct implementation of the BS algorithm. We also provide the experimental results.

  • اشتراک گذاری در

دیدگاه خود را بنویسید:

تاکنون دیدگاهی برای این نوشته ارسال نشده است

الگوریتم های جستجوی جدید و بهبود یافته و تجزیه و تحلیل دقیق پیچیدگی حالت متوسط آنها
نوشته های مرتبط
مقالات جدید
لوگوی رسانه های برخط

logo-samandehi

پیوندها