PDA

View Full Version : بهترین الگوریتم جستجو



vbprogrammerx
سه شنبه 23 اسفند 1384, 20:04 عصر
بهترین الگوریتم جستجو را اگه کسی می دونه بزاره(سریع تر از جستجوی باینری)

razavi_university
سه شنبه 23 اسفند 1384, 21:49 عصر
الگوریتم Quick Sort از باینری سریعتره بستگی به کارت داره به کتاب طراحب الگوریتم حعفرنژاد یه نگاهی بکن

3tareh
سه شنبه 23 اسفند 1384, 22:08 عصر
سلام
فکر کنم بهترین جستجو binarySearch هست که از O (lg n) می باشد ولی داده ها باید sort شده باشد.


الگوریتم Quick Sort از باینری سریعتره
Quick Sort برای sort کردن استفاده می شه و در حالت متوسط از O (n log n ) ولی از باینری برای search استفاده می کنند.

vbprogrammerx
چهارشنبه 24 اسفند 1384, 19:02 عصر
ممنونم ازتون اما یه الگوریتم سریعتر سراغ ندارید......

sara_2004sh2003
چهارشنبه 24 اسفند 1384, 20:19 عصر
برای اطلاعات بیشتر به کتاب طراحی الگوریتم نوشته مهندس خلیلی مراجعه کن

.مهدی فهمیده غلامی.
جمعه 26 اسفند 1384, 23:57 عصر
بهترین متد جستجو در یک ساختمان داده خطی چنانچه ان ساختمان داده از قبل مرتب باشد
الگوریتم جستجوی دودویی است در بهترین حالت دارای مربته زمانی(1)O
می باشد در حالت متوسط LOG N و بدترین حالت N می باشد .
روش های HASH نیز با مرتبه زمانی (1)O نیز موجود می باشند.
QUICK SORT یک روش مرتب سازی داده هاست.

nasiri_m
شنبه 27 اسفند 1384, 10:32 صبح
فکر می کنم QUICK SORT سریعترین باشد مگر در حالتی که لیست نزولی یا صعودی باشد که استثنا است

3tareh
شنبه 27 اسفند 1384, 12:13 عصر
سلام
برای جستجوی دودویی می تونین از درخت های قرمز-سیاه استفاده کنین چون زمان اجرا در آنها در بدترین حالت از O(log n) است.
البته جستجوی روی درخت های B-tree از red-black ها هم سریعتر است ولی باید توجه داشته باشید که B-tree ها برای کار روی دیسک های مغناطیسی یا سایر وسایل ذخیره سازی ثانویه با دسترسی مستقیم هستند و برای داده هایی که در حافظه ذخیره شده اند کاربردی ندارند.

someCoder
شنبه 27 اسفند 1384, 16:08 عصر
بهترین الگوریتم جستجو را اگه کسی می دونه بزاره(سریع تر از جستجوی باینری)
تو چه ساختمان داده ای؟


الگوریتم Quick Sort از باینری سریعتره
سرچ رو چجوری با سورت مقایسه می کنن؟!!!


روش های HASH نیز با مرتبه زمانی (1)O نیز موجود می باشند.
به نظر من هم منطقی ترین جواب به این سوال همینه.



فکر می کنم QUICK SORT سریعترین باشد مگر در حالتی که لیست نزولی یا صعودی باشد که استثنا است از چی سریعتره؟ Bubble sort؟


