PDA

View Full Version : shell sort

miracle
چهارشنبه 16 اسفند 1385, 01:30 بعد از ظهر
پیچیدگی shell sort چقدر هست؟
whitehat
چهارشنبه 16 اسفند 1385, 02:44 بعد از ظهر
O(n^2)

اطلاعات بیشتر (http://linux.wku.edu/~lamonml/algor/sort/shell.html)
Microsoft.net
چهارشنبه 16 اسفند 1385, 03:50 بعد از ظهر
البته محاسبه پیچیدگی اگوریتم شل خیلی سخت و متغیر هست و بستگی به انتخاب اندازه K داره
Smart User
شنبه 19 اسفند 1385, 12:43 قبل از ظهر
راستش تا جایی که من میدونم نمی تونیم اوردر دقیق به دست بیاریم..
raha_hakhamanesh
سه شنبه 22 اسفند 1385, 06:08 بعد از ظهر
با سلام

ببخشید دوستان صحبت دوستمون کلاه سفید درسته و مرتبه زمانی اون
O(nk) is order of shell sort

موفق باشید
miracle
سه شنبه 22 اسفند 1385, 11:08 بعد از ظهر
بدترین حالت میشه(O(n^2 ...بهترین حالتش چی میشه؟
whitehat
سه شنبه 22 اسفند 1385, 11:32 بعد از ظهر
O(nLog(n))
الگوریتم ها در حالت ایده ال سعی می کنند به (O(n نزدیک شوند اما در بهترین حالت ما حداقل به میزان بالا مقایسه نیاز داریم.
البته محاسبه پیچیدگی اگوریتم شل خیلی سخت و متغیر هست و بستگی به انتخاب اندازه K دارهدر صورتی که منظور شما θ باشد ، حرف شما صحیح می باشد، اما می توان ماکزیمم پیچیدگی با استفاده از روش های گوناگون بدست آورد . در مورد این الگوریتم بهتره بگیم در بدترین شرایط پیچیدگی برابر مقدار زیر است

Ω(n^2)