PDA

View Full Version : سوال: Decision Tree



M.e.T.i
دوشنبه 24 فروردین 1388, 14:20 عصر
سلام.
میخواستم یه چیزایی در مورد Decision Tree بدونم. کسی میتونه راهنماییم کنه؟

pesar irooni
دوشنبه 24 فروردین 1388, 17:02 عصر
درخت تصمیم یه درخت دودویی که مقایسه بین عناصر رو نشون میده و در اصل فرآیند مرتب سازی رو شرح میده.
هر گره داخلی تو این درخت مقایسه بین دو تا عنصر رو نشون میده و برگهای این درخت هم جایگشت بین عناصر رو نشون میده که یکی از این جایگشت ها (برگ ها) بصورت مرتب شده اعداد لیست رو نشون میده.
ارتفاع این درخت هم حداقل log (n!) = n log n هست که به عنوان حد پایین برای مرتب سازی های مقایسه ای در بدترین حالته.
لبه ها یا شاخه های این درخت هم که دوتاست عبارت است از => و < که حاصل مقایسه بین دو عدد رو نشون میده. هر مسیر تو درخت تصمیم از ریشه تا برگ نشون دهنده دنباله ای از محاسباته که یه الگوریتم مرتب سازی میتونه تولید کنه.
http://homepages.ius.edu/RWISMAN/C455/html/notes/Chapter8/ch8-1.gif