سوالی که من اینجا میبینم در مورد ساختمان داده مورد نظر هیچی نگفته، پس سریعترین راه همون Hash با (O(1 هست

mohandese_hiclass
جمعه 25 فروردین 1385, 23:56 عصر
سلام
برای جستجوی دودویی می تونین از درخت های قرمز-سیاه استفاده کنین چون زمان اجرا در آنها در بدترین حالت از O(log n) است.
البته جستجوی روی درخت های B-tree از red-black ها هم سریعتر است ولی باید توجه داشته باشید که B-tree ها برای کار روی دیسک های مغناطیسی یا سایر وسایل ذخیره سازی ثانویه با دسترسی مستقیم هستند و برای داده هایی که در حافظه ذخیره شده اند کاربردی ندارند.

دوست عزیز هزینه ایجاد این درختها رو حساب کردید که از خود هزینه جستجو زیادترند؟؟؟؟:متفکر:

mohandese_hiclass
شنبه 26 فروردین 1385, 00:00 صبح
من آخرش نفهمیدم انجا بحث روی جستجوست یا مرتب سازی ولی اگه موضوع جستجو هست بستگی داره به ساختمان داده مسئله و نحوه چیدمان اعداد ولی اگه مسئله مرتب سازی باز اون هم شرایط بالا رو داره و نیشه گفت همیشه QUICK SORT سریعترین ما برای مرتب سازی الگوریتمی با پیچیدگید n هم داریم

k.robot
یک شنبه 27 فروردین 1385, 13:15 عصر
دوست عزیر شما میتوانید به random binary search مراجعه کنید.

arash_hemmat
یک شنبه 27 فروردین 1385, 23:57 عصر
دوست عزیر شما میتوانید به random binary search مراجعه کنید.
هزینه random binary search که در بدترین حالت همون n میشه!

mohandese_hiclass
دوشنبه 28 فروردین 1385, 10:40 صبح
هزینه random binary search که در بدترین حالت همون n میشه!

آرش جان حرف شما کاملا درسته ولی به یک نکته دقت نکردید اونم تتای random binary search

در این مورد هم کمی فکر کنید اگه کمکی لازم بود من با کمال میل کمکتون می کنم

k.robot
دوشنبه 28 فروردین 1385, 14:40 عصر
دوست عزیز همونجوری که مهندس اشاره کرده اشاره من به هزینه متوسطه

محمد صادق
سه شنبه 29 فروردین 1385, 12:30 عصر
به نظر من از باینری سرچ (با احتساب هزینه اش) هیچی بهتر نیست.

sadaf_m
دوشنبه 15 خرداد 1385, 18:44 عصر
برای تعداد کمتر از 20 به ترتیب:

InsertionSort
QuickSort
MergeSort
HeapSort
SelectionSort
BubbleSortسرعت کم میشود و برای تعداد بیشتر از 20 به ترتیب زیر سرعت مرتب سازی و جستجو کم می شود :

QuickSort
MergeSort
HeapSort
InsertionSort
SelectionSort
BubbleSort

mohandese_hiclass
جمعه 19 خرداد 1385, 20:51 عصر
برای تعداد کمتر از 20 به ترتیب:

InsertionSort
QuickSort
MergeSort
HeapSort
SelectionSort
BubbleSortسرعت کم میشود و برای تعداد بیشتر از 20 به ترتیب زیر سرعت مرتب سازی و جستجو کم می شود :

QuickSort
MergeSort
HeapSort
InsertionSort
SelectionSort
BubbleSort

میشه به مرجعی که این مطالب و نوشته اید اشاره کنید

sadaf_m
جمعه 19 خرداد 1385, 22:56 عصر
میشه به مرجعی که این مطالب و نوشته اید اشاره کنید


من این مطلب رو از جزوه ی ساختمان داده ی ترم پیشم پیدا کردم. ولی اگه بخواین می تونم
در مورد منبعش تحقیق کنم.
و البته فکر میکنم این نتیجه با آزمون و خطا بدست اومده باشه و ممکنه اثبات ریاضی نداشته باشه.

mohandese_hiclass
دوشنبه 22 خرداد 1385, 18:57 عصر
من این مطلب رو از جزوه ی ساختمان داده ی ترم پیشم پیدا کردم. ولی اگه بخواین می تونم
در مورد منبعش تحقیق کنم.
و البته فکر میکنم این نتیجه با آزمون و خطا بدست اومده باشه و ممکنه اثبات ریاضی نداشته باشه.
من خودم چنین برنامه ای نوشتم ولی در بعضی موارد با نوشته شما متناقضه اگه مرجعشو لطف کنید خوشحال می شم شاید من اشتباه می کنم

Developer Programmer
جمعه 26 خرداد 1385, 11:12 صبح
الگوریتم جستجوی دودویی در بهترین حالت دارای مربته زمانی(1)O
می باشد در حالت متوسط LOG N و بدترین حالت N می باشد . از اونجایی که لیست مرتبا نصف میشه ؛ پس در بدترین حالت یا در جستجوی ناموفق log N میشه (نه n )

rezamarmouz
سه شنبه 14 تیر 1390, 15:56 عصر
بستگی داره خوب، هر کدوم در یه زمانی کاربرد داره. این کد همه ی جستوجو هاست:

http://mycollege.ir/forum/index.php/topic,135.0.html

هر کدوم برای زمان و شرایط خاص کاربرد دارن، مثلا وقتی تعداد داده ها زیادن هرمی خوبه و وقتی کمتر از مثلا 40 تا باشن دودیی و ... البته اینارو از خودم گفتم و اشتباه هستن :D

parva-88
یک شنبه 19 تیر 1390, 11:13 صبح
دوست عزیز هزینه ایجاد این درختها رو حساب کردید که از خود هزینه جستجو زیادترند؟؟؟؟:متفکر:

quick sort چون مرتبه ی اجراییش کمتره و مناسب تره !

farzaneh69
جمعه 29 مهر 1390, 16:01 عصر
سلام دوستان من ترم 5 کارشناسی نرم افزار هستم در در س طراحی الگوریتم با مشکلی روبه رو شده ام .به نظر شما چه گونه می توان نمودار زمانی برای الگوریتم دودویی با 1000 داده را به دست اورد .

minaalamshahi
سه شنبه 04 شهریور 1393, 11:46 صبح
این الگوریتم ها مگه الگوریتم های مرتب سازی نیست؟
یه لینک خوب و جامع برای تحقیق در مورد الگوریتم های سرچ و سرچ در رشته سراغ دارید؟